Paths with given sum in binary search tree
In last post, we discussed how to print all paths of a tree. Today let’s discuss another problem which can be used with same method as print all paths in tree with slight various. Problem at hand is to print path with given sum in binary search tree. For example, in given tree below, path with sum 114 is 30,40,45
Basic algorithms remains same as to print paths in a tree. Extra thing to be done is to keep track of sum of all nodes in path leading to current node. At each node, check if sum of all nodes in path is equal to given number, if yes, print the path. If sum of all nodes at currentNode is greater than sum, then just abandon the path as there is no way that path be the one we are looking for.
Paths with given sum in BST
1. Start from root, call it currentNode. 2. Subtract currentNode value from given sum, call it subSum 3. If sumSum is zero and node is leaf, print the path. 4. Check if subSum is less than zero, if yes, break 5. Else, 5.1 Check all path in left subtree of currentNode with sum as subSum 5.2 Check all paths in right subtree of currentNode with sum as subSum
This algorithm can easily be implemented using recursion. Pass current sum required with each successive node in path. And of course, book-keeping to print the path as we did with printing all paths of a tree.
Path with given sum implementation
Since we are traversing each node at least once, complexity of algorithm to print paths with given sum in binary search tree is O(N).
There is simpler version of this problem : Find if binary search tree contains path with given sum. In this problem, all what is ask is yes or no. No book keeping required.
At each node, subtract node value from sum required, and check if there is path on left or right subtree with reduced sum. Of yes, return yes, if not, then return no. This is classic case of recursion.
Complexity of implementation of to find if there is a path of given sum in binary search tree also is O(N).
Please share if there is something is wrong or missing. We would love to hear what you have to say.