Lowest Common Ancestor

235. Lowest Common Ancestor of a Binary Search Tree

充分利用BST的条件，查找值的时候只需要判读值就可以确定方向，O(h)的时间！！

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root

        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

236. Lowest Common Ancestor of a Binary Tree

“The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

Case1 if a is NOT the ancestor of b （a和b不直接隶属）
- 1 if left subtree returns None and right subtree returns None, return None
- 2 if left subtree AND right subtree return NOT NULL, return c
- 3 either left or right returns NOT null, return not null
Case2 if a is the ancestor of b (a和b直接隶属)
- same thing

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        # 1 Base case : root is q or p 
        if not root or root is q or root is p:
            return root

        # 2 Recursion : ask value from left and right subtree
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        # Case: return c
        if left and right:
            return root

        return left if left else right

Follow up 1 Not Exist

What if the node p or q is NOT in the tree ?
- case1: if return c, no worries! a and b are in the tree
- case2: if return None, both a and b not in the tree
- case3: if sol == p or sol == q p和q直接隶属 FindNode in B or A

    sol = LowestCommonAncestor(root, p, q)
    if sol is None:
        return None
    elif sol != p and sol != q:
        return sol
    else: # a, b 直接隶属
        return LowestCommonAncestor(sol, q, q) if sol == p else LowestCommonAncestor(sol, p, p)

Follow up 2 Parent Node

What if we have parent pointers ?
Method1:
- step1. keep looking up from a and b, to find height(a) and height(b)
- step2. move the one with larger height value by abs(height(a)-height(b))
- step3. move a and b together one step by one step until a == b
Method2: HashSet
- => interaction of two linked list

Follow up 3 k Nodes(No parent pointers)

General Idea to solve k-something ...

Method1: Binary Reduction
- eg. Merge Sort
- Call how many times of LCS(nodea, nodeb)? O(kn)
Method2: Iterative
- 12 -> 3, 13 -> 4, 14 -> 5 ...
- Call how many times of LCS(nodea, nodeb)? O(kn)
Method3: k way all together O(n)

class Solution(object):
    def lowestCommonAncestor(self, root, nodes):
        if not root or root in nodes:
            return root

        left = self.lowestCommonAncestor(root.left, nodes)
        right = self.lowestCommonAncestor(root.right, nodes)

        if left and right:
            return root

        return left if left else right

Follow up 4 k-nary Tree

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x 
        self.children = []

Follow up 5 k node in k-nary tree

Combine 3 & 4

Follow up 6 very large tree

LCA for two nodes a and b in a very large tree that contains billions of nodes, given 10000 machies.(32 machines)

Mapper: 1 job -> distribute to 10000 machines.
Reducer: collect results from each mapper (machines) to do aggregation/post-processing

Solution Map-reduce Assume we hace 32 machines 2 ^ 5 = 32, so we have 32 nodes in level 5.

Case 1: both nodes a and b are within top 5 layers (we can run BFS1 within top 5 layers) Call LCA(root, a, b, level_limit = 5)
Case 2: either node a or node b is within top 5 layers.
- Assume a is on top 5 layers, Call Find(M1, b), Find(M2, b), ..., Find(M32, b)
- Say, M7 return s that I found b in my sub-tree. Call LCA(root, a, M7, level_limit = 5)
Case 3: neither node a nor node b is within top 5 layers.
- Call LCA(M1, a, b), LCA(M2, a, b), ..., LCA(M32, a, b)
- Case3.1 a and b are in different machines.
  - In this case, there must be exactly two machines that find non-null
  - Say they're M3, M7, Call LCA(root, M3, M7, level_limit=5)
- Case3.2 a and b are in the same machine.
  - In this case, ONLY ONE machine returns non null
  - Case3.2.1 if it returns a or b: one node is the ancestor of the other node
  - Case3.2.2 if it returns c: a and b are both in the tree and c is the LCA

LCA