Last Updated: 31 Jul, 2021

Remove leaf nodes in Tree

Moderate

Problem statement

You are given a Generic tree. In this tree, you have to remove all the leaf nodes from the tree and return the root.

Leaf nodes are those nodes that don’t have any children.

Note :

Root Will Also Be A Leaf Node If It Doesn't Have Any Child.

For Example :

For the Given generic tree:

In this Example after removing the leaf nodes - 11, 10, 13, 9. The final answer is 5 2 7 8. Here 2 denotes the number of children 5 has.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases. Then each testcase follows.

The first line of each test case contains the elements in level order form separated by space. The order is as follows: 
Root_data, n(Number of children of Root), n children, and so on for every Node.

If any node does not have a  child, take 0 as the number of children. Refer to the example below.

1 (2)
2 3 (1 0)
4 (1)
5 (0)

Explanation :
Level 1 :
The root node of the tree is 1 and it has 2 children.

Level 2 :
First child of 1 = 2
Second child of 1 = 3
2 has 1 child.
3 has 0 children. 

Level 3 :
First child of 2 = 4
4 has 1 child.

Level 4 :
First child of 4 = 5
5 has 0 children.

The input ends when all nodes at the last level have 0 children.

Note: The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 2 3 1 4 0 1 5 0

Output Format :

For each test case, print the tree after removing the leaf nodes from the given tree level-wise and each level in a new line.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of.  Just Remove All Leaf Nodes And Return The Updated Root.

Constraints :

1 <= T <= 10
1 <= N <= 5000

Time Limit: 1sec

Solve now

Approaches

01 Approach

In this approach, we will iterate through all the nodes connected to the current node and check if any node is a leaf node or not. If a node is a leaf node then we will remove the current node else we will call this function again for the remaining nodes.

The steps are as follows:

Check if the current node is NULL or if it is a leaf node then return NULL.
Iterate through all the nodes of the current node and check if the new node is a leaf node or not.
If it is a leaf node then call the removeChild function for the current node.
Else call this function again for the new node.
Return the root.

Solve now

02 Approach

In this approach, we will take a queue index in which we will store all the non-leaf nodes and iterate through all the nodes connected to the current node and check if any node is a leaf node or not. If a node is a leaf node then we will remove the current node else we will push the current node in index.

The steps are as follows:

Check if the current node is NULL or if it is a leaf node then return NULL.
Iterate through all the nodes of the current node and check if the new node is a leaf node or not.
If it is a leaf node then call the removeChild function for the current node.
Else Push the current node into the queue.
Return the root.

Solve now