# Lowest Common Ancestor

## 236 LCA - given 2 nodes and root in Binary tree

*   Time O(n), space O(h)

    ```java
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
     // 碰到node1 or node2 就返回
      if(root == null || root == node1 || root == node2){
          return root;
      }

      TreeNode left = lowestCommonAncestor(root.left, node1, node2); 
      TreeNode right = lowestCommonAncestor(root.right, node1, node2);

      if( left != null && right != null){
          return root;
      }
      if(left != null){
          return left;
      }
      if(right != null){
          return right;
      }
      return null;
    }
    ```

## LCA - given 2 nodes with parent pointer in same binary tree

* Get depths of each nodes, make deeper node to the same level of another
* Time O(h), Space O(1)

```java
public static BinaryTree<Integer> LCA(TreeNode node0, TreeNode node1) {
  int depth_0 = depthGetter(node0), depth_1 = depthGetter(node1);

  // adjust node0 to make it deeper than node1
  if(depth_1 > depth_0){
    BinaryTree<Integer> tmp = node0;
    node0 = node1;
    node1 = tmp;
  }

  int diff = Math.abs(depth_0 - depth_1);

  while( diff-- > 0){
    node0 = node0.parent;
  }

  while(node0 != node1){
    node0 = node0.parent;
    node1 = node1.parent;
  }

  return node0;
}
```

## LCA - given 2 nodes with parent pointer, optimize for close ancestor

* Use Hashtable
* Time and Space O(D0 + D1)

```java
public static BinaryTree<Integer> LCA(TreeNode node0, TreeNode node1) {
  Set<BinaryTree<Integer>> s = new HashSet<>();
  while(node0 != null || node1 != null){
    if(node0 != null){
      if (!s.add(node0)){
        return node0;
      }
      node0 = node0.parent;
    }
    if(node1 != null){
      if (!s.add(node1)){
        return node1;
      }
      node1 = node1.parent;
    }
  }
  return null;
}
```

## 235 LCA with BST

* Worst case O(h)
*   Keep search the root in range \[node0, node1]

    ```java
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if(p.val > q.val){
          TreeNode tmp = p;
          p = q;
          q = tmp;
      }
      while(root.val < p.val || root.val > q.val){
          while(root.val < p.val) root = root.right;
          while(root.val > q.val) root = root.left;
      }
      return root;
    }
    ```

## 1123. Lowest Common Ancestor of Deepest Leaves

Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.

```python
class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def helper(node):
            if not node:
                return 0, None
            d1, t1 = helper(node.left)
            d2, t2 = helper(node.right)
            
            if d1 > d2: return d1+1, t1
            elif d1 < d2: return d2+1, t2
            else: return d1+1, node
            
        return helper(root)[1]
```
