Path with given sum in binary search tree

In last post Paths in Binary Search Tree we discussed and solved problem to find all the paths in binary search tree. Next step is to find specific path with sum in binary search tree. Given a number K, find all paths with sum K in BST. For example if K  = 21, and given below BST, path will be [10,5,6].

path with given sum in binary search tree

Keep in mind, that there can be more than one paths with given sum. Confirm with interviewer what does he expects in implementation.

Path with given sum : Thoughts

We already know how to traverse all paths in binary search tree. All we need now is to qualify those paths if all nodes in path sum up to given number K.

Let’s figure our recursive nature of problem. At the root level, we are required to find path with sum K. As soon as we add root in path, remaining nodes in path needs to add up to K – root.value, in either left or right subtree. For example, in below tree,  at whole tree level, sum required is 21.

As we move down, that is root is added to path, sum required further is 11 from either left or right subtree. Problem is reduced to subproblem.

At this point, we cannot go forward with node(19), as sum required will reduced to negative. However, we can move down node(5) and problem is reduced to finding path with sum 6.

path with given sum

At this point, we have to find path with sum 6 in left and right subtree of node(5). On left subtree, add node(1) to path. Now problem reduces to finding path with sum 5 on right and left subtree of node(1). However, there are not subtrees of node(1). Hence, path [ 10,5,1 ] is not correct path.

On the other hand, after adding node(6) in path, sum required is 0 and also node(6) is a leaf node, hence path [10,5,6] is required path with given sum in binary search tree.

As we worked out example, we came up with some basic conditions for algorithm.

  1. If at any node in path, sum required becomes negative, do not go down the path.
  2. If sum required become zero, check if the last node added is leaf node. If yes, then add path to solution.
  3. If sum required is greater than zero, and node is leaf node, then that path is not with required sum.

Paths with given sum  : Implementation

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

void printPath(Node * node, int sum, int path[], int pathLen){
	
	if(!node)
		return;
	
	int subSum = sum - node->value;
	path[pathLen] = node->value;
	
	int isLeaf = !( node->left || node->right );
        if(isLeaf && subSum == 0){
        	printf(" Path with given sum is: " );
	        for(int i=0; i<=pathLen; i++)
               	     printf("%d, ", path[i]);
           	printf("\n");
        }  
        printPath(node->left, subSum, path, pathLen+1);
        printPath(node->right, subSum, path, pathLen+1);
        return ;
}

Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
  
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
  
  return newNode;
}

Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value > value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  int n = 0;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
  int path[100];
  printPath(root, 115, path, 0);
  
  return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    private void pathWithGivenPath(Node root, int sum, ArrayList<Node> path){
        if(root == null)
            return;

        if(sum < 0) return;

        int subSum = sum - root.value;
        path.add(root);

        boolean isLeaf = ( root.left == null && root.right == null );
        if(isLeaf && subSum == 0){
            path.forEach(node -> System.out.print(" " + node.value));
            System.out.println();
        }
        pathWithGivenPath(root.left, subSum, path);
        pathWithGivenPath(root.right, subSum, path);

        path.remove(path.size()-1);
    }

    public void printPathWithGivenPath(int sum){
        ArrayList<Node> path = new ArrayList<>();
        pathWithGivenPath(this.root, sum, path);
    }
}

Test class

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();

        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);

        binarySearchTree.printPathWithGivenPath(20);
    }
}

Complexity of algorithm to print all paths with given sum in binary search tree is O(n) as we will be scanning all nodes of BST at least once.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com