Challenge

Given a binary Tree, find the lowest common ancestor of two nodes.

Example: LCA(4,9) => 7 LCA()

         3
        / \
       7   1
      / \   \
     4   9   2

Solution 1 - Recursion

class Solution:
    
    def helper(self, root, nodes):
        
        if not root:
            return None
        
        if root in nodes:
            return root
        left = self.helper(root.left, nodes)
        right = self.helper(root.right,nodes)
        if left and right:
            return root
        if left and right is None:
            return left
        if right and left is None:
            return right
        
        
    
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
        return self.helper(root, nodes)

Solution 2 - Iterative

Another strategy is for each node keep in memory his parent.
Then you can go up the ancestry tree and find the lowest they share.

E.g searching the common ancestors of multiple nodes.

class Solution:
    
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
        if len(nodes)==1:
            return nodes[0]
        ancestors = {}
        stack = [root]
        ancestors[root.val] = None
        ids = {}
        while stack:
            node = stack.pop(0)
            ids[node.val] = node
            if node.left:
                stack.append(node.left)
                ancestors[node.left] = node
            if node.right:
                stack.append(node.right)
                ancestors[node.right] = node
        
        # find paths
        path = defaultdict(int)
        s = defaultdict(int)
        for n in nodes:
            parent = n
            
            while parent:
                path[parent.val] += 1 
                s[path[parent.val]] =   parent.val
                if parent not in ancestors:
                    break
                parent = ancestors[parent]
            

        for k, v in path.items():
            if v == len(nodes):
                return ids[k]
        
            
        return