Lowest Common Ancestor II

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

Question

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

The node has an extra attribute parent which point to the father of itself. The root’s parent is null.

Example:

Input：{4,3,7,#,#,5,6},3,5
Output：4
Explanation：
     4
     / \
    3   7
       / \
      5   6
LCA(3, 5) = 4

Input：{4,3,7,#,#,5,6},5,6
Output：7
Explanation：
      4
     / \
    3   7
       / \
      5   6
LCA(5, 6) = 7

Analyzation

Recursion

Two steps:

Firstly, find all the parent nodes for one of the two trees and put them into a set (avoid duplicate).

Secondly, traverse all the parent nodes from the other tree and the first-found node is the answer because it is from bottom to the top.

The Code

class Solution:
    """
    @param: root: The root of the tree
    @param: A: node in the tree
    @param: B: node in the tree
    @return: The lowest common ancestor of A and B
    """
    def lowestCommonAncestorII(self, root, A, B):
        # write your code here
        
        # get a set of parent nodes
        parent_set = set()
        
        # traverse all the parent nodes of A and put them into the parent set
        node = A
        while node is not None:
            parent_set.add(node)
            node = node.parent
        
        # find the first parent that is in the parent set and that is the final answer
        node = B
        while node is not None:
            if node in parent_set:
                return node
            node = node.parent
            
        return None

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).