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

Yehudit

I think you should explain how you calculate that result. I'm not sure that there is a widely-accepted definition of horizontal distance in trees; my own calculation cae up with the answer 4. – Dreiser

I do not include the target nodes in the count – Yehudit

Are you calculating 2 as there is a place for right child of g and left child of h? – Parricide

The positions of the legs inside of a binary tree are arbitrary, unless there is some other rules given for the placement of them, then there are no way of knowing if they are beside each other or on either end. what @HighPerformanceMark was referencing when he gave it a distance of 4, he calculated the number of steps from a to d by going a->g->f->h->d or a total of 4 steps away. – Buckra

Hi. 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 – Yehudit

Why can't be the horizontal distance between the nodes equal to the height of the node in the tree - 1? – Naos

So the count 2 is because of the missing childs x and y? Also are the elements unique in the tree? – Temptress

@Naos your formula is true only for nodes at the extreme end of the tree – Temptress

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.

Naos

A couple of things can go wrong, In your array there will be no depth information, so a and c will show the distance of 1, also the OP wants to count empty nodes as well, so level order traversal need to be modified to account for that, overall I think there should also be a bit more quality to the question, it isn't exactly clear on how to handle cases like this. – Temptress

That's right! I am modifiying the answer to handle the cases, when the tree is a complete binary tree, filled at all levels. – Naos

I would do something like a list of lists, where each inner list is a level in the tree, but again the OP has to specify how he wants to handle such cases. – Temptress

Answer 2

This is one approach that might not be the best and optimal solution in terms of memory.

So suggestions/ improvements are welcome.

Algorithm-

• Traverse BT using a Breadth-First Search (Level order) approach.
• While traversing, consider blank spaces(where node isn’t present) as ‘-1’
• Insert BFS path elements in an array Find indices of 2 node elements to be found.
• Calculate distance using indexes.

Complexity- Time: O(N) Space: O(N)

Assumptions- Every node in BT has a unique value.

class Node {
  Node() {
    value = -1;
  }
  Node(int num) {
    value = num;
  }
  int value;
  Node left = null;
  Node right = null;
}

Declaring some required DS

static Queue<Node> queue = new LinkedList<Node>();
static ArrayList<Integer> list = new ArrayList<Integer>();
static Set<Integer> set = new HashSet<Integer>();

Then three functions

 static void convertBTToArray() {
    if (set.isEmpty())
      return;
 
    Node node = queue.poll();
 
    if (node != null) {
      list.add(node.value);
 
      if (node.value != -1)
        set.remove(node.value);
 
      if (node.left != null) {
        queue.add(node.left);
        set.add(node.left.value);
      } else
        queue.add(new Node());
      if (node.right != null) {
        queue.add(node.right);
        set.add(node.right.value);
      } else
        queue.add(new Node());
 
      convertBTToArray();
 
    } else
      return;
  }
 
 
  static void init(Node root) {
    // traverse in BFS fashion (level order) and convert to Array.
    Node rootCopy = root;
    if (rootCopy != null) {
      queue.add(rootCopy);
      set.add(rootCopy.value);
      convertBTToArray();
    }
  }
 
    // get distance between start and end values.
  static int getHorizontalDistance(int startValue, int endValue) {
    int startIndex = -1, endIndex = -1;
    for (int i = 0; i < list.size(); i++) {
      if (startIndex == -1)
        startIndex = list.get(i) == startValue ? i : -1;
 
      if (list.get(i) == endValue) {
        endIndex = i;
        break;
      }
    }
 
    // check if both numbers are from same level else return -1
    if (Math.floor(Math.log(startIndex + 1) / Math.log(2)) >= 0
      && Math.floor(Math.log(endIndex + 1) / Math.log(2)) >= 0)
      return (endIndex - startIndex - 1);
    else
      return -1;
  }

and finally the main method

public static void main(String...s) {
    // create your tree and enter elements here

    // -1 indicates that distance cant be found and hence invalid input.
    System.out.println("Dist(7,1): "+getHorizontalDistance(7, 1));
    
  }

Pedaiah

Answer 3

Find horizontal distance(hd1) of 'a' from 'f' i.e root and horizontal distance(hd2) of 'd' from 'f'.

Take hd of root=0. Then do hd2-hd1 to get the horizontal distance b/w given two nodes. Here hd1 would be negative since it's to the left of the root and hd2 would be positive since it's to the right of the root.

Function to calculate horizontal distance of a node would look like this.

int HD(Node* root, Node* node, int hd=0){
    if(!root) return INT_MIN;
    if(root==node) return hd;
    return max(HD(root->left, node, hd-1), HD(root->right, node, hd+1));
}

Now

hd1 = HD(root, nodeA)
hd2 = HD(root, nodeD)

hd2-hd1 will give 4 in your case.

Bagwell

Answer 4

Here is the code:

/**
* 
* @author satish hawalppagol
*
*/



public class BinaryTreeTest
{
    public int findDistance(Node root, int n1, int n2) 
    {

    int leftNodeToRootNode = Pathlength(root, n1, "leftNodeToRootNode") - 2;
    int rightNodeToRootNode = Pathlength(root, n2,"rightNodeToRootNode") - 2;
    int lcaData = findLCA(root, n1, n2).data;   //LCA->Lowest Common Ancestor
    int lcaDistance = Pathlength(root, lcaData,"lcaDistance") - 1;
    return (leftNodeToRootNode + rightNodeToRootNode) - 2 * lcaDistance;

    }

    public int Pathlength(Node root, int n1,String callingFrom) 
    {

    if (root != null) 
    {

        int x = 0;

        if("rightNodeToRootNode" == callingFrom)
        {

            if(root.left ==null && root.right ==null)
            {
                //do nothing
            }
            else if(root.left ==null || root.right ==null)
            {
                System.out.println("counting the position where the node is not 
                present is : "   +   root.data);
            }
            if ((root.data == n1) || (x = Pathlength(root.left, 
               n1,"rightNodeToRootNode")) > 0  || (x = Pathlength(root.right, 
               n1,"rightNodeToRootNode")) > 0) 
            {
                return x + 1;
            }
        }
        if("rightNodeToRootNode" != callingFrom )
        {

            if ((root.data == n1) || (x = Pathlength(root.left, 
            n1,"leftNodeToRootNode")) > 0  || (x = Pathlength(root.right, 
            n1,"leftNodeToRootNode")) > 0) 
            {
                return x + 1;
            }
        }

        return 0;
    }
    return 0;
}

public Node findLCA(Node root, int n1, int n2) 
{

    if (root != null)
    {

        if (root.data == n1 || root.data == n2) 
        {
            return root;
        }
        Node left = findLCA(root.left, n1, n2);
        Node right = findLCA(root.right, n1, n2);

        if (left != null && right != null)
        {
            return root;
        }
        if (left != null) 
        {
            return left;
        }
        if (right != null)
        {
            return right;
        }
    }
    return null;
}

public static void main(String[] args) throws java.lang.Exception 
{

    Node root = new Node(5);
    root.left = new Node(2);
    root.right = new Node(3);
    /*root.left.right = new Node(12);*/
    root.left.left = new Node(7);
    root.left.left.left = new Node(9);
    /*root.left.left.right = new Node(17);*/

    root.right.right = new Node(1);
    /*root.right.right.left = new Node(4);*/
    root.right.right.right = new Node(6);

    BinaryTreeTest binaryTreeTest = new BinaryTreeTest();
    System.out.println("Distance between 9 and 6 is : " + 
    binaryTreeTest.findDistance(root,9, 6));
    }

}

class Node 
{
int data;
Node left;
Node right;

    public Node(int data) 
    {
    this.data = data;
    this.left = null;
    this.right = null;
    }
}


///////////input/////////   
//          5          //   
//        /    \       //   
//       2     3       //   
//      / \      \     //   
//     7          1    //   
//    /  \       /  \  // 
//   9               6 // 
///////////input/////////   

counting the position where the node is not present is : 2
counting the position where the node is not present is : 7
counting the position where the node is not present is : 3
counting the position where the node is not present is : 1
Distance between 9 and 6 is : 4

Arjun

Welcome to Stack Overflow! While this code may solve the question, including an explanation of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. Please edit your answer to add explanations and give an indication of what limitations and assumptions apply. – Urga