Shortest path to leaf in Binary Search Tree

Question

I'm using recursion to find the shortest path in a BST(Binary Search Tree) and the shortest path should be the first childless leaf that is found. Whenever I return it gives me back the root. I've tried many various ways and I either keep getting the root back for a nullPointerException. Here is what I have

     public int minPath(){
     if(isEmpty()){
         return -1;
     }
     else{
         return findMin(root);
     }
 }

 private int findMin(IntegerTreeNode tNode){
     if((tNode.left != null) && (tNode.right != null)){
         findMin(tNode.left);
         findMin(tNode.right);
     }
     return tNode.item;
 }

I think what is happening is that it is returning the start of the stack, so how would I return the first childless leaf node?

Alejandro Alejandro · Accepted Answer · 2014-04-28T02:19:10

You can use Breadth-First-Search to solve this issue, since it will find the shortest path to a specified destination with unweighted edges. Since this is a BST, there should be no weighted edges, so BFS would be your algorithm of choice here.

Here is a wonderful presentation and pseudocode follow up of the algorithm:

BFS Tutorial

Your goal state will just be a node that doesn't have any children, hence a leaf node. Since BFS will find you the shortest path to this goal, this algorithm will return the first leaf node.

Shortest path to leaf in Binary Search Tree

2 Answers