Remove nodes on root to leaf paths of length < K | C ++ program to remove nodes on root to leaf paths of length < K ; New node of a tree ; Utility method that actually removes the nodes which are not on the pathLen >= k . This method can change the root as well . ; Base condition ; 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 . ; 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. ; Return root ; ; Method which calls the utitlity method to remove the short path nodes . ; Method to print the tree in inorder fashion . ; Driver method .
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * newNode ( int data ) { Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } Node * removeShortPathNodesUtil ( Node * root , int level , int k ) { if ( root == NULL ) return NULL ; root -> left = removeShortPathNodesUtil ( root -> left , level + 1 , k ) ; root -> right = removeShortPathNodesUtil ( root -> right , level + 1 , k ) ; if ( root -> left == NULL && root -> right == NULL && level < k ) { delete root ; return NULL ; } return root ; } Node * removeShortPathNodes ( Node * root , int k ) { int pathLen = 0 ; return removeShortPathNodesUtil ( root , 1 , k ) ; } void printInorder ( Node * root ) { if ( root ) { printInorder ( root -> left ) ; cout << root -> data << " ▁ " ; printInorder ( root -> right ) ; } } int main ( ) { int k = 4 ; Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> left -> left -> left = newNode ( 7 ) ; root -> right -> right = newNode ( 6 ) ; root -> right -> right -> left = newNode ( 8 ) ; cout << " Inorder ▁ Traversal ▁ of ▁ Original ▁ tree " << endl ; printInorder ( root ) ; cout << endl ; cout << " Inorder ▁ Traversal ▁ of ▁ Modified ▁ tree " << endl ; Node * res = removeShortPathNodes ( root , k ) ; printInorder ( res ) ; return 0 ; }