Breadth First Search Algorithm to Convert Level Order Binary Search Tree to Linked List

Given a binary search tree root, convert it to a singly linked list using level order traversal.

Constraints
1 ≤ n ≤ 100,000 where n is the number of nodes in root

Breadth First Search Algorithm to Convert a Binary Search Tree to Linked List

The Breadth First Search Algorithm is suitable in solving this problem. As we are traversing the binary tree level by level, we add a Linked Node along the way. In order to acchieve this, we need to store a previous Linked Node so that we can connect a new node to it.

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* binarySearchTreeToLinkedList(Tree* root) {
    if (!root) {
        return NULL;
    }
    queue<Tree*> Q;
    LLNode* dummy = new LLNode();
    auto head = dummy;
    Q.push(root);
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        head->next = new LLNode(p->val);
        head = head->next;
        if (p->left) {
            Q.push(p->left);
        }
        if (p->right) {
            Q.push(p->right);
        }
    }
    return dummy->next;
}

The time complexity is O(N) as we will visit each node in the Binary Search Tree exactly once, and the space complexity is O(N) as we are using a queue to push the children nodes of the next level into the queue.

The following is the Python implementation that uses the deque (double-ended queue) to implement the same BFS Algorithm:

from collections import deque

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def binarySearchTreeToLinkedList(self, root):
        if root is None:
            return None
        q = deque()
        q.append(root)
        dummy = LLNode(-1)
        head = dummy
        while len(q) > 0:
            p = q.popleft()
            head.next = LLNode(p.val)
            head = head.next
            if p.left is not None:
                q.append(p.left)
            if p.right is not None:
                q.append(p.right)
        return dummy.next

However, the Queue in Python can be simply based on the list as well – therefore the following is simpler. The list can act as a queue and the popleft is equivalent to pop(0) of list.

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def binarySearchTreeToLinkedList(self, root):
        if root is None:
            return None
        q = [root]
        dummy = LLNode(-1)
        head = dummy
        while len(q) > 0:
            p = q.pop(0)
            head.next = LLNode(p.val)
            head = head.next
            if p.left is not None:
                q.append(p.left)
            if p.right is not None:
                q.append(p.right)
        return dummy.next

–EOF (The Ultimate Computing & Technology Blog) —