Remove all nodes in a binary tree which don’t lie in path

In previous posts we learned how to print paths with given sum and print all paths in binary search tree. Today’s problem is to delete all nodes which don’t lie on paths with given sum.

This problem involves two subproblems, one is to find all paths of given sum and second is to remove nodes from tree.

Formally speaking, problem goes like : given a binary tree, defining a term “complete path sum” as, sum of values of nodes lying in a path from root to the leaf; now given a value ‘K’, find the k-heavy path and prune binary tree i.e. remove nodes which don’t lie on those paths.

For example, in below tree, if K is given as 65,

remove nodes which don't lie on path

 

resultant tree will look like: 30, 20 and 15

To understand how paths of a given sum are detected in binary search tree, please go through Print paths with given sum in BST.  All we have to do is prune all nodes which are not on these paths.

One way is to first get all nodes which are not part of any path and then one by one delete those nodes.

It requires two traversals of tree and as well as space to save all paths.  If node can be deleted while calculating paths will save extra traversal ass well the space as path need not be stored anymore.

When is it confirmed that path we are following is not a path with given sum? At leaf node, right?
If a leaf node does not satisfy path condition, it can be deleted.

Now what happens to parent node of leaf node we just deleted? That cannot be deleted as there may be other subtrees of parent node which lead to a path with given sum. For each node, deletion is dependent on what comes from its subtrees.

Well, solution depends on solutions to subproblem, classic case for recursion? What would be base case? If leaf node is not part of path of given sum, delete it and return false indication to parent node. If it is part of path with given sum, return true indication to parent node.

At parent node, there are two possible conditions:
1. Both left subtree and right subtree return false
Parent has to be deleted as there is no possible path from this node. Also, return false indication to parent of current node.
2. Any one subtree returns false
Then current node cannot be deleted, but we have to appropriately set right or left subtree as NULL.

As we are visiting every node in tree, complexity would be O(N).

  • Pingback: Amazon interview experience 2 | Algorithms and Me()

  • Saurabh Tyagi

    i have done it …. in N^2 complexity and having much lesser memory….i have ran it on my test case … hope it will run for u too…. written smaller code 🙂

    #include

    using namespace std;

    #define TreeNode node

    struct node

    {

    int val;

    struct node* left;

    struct node* right;

    };

    void del(TreeNode **child, TreeNode **par) {

    if(child == NULL) return;

    if((*par)->left == (*child)) {

    (*par)->left = NULL;

    } else {

    (*par)->right = NULL;

    }

    free(*(child));

    }

    int req = 21;

    void get_ans(TreeNode **root, TreeNode **par, int sum) {

    if((*root) == NULL) return;

    if((*root)->left == NULL && (*root)->right == NULL) {

    cout<val)<val))) {

    del( root, par);

    //get_ans(&((*root)->left), (root), sum + (*root)->val)

    }

    return;

    }

    if((*root) != NULL)

    get_ans(&((*root)->left), (root), sum + (*root)->val);

    if((*root) != NULL)

    get_ans(&((*root)->right), (root), sum + (*root)->val);

    //return;

    }

    void traverse(TreeNode **root) {

    if(*root == NULL) return;

    cout<val<left);

    traverse(&(*root)->right);

    return;

    }

    void isValidBST(TreeNode** root) {

    TreeNode *par = NULL;

    TreeNode *ret = (*root);

    get_ans(root, &par, 0);

    traverse(root);

    }

    struct node* newnode(int data)

    {

    struct node* node = (struct node*)

    malloc(sizeof(struct node));

    node->val = data;

    node->left = NULL;

    node->right = NULL;

    return(node);

    }

    int main()

    {

    /* Constructed binary tree is

    10

    /

    8 2

    / /

    3 5 2

    */

    struct node *root = newnode(10);

    root->left = newnode(8);

    root->right = newnode(2);

    root->left->left = newnode(3);

    root->left->right = newnode(5);

    root->right->left = newnode(2);

    isValidBST( &root);

    return 0;

    }

    • http://algorithmsandme.in/ Jitendra Sangar

      Cool thanks, Can you please send a ideone link of code, so that I can mention it in post with due credits!

      • Saurabh Tyagi

        yes sure i can …. but there is one thing i am unable to guess abt the code …. that when we delete the root … it will no longer be equivalent to NULL.. i,e no memory space left for root in that case what will we use to compare with root….except this the code run extremely fine…. well i have managed that condition in a condition … hope it will help

        http://ideone.com/PkiFq6

      • Saurabh Tyagi
  • Saurabh Tyagi

    yes sure i can …. this the code run extremely fine.. case for root is managed seperately … hope it will help

    http://ideone.com/PkiFq6