You are given two nodes of a Binary Tree. Find the minimum distance between two nodes. Root node is not given, Only Parent Pointer is given for each node. Given node1, node2, we have to find minimum distance between two nodes.

Example -

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

Input : Node1 = 1, Node2 = 3
Ouptut : 2 (As distance from 1 to 3 is 2)

Input :Node1= 2 Node2 = 6
Output = 3 (As distance from 2 to 6 is 3)

Optimal Time Complexity : O(n). You must be able to solve this in O(n)

Brute-Force:

I suggested a solution using vector (1-indexed). We can have two arrays, one each for node1 & node2 respectively. We can keep track of nodes visited from bottom to top using both arrays (i.e. will push the visited node into the array).

And once we find the same node, we can sum up the indexes of both arrays -1 (this 1 for common array, as it would be counted twice) to give the minimum distance between two nodes.

Sample tree class, which I wrote during Interview:

class BinaryTree{
BinaryTree* Parent;
int val;
};

Function :

int distancebetweentwoNodes(BinaryTree* node1, BinaryTree* node2){
}

Interviewer wanted to have look-up in O(1). I suggested using hashmap, but couldn't completely code this sucessfully, there were few bugs in the code.