Determining the distance between pairs of nodes in a BST tree

Question

I want to write a psudo-code to find the distance between 2 nodes in a BST.

I have already implemented LCA function.

Here is my attempt:

findDistance(root,p,q){
  if(root==null) return -1;
  Node LCA = findLCA(root,p,q);
  d1=distance(p,LCA);
  d2=distance(q,LCA);
  return abs(d1-d2);
}

My only problem here is that I don't know how to compute the distance between a node to its LCA.

Any help will be amazing!

Thanks!

Answer 1

Finding the LCA is helpful, but you could determine the length of the path while determining the LCA.

I would first define a helper function which will give the path from the root to the given node. As the root is the only node without a parent, we don't actually need to provide the root to this function:

function getPath(p) {
    let path = [];
    // Walk up the tree and log each node
    for (let node = p; node != null; node = node.parent) {
        path.push(node);
    }
    // We want the root to be first element of path, and p to be the last:
    return path.reverse(); 
}

Now with this function we can collect the two paths for the two given nodes. Then we can ignore the common prefix in these two paths (the last common node is the LCA). The remaining lengths of the paths should be summed to get the final result:

function findDistance(p, q) {
    let path1 = getPath(p);
    let path2 = getPath(q);
    let len = min(path1.length, path2.length);
    // Find the index where the paths diverge
    let i = 0;
    while (i < len && path1[i] == path2[i]) {
        i++;
    }
    // LCA is at path1[i-1] == path2[i-1]
    // Subtract the nodes that the paths have in common (from both):
    return path1.length + path2.length - i*2;
}