Categories
Algorithms Computer Science

Determine max and min root leaf path in a Binary Search Tree (BST)

Let’s view an algorithm that manage to find the minimum and the maximum root-leaf path in a binary search tree. I used three stacks in this algorithm, one is temporary and the other will be filled with the results. Note that if we change:

  • i > maxSeq.size() with i >= maxSeq.size() we get the longest root-leaf path from the right instead of from the left
  • i < minSeq.size() with i <= minSeq.size() we get the shortest root-leaf path from the left instead of from the right
/**
 * Find the longest root-leaf path
 * 
 * @param t A BST tree
 * @param depth Initially set to 0
 * @param tempSeq Empty stack
 * @param minSeq Empty stack
 * @param maxSeq Empty stack
 */
public void maxMinPath(BSTNode t, int depth, Stack tempSeq, Stack minSeq, Stack maxSeq){
  tempSeq.push(t);
  if(t.hasLeft()) maxMinPath(t.left(), depth + 1, tempSeq, minSeq, maxSeq);
  if(t.hasRight()) maxMinPath(t.right(), depth + 1, tempSeq, minSeq, maxSeq);
  if(t.isLeaf()){
    if(i > maxSeq.size()) maxSeq = tempSeq.clone();
    if(minSeq.size() == 0 || i <= minSeq.size()) minSeq = tempSeq.clone();
  }
  tempSeq.pop();
}