Problem

Submissions

Hints & solutions

Discuss

Linked List to binary Tree

Easy

0/40

Average time to solve is 15m

0 upvote

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
1 2 3 4 -1

Sample Output 1:

4 2 1 3

Explanation of the Sample Input1:

The given linked list is :

After processing the level order input, we get the tree as:

 Hence the inorder input of the tree is 4 2 1 3

Sample Input 2:

1
10 12 15 25 30 36 -1

Sample Output 2:

25 12 30 10 36 15

Explanation of the Sample Input2:

The given linked list is :

After converting the linked list into tree, we get:

Hence the inorder traversal of the tree is 25 12 30 10 36 15

Hint 1

Use the definition of level order traversal and complete binary tree.

Approaches (1)

Approach 1

Level order traversal

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.

Time Complexity

O(N), where N is the number of nodes in the linked list.

Space Complexity

O(N), where N is the number of nodes in the linked list.

(100% EXP penalty)

Linked List to binary Tree

Console