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:

1. 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.
2. 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.

Answer 2

This is in C++, but it is so simple you can convert it easily. Just change min to max to get the maximum tree depth.

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

Just to explain what this is doing, it is counting from the leaf node (it returns 0 when it finds a leaf) and counts up back to the root. Doing this for the left and right hand sides of the tree and taking the minimum will give you the shortest path.

Answer 3

Breadth first search is exactly optimal in terms of the number of vertices visited. You have to visit every one of the vertices you'd visit in a breadth first search just in order to prove you have the closest leaf!

However, if you have a mandate to use recursion, Mike Thompson's approach is almost the right one to use -- and is slightly simpler.

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf