LeastCommonAncestor

// without parent
public Node findCommonAncestor(Node root, Node n1, Node n2) {
  if (root == null) {
    return null;
  } else if (root == n1 || root == n2) {
    return root;
  } else {
    Node leftAnc = findCommonAncestor(root.left, n1, n2);
    Node rightAnc = findCommonAncestor(root.right, n1, n2);
    
    if (n1 != null && n2 != null) {
      return root;
    } else if (leftAnc == null) {
      return rightAnc;
    } else {
      return leftAnc;
    }
  }
}

// with parent 
public Node findCommonAncestor(Node root, Node n1, Node n2) {
  int depth1 = depth(n1);
  int depth2 = depth(n2);
  
  if (depth1 > depth2) {
    n1 = hopToParent(n1, depth1 - depth2);
  } else if (depth2 > depth1) {
    n2 = hopToParent(n2, depth2 - depth1);
  }
  
  while (n1 != n2) {
    n1 = n1.parent;
    n2 = n2.parent;
  }
  return n1;
}

private int depth(Node d) {
  int count = 0;
  while (d != null) {
    count++;
    d = d.parent;
  }
  return count;
}

private Node hopToParent(Node d, int k) {
  for (int i = 0; i < k; i++) {
    d = d.parent;
  }
  return d;
}