4.2 LCA II

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

Assumption: Given two nodes are not guaranteed in the tree

Input: TreeNodeP one, TreeNodeP two

Output: TreeNodeP a LCA if exists

Solution:

1. Find the depth of both nodes by moving up from the node to root

If roots are different, meaning not in the same tree, return null

2. Move up the deeper node to match the level of the lower one

3. Move up both nodes together. When they meet, the node is the LCA

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;
  }
}

class Result {
  public TreeNodeP node;
  public int count;
  public Result(TreeNodeP node, int count) {
    this.node = node;
    this.count = count;
  }
}

public TreeNodeP LCA(TreeNodeP one, TreeNodeP two) {
  if (one == null || two == null) { return null; }
  if (one == two) { return one; }
  
  // Get root and depth of both nodes  
  Result resOne = getDepth(one);
  Result resTwo = getDepth(two);
  int depthOne = resOne.count;
  int depthTwo = resTwo.count;

  if (resOne.node != resTwo.node) { return null; }
  if (depthOne >= depthTwo) {
    return helper(one, two, depthOne - depthTwo);
  } else {
    return helper(two, one, depthTwo - depthOne);
  }
}

private Result getDepth(TreeNodeP node) {
  int count = 1;
  while (node.parent != null) {
    node = node.parent;
    count++;
  }
  return new Result(node, count);
}

private TreeNodeP helper(TreeNodeP lower, TreeNode P higher, int depthDiff) {
  // Move up lower node
  while (depthDiff > 0) {
    lower = lower.parent;
    depthDiff--;
  }
  // Move up both nodes
  while (lower != higher) {
    lower = lower.parent;
    higher = higher.parent;
  }
  return lower;
}