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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | /** * 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; } |
/**
* 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | 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 |
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.nextHowever, 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | # 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 |
# 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) —
loading...
Last Post: Convert Base 3 String To Decimal Integer
Next Post: Teaching Kids Programming - Introduction to Object Oriented Programming
