Given a Linked List Representation of Complete Binary Tree. The task is to construct the Binary tree and print the level order traversal of the Binary tree.
Note: The complete binary tree is represented as a linked list in a way where if the root node is stored at position i, its left, and right children are stored at position 2*i+1, and 2*i+2 respectively. H is the height of the tree and this space is used implicitly for the recursion stack.
Examples:
Input: n = 5, k = 1->2->3->4->5
Output: 1 2 3 4 5
Explanation: The tree would look like
1
/ \
2 3
/ \
4 5
Now, the level order traversal of
the above tree is 1 2 3 4 5.
Input: n = 5, k = 5->4->3->2->1
Output: 5 4 3 2 1
Explanation: The tree would look like
5
/ \
4 3
/ \
2 1
Now, the level order traversal of
the above tree is 5 4 3 2 1.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).
Constraints:
1 <= n <= 105
1 <= ki <= 105
Approach 01:
-
C++
-
Python
void convert(Node *head, TreeNode *&root) {
// Your code here
if (head == NULL) return;
root = new TreeNode(head->data);
head = head->next;
queue<TreeNode*> q;
q.push(root);
while (head != NULL) {
TreeNode *parent = q.front();
q.pop();
TreeNode *leftChild = NULL, *rightChild = NULL;
if (head != NULL) {
leftChild = new TreeNode(head->data);
head = head->next;
q.push(leftChild);
}
if (head != NULL) {
rightChild = new TreeNode(head->data);
head = head->next;
q.push(rightChild);
}
parent->left = leftChild;
parent->right = rightChild;
}
}
class ListNode:
def __init__(self, data=0, next=None):
self.data = data
self.next = next
class TreeNode:
def __init__(self, data=0, left=None, right=None):
self.data = data
self.left = left
self.right = right
from queue import Queue
def convert(head):
if head is None:
return None
root = TreeNode(head.data)
head = head.next
q = Queue()
q.put(root)
while head is not None:
parent = q.get()
leftChild = None
rightChild = None
if head is not None:
leftChild = TreeNode(head.data)
head = head.next
q.put(leftChild)
if head is not None:
rightChild = TreeNode(head.data)
head = head.next
q.put(rightChild)
parent.left = leftChild
parent.right = rightChild
return root