Binary Tree Leaves to Doubly Linked List.

Easy

0/40

Average time to solve is 15m

0 upvote

Asked in companies

Problem statement

You are given an arbitrary binary tree with N nodes numbered from 1 to N. Your task is to remove all the leaf nodes from the tree and return them as the nodes of a doubly linked list. Also, you have to use the existing tree class for the doubly linked list with the left and the right pointers may act as the previous and next pointers of the nodes of the list.

A leaf of a binary tree is the node which does not have a left child and a right child.

For Example:

Given a binary tree -

Doubly Linked List is -
4 5 3 
And after removal of all the leaves, the inorder traversal of the tree will look like - 
2 1

Note:

1. Two nodes may have the same value associated with them.
2. The root node will be fixed and will be provided in the function.
3. The order of nodes in the doubly linked list should be the order of leaves in the tree from left to right.
3. You need to modify the binary tree in place and you only need to return the head of the doubly linked list

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

Input Format:

The first line of the input contains a single integer T, representing the number of test cases. 

The first line of each test case contains an integer 'n', representing the number of nodes in the tree.

The second line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for NULL node) 
Refer to the example for further clarification.

Example: Consider the binary tree

The input of the tree depicted in the image above will be like:

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Output Format:

For each test case, two lines will be printed-
Line 1: Doubly Linked List
Line 2: Inorder Traversal of the updated 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 <= 100
1 <= N <= 3000
Time Limit: 1sec

Sample Input 1:

1
5
1 2 3 4 5 -1 -1 -1 -1 -1 -1

Sample Output 1:

4 5 3 
2 1

Approaches (2)

Approach 1

Approach 2

Brute Force Approach.

In this approach, we use the brute force approach to solve the problem. We first traverse and collect all the leaf nodes in a list, then make a Doubly Linked List from them.

Steps :

We can use a helper function passing two parameters as the root of the binary tree and a NULL head as the starting of our newly Doubly Linked List.
We used a function leafNodes, which collects all the leaf nodes of the binary tree in the leaf list.
Now, make a new node headNode, which stores the value of the new head node of our Doubly Linked List.
Copy this headNode, in previous node prev, and the head pointer *head.
Now iterate over all the leaf nodes stored in the leaf list.
Use a current node curr, to store the current node value and store the left pointer of curr with prev and right pointer with NULL.
Update the prev with the curr, so that current value acts as the previous value for the next iteration.
Now, update the binary tree by removing all the leaf nodes from it.

Time Complexity

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

Space Complexity

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

(100% EXP penalty)

Binary Tree Leaves to Doubly Linked List.

Console