[Top Interview 150] 236. Lowest Common Ancestor of a Binary Tree

Solution)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Base Case
        if not root or root == p or root == q:
            return root

        # Recursive Call
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)

        # If p and q are descendants of a certain node
        # return that node
        if l and r:
            return root
            
        # If p or q is an ancestor of the other
        # return that ancestor
        return l or r

 
Problem: LeetCode
Reference: Marlen09
 
Time Complexity: O(h^2)
Space Complexity: O(1)
 

Explanation)

There are 2 patterns of finding the lowest common ancestor. 
1) Both p and q are descendants of a certain node
2) One of the nodes is the ancestor of the other
 

2 patterns

 
This solution's main goal is to distinguish which pattern is given and return the lowest common ancestor according to the pattern.
 

1. Base Case)

This base case looks a bit complicated but it's just shortened efficiently.
 
If there is no root, we return None.
If root is p, we return p.
If root is q, we return q.
 
It's just these 3 conditions, but written in a clever way.
 

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 1. Base Case
        if not root or root == p or root == q:
            return root

 

2. Find p and q in left and right subtrees)

These recursions are used for us to find p and q in left/right subtrees.
 
This recursion will give us two results.
1) We get values for both l and r
2) We only get result of either l or r
 

Two Results

Essentially, the result of l and r will let us know which pattern of ancestry is used.
 

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 1. Base Case
        if not root or root == p or root == q:
            return root

        # 2. Find p and q in left and right subtrees 
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)

 

3. Distinguish the pattern)

As I said the result of l and r will allow us to distinguish the pattern of ancestry.
 
1) If we get values for both l and r, that means there is a certain node that has both p and q as its descendants.
2) If we get one of the values of either l or r, that means that variable with a value is the ancestor ot the other.
 
Return the node according to the result.
 

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 1. Base Case
        if not root or root == p or root == q:
            return root

        # 2. Find p and q in left and right subtrees 
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)

        # 3. Distinguish the pattern
        if l and r:
            return root
        return l or r

---

 
 
It's amazing this user came up with such concise and clever solution. I thought about having 2 patterns of ancestry, but I didn't know how to code it. Amazing solution!