Shortest path in Binary Search Tree

Introduction

Another interview question for the most interesting data structure called BST (Binary Search Tree). To know more about BSTs check my previous post.

Problem Statement : Given a Binary Search Tree, keyed on positive integers. The task is to find the Shortest path in Binary Search Tree which adds up to the number K. If no such path exists, return a message accordingly.

Understanding the problem

A node in a binary search tree always has a higher key at its right child compared to its left child. There are many path running from the roots to the leaves. When we add up the key values along a path, it will sum up to some number NUM1. We need to find such a path where NUM1 is equal to K. Point worth noting is that, we might have many paths summing up to K. We need to return the shortest of them all. If there are multiple paths of the same length satisfying our condition then return any.

Here is a diagrammatic representation of our problem statement.
Shortest path in Binary Search Tree

The big idea

Hmmm.. Let us see. I have a number K and I want to get the smallest possible set of numbers from given numbers which add up to K. What would that be?

A concrete example would be to find the path which adds up to 72. We have two options as below:
The path 11, 17, 23, 21 and the path 11, 17, 13, 15, 16. As per the problem definition, we are interested in the path 11, 17, 23, 21.

Its certain that if we add up bigger numbers then we can get the sum with a smaller set compared to adding smaller numbers.

For e.g.: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 is the set of numbers available to us. I need a sum 18, then it is always lesser numbers required if I add up 8 and 10 compared to adding up 6, 5, 4, and 3.

What does this mean and why am I telling all this?

Just wanted to point out that the heavier numbers will lie on the right hand side of the Binary Search Tree. Which precisely means that we need to start evaluating the right children first and possible break out early in case we fin a path summing up to K. As the shorter paths with value K can lie on the right of the tree, if we do not find one we gradually shift to the paths at the left an evaluate them.

The solution requires the path traversals in a tree which is mentioned in detail in one of my previous posts for Finding All Paths in a Binary Tree.

Source Code

You can of course download the complete source code from the Github link for Techieme. Here is the important part of the code.

Analysis

A simple analysis would suggest that the running time of this algorithm in the worst case would require to visit each node once. Which means it would be O(N).

The space required is to store a path, and the longest path would not be more than the height of the tree. In case the tree is fairly balance the space used would be O(logN) where N is the number of nodes. If the tree is ridiculously skewed, you might end up using O(N) space for the path and O(logN) space for the recursion stack.

Conclusion

If you notice, this is just the same code as the one we use to find all the paths in a binary tree. Just slightly tweaked. This is a recursive solution and we can solve this problem using an iterative solution as well. But no matter which, this solution will always need a routing which knows how to find a path.

Which means, if we can plugin a different iterative method for path traversal, we will end up with a complete iterative solution. However, the iterative solution will need auxiliary space to store the parent, as one node can branch out into two more and we may require to evaluate both. A stack would be advisable for iterative solution. Will post the iterative solution soon.

Also, this problem statement can be tweaked to find the longest path in the tree and for that we would need to reorder the recursion step, to evaluate the left sub tree first.

Don’t forget to subscribe to TechieMe to get updates on latest posts.