Given two nodes in a binary tree (with parent pointer available), find their lowest common ancestor.

Assumptions

• There is parent pointer for the nodes in the binary tree

• The given two nodes are not guaranteed to be in the binary tree

Examples

        5

      /   \

     9     12

   /  \      \

  2    3      14

The lowest common ancestor of 2 and 14 is 5

The lowest common ancestor of 2 and 9 is 9

The lowest common ancestor of 2 and 8 is null (8 is not in the tree)

 

/**
 * public class TreeNodeP {
 *   public int key;
 *   public TreeNodeP left;
 *   public TreeNodeP right;
 *   public TreeNodeP parent;
 *   public TreeNodeP(int key, TreeNodeP parent) {
 *     this.key = key;
 *     this.parent = parent;
 *   }
 * }
 */
public class Solution {
  public TreeNodeP lowestCommonAncestor(TreeNodeP one, TreeNodeP two) {
    // Write your solution here.
    int aLen = getHeight(one);
    int bLen = getHeight(two);
    if (aLen >= bLen) {
      return getLCANode(aLen - bLen, one, two);
    } else {
      return getLCANode(bLen - aLen, two, one);
    }
  }

  private int getHeight(TreeNodeP node) {
    int len = 0;
    while (node != null) {
      node = node.parent;
      len += 1;
    }
    return len;
  }

  private TreeNodeP getLCANode(int diff, TreeNodeP node, TreeNodeP other) {
    while (diff > 0) {
      node = node.parent;
      diff -= 1;
    }
    while (node != other) {
      node = node.parent;
      other = other.parent;
    }
    return node;
  }
}