how to find the horizontal distance between two nodes at the same level in a binary tree?

Question

Given a binary tree: Binary tree of height 3

I want to find the horizontal distance between two nodes at the same level also counting the nodes that are not there in between while not counting the nodes themselves, Say in

          f
      /         \
     g           h      
    /  \        /  \        
  a                d    

in between the nodes a and d there is a horizontal distance of 2.

Edit:

Please see distance between a to d is calculated on the same level not including the parent or child nodes of either a or d but only the missing nodes at the same level. so distance between a to d would be a>(x>y)>d where in x and y are the missing child nodes of node g and h respectively. Hence not counting the target nodes a and d there'll be a horizontal distance of 2

Answer 1

Think of it this way:

      a
    /   \
   b      c
  /  \   / \
 e    f g   h

Now, you want to determine horizontal distance between nodes at the same level. Eg: f and g. Here is a step by step approach:

1. Perform a level order traversal of the binary tree and store the values in an array.
2. This results in an array with its elements as node values.
3. Traverse the array elements. When you encounter f (starting node), set counter to 0.
4. Keep traversing the array and check that:
   1. If the g (end node) is encountered, then stop traversing.
   2. If the counter has been set, and the end node is not encountered, then update the value of the counter by 1.
5. Finally, print the value of the counter.

Update: As pointed out by anand_v.singh, if the tree might not be completely filled at all levels, then it can produce wrong results.
To overcome this problem, an additional parameter called tree_height will be determined. Suppose, the height of the tree was 3, then the array will contain at most 2^tree_height -1 elements, all initialized to a value that is not equal to the value of any tree nodes. Now, you can use something like array representation of binary heap, to place node values into the array, at their respective indices. Then follow the above-mentioned procedure to obtain the results.