Remove Leaf Nodes from Trees — (JAVA)

Elements of Tree

Leaf Node : The node with 0 child is a leaf node in tree .

• The approach to this problem solving — to remove the leaf nodes from any tree , is , with the help of recursion . We will work on root node , and recursion will take care of the children ( all the sub-trees of node ) of the root node .
• Here we are using dfs (Depth First Search) , to solve this problem , you can also use bfs ( using queue ) to solve this problem .
• Time Complexity : O (n) (Since we need to visit every node)

Note : This problem is generally asked in many interviews of product based companies .

1. Remove Leaf Node from a Generic Tree / N-ary Tree

• In n-ary / generic tree , if node has 0 children , then that node is a leaf .
• If such case encounter simply return null (node will be null) .
• Similarly , traverse to all nodes using recursion .

if (root.children.size() == 0){
      root = null;
      return root;
}
        
        
for(int i=root.children.size()-1 ; i >= 0 ; i--){
       if (removeLeafNodes(root.children.get(i)) == null){
            root.children.remove(root.children.get(i));
     }
}
return root;

2. Remove Leaf Node from a Binary Tree

• Since Binary Tree have maximum two nodes , if and only both nodes are null , return null . (that node will be set to null)
• Similarly , traverse to left and right sub-tree .

if (root == null){
     return root;
}
        
if (root.left == null && root.right == null){
   return null;
}
        
root.left = removeAllLeaves(root.left); 
root.right = removeAllLeaves(root.right); 
        
return root;

Bonus : These are some problems you can solve after reading this article .

1. https://leetcode.com/problems/delete-leaves-with-a-given-value/
2. https://practice.geeksforgeeks.org/problems/sum-of-leaf-nodes/1
3. https://codezen.codingninjas.com/practice/499/1945/leaf-nodes
4. https://leetcode.com/problems/delete-leaves-with-a-given-value/