views:

1147

answers:

3

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!

+11  A: 

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.

Brian R. Bondy
Your pseudocode only finds the first potential shortest path. There may be more than one path at that level which has no children. This may or may not matter.If it does, you have to mark the depth in the queue, so you can tell if you've processed an entire row.
Chris
Agreed, I almost wrote this but wanted to keep it more simple. Thanks for the comment on the topic.
Brian R. Bondy
As you mentioned you would put some kind of marker in the queue or on the last node of a certain depth of the tree. Then you would finish all items in the queue at that depth.
Brian R. Bondy
A leaf node might be one of the base cases, but you need to consider the null case as well. Unfortunately I have the basic concept down, but am getting slightly wrong answers here for the shortest case, especially in cases where only a left or a right tree is present, and not the other.
Sev
It doesn't matter if there is no left or right subtree. If there's only a left and no right for example, then only add the left to the queue.
Brian R. Bondy
A: 

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.

Mike Thompson
I already tried this method, and it is problematic in some cases...I'm also confused why.
Sev
problematic how?
1800 INFORMATION
Insert the following in a BST and try it, gives you 1 instead of the real answer 4 (or 5, depending on what you consider root to be.insert dinsert sinsert finsert eninsert noninsert ecinsert nop
Sev
You who the what now?
1800 INFORMATION
Although this returns the tree depth, it does not do it in the most efficient way. The reason it is not efficient is because the entire tree needs to be searched.
Brian R. Bondy
A: 

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
Captain Segfault