Last Updated: 16 Dec, 2020

Linked List to binary Tree

Easy

Asked in companies

Solve now

Problem statement

Given a linked list containing N nodes where each node is associated with a certain value. The list is the representation of the level order traversal of a binary tree, you need to construct a complete binary tree from the given list and return its root.

Note

1. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes at the last level are as far left as possible.
2. All the node values are positive.
3. The size of the linked list is greater than 1.
4. The end of the linked list is represented by -1.

Input Format:

The first line of the input contains an integer T denoting the number of test cases.
The first and the only line of each test case contains the values of nodes of the linked list L, which is to be converted into the complete binary tree.

Output Format:

Print the inorder traversal of the created binary tree.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^4
Time Limit: 1sec

Solve now

Approaches

01 Approach

Since the linked list contains level order input of the tree, we can use some king of breadth-first search to create the tree.
One thing to note is that the head of the linked list is the root of the tree and the next two nodes in the list will be the left and right children respectively. Hence we know the partial binary tree.
Following the same pattern, we can create our complete tree.
The main idea is to do the level order traversal of the partially built tree. To do the level order traversal, we will use a queue.
Create an empty queue q and push the head of the linked list into the queue.
On every iteration, we pop a node from the queue, make the next two nodes in the linked list as the left and the right child of the popped node and enqueue the next two nodes. Keep on doing this until we reach the end of the linked list.
After the linked list ends, we will have our complete binary tree.

Solve now