LeetCode 1650. Lowest Common Ancestor of a Binary Tree III

This question is one of the variations of the “Lowest Common Ancestor of a Binary Tree” problem and goes as follows:

Given two nodes of a binary tree nodeA and nodeB, return their lowest common ancestor (LCA). Each node has the following attributes: int val, Node left, Node right, int parent.

Method 1:

One way to solve this problem is to traverse from one of the nodes all the way up to the top, and save all the ancestors in a hash map. Afterwards, we will go from the other node to the top of the tree, and return the node if it’s already in the hash map. If so, we have found the lowest common ancestor.

def lowestCommonAncestor(self, a: 'Node', b: 'Node') -> 'Node':
    ancestors = set()
    
    while a is not None:
        ancestors.add(a)
        a = a.parent
        
    while b is not None:
        if b in ancestors:
            return b
        b = b.parent

Since we will go from nodeA to the root once and also from nodeB upwards once, the time complexity is O(N), N being the number of nodes in the tree. This is because the tree can be skewed if we’re out of luck.
And as we need to store the list of ancestors, the space complexity is also O(N).

Time: O(N), Space: O(N)

Method 2:

This method is a bit tricky and and most people won’t be able to come up with it in a short amount of time.

The idea is as follows: we will use 2 pointers (pointerA, pointerB) that go from nodeA and nodeB upwards respectively. Assume nodeA locates at a shallower level than nodeB, i.e. depth(nodeA) < depth(nodeB), pointerA will reach the top quicker than pointerB.

Suppose the difference in depth between nodeA and nodeB is diff, by the time pointerA reaches the top, pointerB will be diff levels behind. Now if pointerA resets its path and continues upwards from nodeB instead of nodeA, it will need diff steps to reach the level of nodeA, by which time pointerB has already caught up and will be at the same level of pointerA (pointerB restarts from nodeA after reaching the top).

Now the only thing to do is to compare pointerA and pointerB on the way up. If pointerA and pointerB points to the same node, we’ve found the lowest common ancestor.

def lowestCommonAncestor(self, a: 'Node', b: 'Node') -> 'Node':
    pointerA, pointerB = a, b
        
    while pointerA != pointerB:
        pointerA = pointerA.parent if pointerA else b
        pointerB = pointerB.parent if pointerA else a
            
    return pointerA

Since we don’t need extra space with this approach, the space complexity is O(1), while the time complexity stays the same.

Time: O(N), Space: O(1)

Hopefully, you have found this article useful.

If you like my stories, don’t forget to give them a clap 👏 .

Please follow me and share the article with your friends! Cheers! 😉