Algorithms and Me: Binary Search Tree: Prune nodes

Find the k-heavy path and prune the binary tree i.e. prune/delete nodes for which complete path sum is not equal to k.

At parent node, there are three possible conditions:

1. Both left sub tree and right sub tree return false : 

The current node is to be deleted as there is no possible path from this node.

2. Both left sub tree and right sub tree return true :

Then current node is to be maintained.

3. Any one sub tree returns false :

Then we have to maintain the current node, but we have to appropriately set right or left sub tree as NULL.

int prune_path(Node * node, int sum, Queue **path){

  int subSum =  sum - node->value;

  /* To check if left tree or right sub tree contributes to total sum  */

  int left_val = false, right_val = false;

  /* Enqueue the node in queue */

   enqueue(path, node);

  /*Check if node is leaf node */

    int isLeaf = node->left == NULL && node->right == NULL;

  /* If node is leaf node and it is part of path with sum  = given sum 

    Print the path and remove it from the list. 

    Also return true to parent node so tha parent node is not deleted */

    if(isLeaf && subSum ==0){

        printQueue(*path);

        printf("\n");

        removeFromList(*path);

        return true;

   }

   /* If node is leaf and it not part of path with sum equals

      to given sum

      Remove from the queue.

      Return false to parent node */

    else if(isLeaf && subSum != 0){

        removeFromList(*path);

        free(node);

        return false;

    }

   /* If node is not leaf and there is left child  Traverse to 

      left subtree*/

    if(node->left)

        left_val = prune_path(node->left, subSum, path);

   /* If node is not leaf and there is right child  Traverse to 

      right subtree*/

      if(node->right)

        right_val = prune_path(node->right, subSum, path)l

   /* This is crux of algo.

   1. If both left sub tree and right sub tree cannot lead to 

      path with given sum, delete the node 

   2. If any one sub tree can lead to path with sum equal to given sum,

      do not delete the node 

   3. If both sub trees can lead to path , do not do anything */

 

   if(left_val == false && right_val == false){

        removeFromList(*path);

        free(node);

        return false;

    }

    if(left_val == true && right_val == true){

        removeFromList(*path);

        return true;

    }

    /* Mark the false branch as NULL */

    else if(left_val == true){

        node->right = NULL;

    }

    else if(right_val == true){

        node->left = NULL;

    }

    removeFromList(*path);

    return true ;

}

Read full article from Algorithms and Me: Binary Search Tree: Prune nodes