Tree - Lowest Common Ancestor

Algorithms
tree
Catalogue
  1. 1. 235. Lowest Common Ancestor of a Binary Search Tree
  2. 2. 236. Lowest Common Ancestor of a Binary Tree
  3. 3. Follow up 1 Not Exist
  4. 4. Follow up 2 Parent Pointer
  5. 5. Follow up 3 k Nodes (No parent pointers)
  6. 6. Follow up 4 k-nary Tree
  7. 7. Follow up 5 k node in k-nary tree
  8. 8. Follow up 6 very large tree

235. Lowest Common Ancestor of a Binary Search Tree

  • Use the Definition of BST !!!
1
2
3
4
5
6
7
8
9
10
11
12
# Time : 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
  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 (same thing)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 ?
  1. case1: if return c, no worries! a and b are in the tree
  2. case2: if return None, both a and b not in the tree
  3. case3: if sol == p or sol == q FindNode in B or A
1
2
3
4
5
6
7
sol = LowestCommonAncestor(root, p, q)
if sol is None:
    return None
elif sol != p and sol != q:
    return sol
else:
    return LowestCommonAncestor(sol, q, q) if sol == p else LowestCommonAncestor(sol, p, p)

Follow up 2 Parent Pointer

What if we have parent pointers ?

  • Method1:
  1. step1. keep looking up from a and b, to find height(a) and height(b)
  2. step2. move the one with larger height value by abs(height(a)-height(b))
  3. 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 …

  1. Method1: Binary Reduction
    • eg. Merge Sort
    • Call how many times of LCA(nodea, nodeb)? O(kn)
  2. Method2: Iterative
    • 12 -> 3, 13 -> 4, 14 -> 5 …
    • Call how many times of LCA(nodea, nodeb)? O(kn)
  3. Method3: k way all together O(n)
1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
# 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.

  1. 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)

  2. 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)
  1. 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
Share