Find distance between two nodes in a binary tree

Problem

Find the distance between two nodes in a binary tree. Every node of the binary tree has left pointer, right pointer and value. There is no parent pointer given in the nodes. Given two nodes or node values of such a binary tree and root of the tree given, find the distance between the given nodes.

Solution

We will first find out the path of the two nodes from root using recursive path finding algorithm. Now we will traverse simultaneously along the two paths till we find a mismatch. Then we know the size of the two paths, so we can easily calculate the distance by the formula, length of path1 + length of path2 - 2*length of the common part.

Code

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeDistanceBetweenNodes
{

 /**
  * @param args
  */
 public static void main(String[] args)
 {
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  Node f = new Node(6);
  Node g = new Node(7);
  Node h = new Node(8);
  a.left = b;
  a.right = c;
  b.left = d;
  c.left = e;
  c.right = f;
  f.left = g;
  f.right = h;

  int distance = findDistance(a, 2, 7);
  System.out.println(distance);

 }

 private static int findDistance(Node root, int val1, int val2)
 {
  List < node > path1 = new ArrayList < node >();
  List < node > path2 = new ArrayList < node >();
  findPath(root, val1, path1);
  findPath(root, val2, path2);
  if (path1.size() == 0 || path2.size() == 0)
   return -1;
  int index = 0;
  for (; index < path1.size(); ++index)
  {
   if (path1.get(index) != path2.get(index))
    break;
  }
  return path1.size() + path2.size() - 2 * index;
 }

 private static boolean findPath(Node root, int value, List < node > path)
 {
  if (root == null)
   return false;
  path.add(root);
  if (root.value == value)
  {
   return true;
  }
  if (findPath(root.left, value, path)
    || findPath(root.right, value, path))
   return true;
  path.remove(root);
  return false;
 }

 static class Node
 {
  Node left;
  Node right;
  int value;

  public Node(int value)
  {
   this.value = value;
  }
 }
}