Remove leaf nodes in Tree

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
0 upvote

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
10 3 20 30 40 2 60 50 0 0 0 0
11 2 5 1 0 0
Sample Output 1 :
10
20
11
Explanation For Sample Output 1 :

For the First Test Case, The leaf nodes are 30, 40, 60, 50. Hence, the answer is 10 1 20 where 1 is the number of children 10 has.


For the Second Test Case, The leaf nodes are 5, 1. Hence, the answer is 11 0.
Sample Input 2 :
2
3 0
5 7 1 2 3 4 6 7 8 0 0 0 0 0 0 0
Sample Output 2 :
NULL
5
Hint

Try removing the Leaf nodes of the current Node and then recursively calling the function for the remaining nodes.

Approaches (2)
Recursive 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:

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

O(N), Where N is the Total Number of Nodes.

 

We are iterating through the tree once for every Node, Hence the time complexity is O(N).

Space Complexity

O(N), where N is the total number of Nodes.

 

We are calling a recursive function for every child node, Hence the space complexity is O(N).

Code Solution
(100% EXP penalty)
Remove leaf nodes in Tree
Full screen
Console