Print paths in binary search tree
Path in a tree is list of nodes from root to leaf. There can be many paths in a tree, maximum length of a path can be N nodes in worst case, in average case it would be logN. Consider following tree:
Paths is above tree are :10,6,4
To traverse a path, we start at root. At every node we have two options, either we go left or we go right. We traverse left first till the we have covered all paths which are on the left side of the node, then we come back to node and traverse all paths which are on the right side. It is plain traversing of all nodes, only thing is we need to do is some book keeping so that we can print the path when we reach a leaf node.
Algorithm to print paths in binary tree
1. Start from root, add node to path
2. Traverse all paths in left sub tree
3. Traverse all paths in right sub tree
Since we are traversing each node at least once, complexity of this code is O(N).
Output of the code for following tree
|Input Binary search tree
Path : 30, 20, 10, 12,
Path : 30, 40, 37,
Path : 30, 40, 45,
Print all paths with a given sum in BST
Let’s consider a problem where we need to print only those paths which sums up to a given number.
Basic algorithms remains same only thing we add is to keep track of sum of nodes and before printing check if the sum of all nodes in path is equal to given number.
Algorithm to print paths with given sum
1. Start from root.
2. Subtract root value from given number, say it as subsum
3. Check all path in left sub tree for sum as subsum
4. Check all paths in right sub tree for sum as subsum
5. If subsum at leaf is zero, print the path
Since we are traversing each node at least once, complexity of algorithm to print paths with given sum is O(N). Following code implements another similar problem where we need to just find whether BST contains a path with given sum.
Driver program for all above functions is, change the function call 🙂
We have seen three versions of problem of printing paths in binary search tree and similar approach used for the solution.