Least distance between two values in a large binary tree with duplicate values

Question

Given a binary tree that might contain duplicate values, you need to find minimum distance between two given values. Note that the binary tree can be large.

For example:

        5
      /   \
    1       7
   / \     / \
  4   3   8   2
 / \
1   2

The function should return 2 for (1 and 2 as input).
(If duplicates are not present, we can find LCA and then calculate the distance.)

I've written the following code but I couldn't handle cases when the values are present in different subtrees and in the below cases:

1. root = 1, root.left = 4, root.left.left = 3, root.left.right = 2, root.left.left.left = 1
2. root = 1, root.left = 4, root.left.left = 3, root.left.left.left = 1, root.left.left.right = 2

void dist(struct node* root,int& min,int n1,int n2,int pos1,int pos2,int level) {
    if(!root)
        return;
    if(root->data==n1){
        pos1 = level;
        if(pos2>=0)
            if(pos1-pos2 < min)
                min = pos1-pos2;
    }
    else if(root->data==n2){
        pos2 = level;
        if(pos1>=0)
            if(pos2-pos1 < min)
                min = pos2-pos1;
    }
    dist(root->left,min,n1,n2,pos1,pos2,level+1);
    dist(root->right,min,n1,n2,pos1,pos2,level+1);
}

I think at each node we can find if that node is the LCA of the values or not. If that node is LCA then find the distance and update min accordingly, but this would take O(n²).

Answer 1

Do a pre-order traversal of the tree (or any traversal should work).

During this process, simply keep track of the closest 1 and 2, and update the distance whenever you find a 2 and the closest 1 is closer than the closest distance so far, or vice versa.

Code (C++, untested first draft): (hardcoded 1 and 2 for simplicity)

int getLeastDistance(Node *n, int *distTo1, int *distTo2)
{
  if (n == NULL)
    return;

  int dist = LARGE_VALUE;

  // process current node
  if (n->data == 1)
  {
    dist = *distTo2;
    *distTo1 = 0;
  }
  else if (n->data == 2)
  {
    dist = *distTo1;
    *distTo2 = 0;
  }

  // go left
  int newDistTo1 = *distTo1 + 1,
      newDistTo2 = *distTo2 + 1;

  dist = min(dist, getLeastDistance(n->left, &newDistTo1, &newDistTo2));

  // update distances
  *distTo1 = min(*distTo1, newDistTo1 + 1);
  *distTo2 = min(*distTo2, newDistTo2 + 1);

  // go right
  newDistTo1 = *distTo1 + 1;
  newDistTo2 = *distTo2 + 1;

  dist = min(dist, getLeastDistance(n->right, &newDistTo1, &newDistTo2));
}

Caller:

Node root = ...;
int distTo1 = LARGE_VALUE, distTo2 = LARGE_VALUE;
int dist = getLeastDistance(&root, &distTo1, &distTo2);

Just be sure to make LARGE_VALUE far enough from the maximum value for int such that it won't overflow if incremented (-1 is probably safer, but it requires more complex code).