Shortest Root to Leaf Path

Question

What is the easiest way, preferably using recursion, to find the shortest root-to-leaf path in a BST (Binary Search Tree). Java prefered, pseudocode okay.

Thanks!

Answer 1

General description:

Use a Breadth-first search (BFS) as opposed to a Depth-first search (DFS). Find the first node with no children.

Using a DFS you might get lucky on some input trees (but there is no way to know you got lucky so you still need to search the whole tree), but using the BFS method is much faster and you can find a solution without touching all nodes.

To find the root to leaf path, you could follow the first found childless node all the way back up to the root using the parent reference. If you have no parent reference stored in each node, you can keep track of the parent nodes as you recurse down. If you have your list in reverse order you could push it all on a stack and then pop it off.

Pseudo-code:

The problem is very simple; here is pseudo code to find the smallest length:

1. Put the root node on the queue.

Repeat while the queue is not empty, and no result was found:

2. Pull a node from the beginning of the queue and check if it has no children. If it has no children you are done you found the shortest path.
3. Otherwise push all the children (left, right) onto the queue.

Finding all shortest paths:

To find all shortest paths you can store the depth of the node along with node inside the queue. Then you would continue the algorithm for all nodes in the queue with the same depth.

Alternative:

If instead you decided to use a DFS, you would have to search the entire tree to find the shortest path. But this could be optimized by keeping a value for the shortest so far, and only checking the depth of future nodes up until you find a new shortest, or until you reach the shortest so far. The BFS is a much better solution though.