Lowest Common Ancestor of a Binary Tree

The problem description can be found in LeetCode.

Approach

Here, it is enough to draw some examples. When we are in a certain node, we can recursively check the values that point to p and q pointers on both left and right. At this point, we can have three possibilities:

1. No nodes found. This means that we have to look at other nodes.
2. We found one node at the left and one node at the right. This means that the current node is our LCA.
3. We found either left or right. So, we can return the one we found.

Solution

from typing import Optional


class Solution:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        def dfs(node: "TreeNode") -> Optional["TreeNode"]:
            if not node:
                return None
            if node.val == p.val or node.val == q.val:
                return node

            left = dfs(node.left)
            right = dfs(node.right)
            if left and right:
                return node
            if left:
                return left
            if right:
                return right

            raise Exception("unreachable")

        return dfs(root)

Complexity

• Time: $O(n)$
• Space: $O(h)$

Where $n$ is the number of nodes in the tree and $h$ is its height. If the tree is unbalanced, it is like having a Linked List, hence $h=n$.