# 4.2 LCA II

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

&#x20;        If roots are different, meaning not in the same tree, return null

&#x20;   2\. Move up the deeper node to match the level of the lower one

&#x20;   3\. Move up both nodes together. When they meet, the node is the LCA

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