Remove nodes on root to leaf paths of length < K

GeeksforGeeks - Remove nodes on root to leaf paths of length < K

Given a Binary Tree and a number k, remove all nodes that lie only on root to leaf path(s) of length smaller than k. If a node X lies on multiple root-to-leaf paths and if any of the paths has path length >= k, then X is not deleted from Binary Tree. In other words a node is deleted if all paths going through it have lengths smaller than k.

The idea here is to use post order traversal of the tree. Before removing a node we need to check that all the children of that node in the shorter path are already removed. There are 2 cases for a node:
i) This node becomes a leaf node in which case it needs to be deleted.
ii) This node has other child on a path with path length >= k. In that case it needs not to be delete

               1
           /      \
         2          3
      /     \         \
    4         5        6
  /                   /
 7                   8 
Input: Root of above Binary Tree
       k = 4

Output: The tree should be changed to following  
           1
        /     \
      2          3
     /             \
   4                 6
 /                  /
7                  8

    // Utility method that actually removes the nodes which are not

    // on the pathLen >= k. This method can change the root as well.

    Node removeShortPathNodesUtil(Node node, int level, int k) 

    {

        //Base condition

        if (node == null)

            return null;

              

        // Traverse the tree in postorder fashion so that if a leaf

        // node path length is shorter than k, then that node and

        // all of its descendants till the node which are not

        // on some other path are removed.

        node.left = removeShortPathNodesUtil(node.left, level + 1, k);

        node.right = removeShortPathNodesUtil(node.right, level + 1, k);

   

        // If root is a leaf node and it's level is less than k then

        // remove this node.

        // This goes up and check for the ancestor nodes also for the

        // same condition till it finds a node which is a part of other

        // path(s) too.

        if (node.left == null && node.right == null && level < k)

            return null;

   

        // Return root;

        return node;

    }

   

    // Method which calls the utitlity method to remove the short path

    // nodes.

    Node removeShortPathNodes(Node node, int k) 

    {

        int pathLen = 0;

        return removeShortPathNodesUtil(node, 1, k);

    }




This suppose each node has a level field: we can compute the level value in O(n)
https://angshukutu.wordpress.com/2015/03/14/remove-nodes-on-root-to-leaf-paths-of-length-k/

public static int labelNodes(Node root, int level){

           if(root.left == null && root.right == null){

               root.level = level;

               return level;

           }

            

           int leftLabel = -1;

           if(root.left != null){

               leftLabel = labelNodes(root.left, level+1);

           }

           int rightLabel =-1;

           if(root.right!=null){

                rightLabel = labelNodes(root.right, level+1);

           }

           root.level = Math.max(leftLabel, rightLabel);

           return root.level;

   }

    

   public static void remNodes(Node c, Node p, int k){

       if(c == null) return;

       Node parent = p;

       Node cur = c;

       if(cur.level < k){

           if(parent!=null){

               if(parent.left == cur) parent.left = null;

               else{

                   parent.right = null;

               }

           }else{

               cur = null;

           }

       }else{

           remNodes(cur.left, cur, k);

           remNodes(cur.right, cur, k);

       }

   }

GeeksforGeeks - Remove nodes on root to leaf paths of length < K