Last Updated: 24 Dec, 2020

Binary Tree Leaves to Doubly Linked List.

Easy

Asked in companies

Solve now

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 -

alt txt

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

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 altImage

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

Solve now

Approaches

01 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.

Solve now

02 Approach

In this approach, we use tree traversal using recursion to modify the binary tree by extracting leaf nodes and adding them in the newly created Doubly Linked List.

Steps:

As we are using recursion, the termination condition will be, when the root becomes NULL.
As we have to add leaf nodes to the Doubly Linked List, we will check if the current node is a leaf node or not. (See def. Of leaf node in the question itself)
The left node serves as the previous pointer whereas right node serves as the next pointer in the head pointer of the Doubly Linked List.
We’ve to modify the binary tree also, thus updating the left and right child of the parent of the current leaf node.
This will modify the binary tree and create a Doubly Linked List in-place.
Recursively call the left and right child of the binary tree, for other nodes of the tree.

Solve now