👵236. Lowest Common Ancestor of a Binary Tree

Medium | Grind 75 | January 17th Tuesday, 2023

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Constraints:

• The number of nodes in the tree is in the range [2, 10^5].

• -10^9 <= Node.val <= 10^9

• All Node.val are unique.

• p != q

• p and q will exist in the tree.

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3

Input: root = [1,2], p = 1, q = 2
Output: 1

SOLUTION

Since P and Q are known to exist in the tree, the algorithm is guaranteed to find a common ancestor. There are two potential scenarios in which a common ancestor is identified:

1. When the nodes p and q are found from the left and right subtree, the current node is the common ancestor. This is where P and Q diverges.

2. If only one P or Q is found in a subtree, that node is the LCA for that subtree. For example, if P is found in the left subtree, the LCA for the entire left subtree. If Q is not found in the right subtree, it is guaranteed to exist under the left subtree, whose LCA is P.

We use a depth-first search (DFS) approach, recursively iterating over the binary tree and examining both the left and right subtrees. If P or Q is found in a subtree, the iteration for that subtree is terminated. The search for the other node continues in the opposite subtree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        def dfs(root): 
            if not root: 
                return 

            # return and stop going down the tree from the node
            if root == p or root == q: 
                return root

            left, right = None, None    
            left = dfs(root.left)
            right = dfs(root.right)

            # current node is where p and q diverge from
            if left and right: 
                return root
            
            # either p or q is the common ancestor or none 
            return left or right

        return dfs(rootQ) 

TIME: O(n) where n is the number of nodes in the binary tree. This is because the helper function 'dfs' visits each node in the binary tree exactly once in the worst case.

SPACE: O(1) since no extra space is being used.

* Written with help from ChatGPT *