236. Lowest Common Ancestor of a Binary Tree

Problem Description

In this problem, we are given the roots of a binary tree and two nodes from this tree. Our task is to find the lowest common ancestor (LCA) of these two nodes. The LCA of two nodes p and q is defined as the deepest node in the tree that has both p and q as descendants (with a node being allowed to be a descendant of itself).

Intuition

The solution to this problem is based on a recursive traversal of the binary tree. When we traverse the tree, we are looking for three possible conditions at each node:

1. One condition is that we have found either node p or q. In this case, the current node could potentially be the LCA.

2. The second condition is that one of the nodes p or q is found in the left subtree and the other is found in the right subtree of the current node. If this is the case, then the current node is the LCA for p and q, as it sits above both nodes in the tree.

3. The third condition is that both nodes are located in either the left subtree or the right subtree of the current node. In this instance, the lowest common ancestor will be deeper in the tree, so we continue searching in the subtree that contains both nodes.

The base case for our recursion occurs when we reach a null node (indicating that we've reached the end of a path and haven't found either p or q), or when we find one of the nodes p or q.

To implement this intuition, we use a recursive algorithm that will search for p and q starting from root. At each step, we make a recursive call to search the left and right subtrees. If both recursive calls return non-null nodes, it means we've found p and q in different subtrees of the current node, and thus the current node is the LCA. If only one of the subtrees contains one of the nodes (or both), we return that subtree's node, propagating it up the call stack. If neither subtree contains either of the nodes, we return null.

This recursive approach continues until the LCA is found, or we've confirmed that p and q are not present in the binary tree.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

To implement the solution for finding the lowest common ancestor, the algorithm employs a depth-first search (DFS) pattern, which is a type of traversal that goes as deep as possible down one path before backing up and trying another. This pattern is particularly useful for working with tree data structures. Here is an overview of how the DFS is applied in this solution:

1. Recursive Function: The solution defines a recursive function lowestCommonAncestor which takes the current node (root), and the two nodes we are finding the LCA for (p and q). Recursion leverages the call stack to perform a backtracking search, allowing us to explore all paths down the tree and retrace our steps.

2. Base Case: The base case of the recursion occurs when either the current node is null, or the current node matches one of the nodes we're looking for (p or q). In this case, the function returns the current node, which may be null or the matching node.

3. Search Left and Right Subtrees: If the base case is not met, the algorithm recursively calls lowestCommonAncestor for the left and right children of the current node. These calls effectively search for the nodes p and q in both subtrees.

4. Postorder Traversal: Since the recursion explores both left and right subtrees before dealing with the current node, this represents a postorder traversal pattern. After both subtrees have been searched, the algorithm processes the current node.

5. LCA Detection:

   • If both the left and right subtree recursive calls return non-null nodes, it means both p and q have been found in different subtrees, and therefore the current node is their lowest common ancestor.
   • If only one of the calls returns a non-null node, that indicates the current subtree contains at least one of the two nodes, and potentially both. The non-null node is returned up the call stack.
   • If both calls return null, it means neither p nor q was found in the current subtree, and null is returned.

6. Propagation of the LCA: The LCA, once found, is propagated up the call stack to the initial call, and ultimately returned as the result of the function.

Here is the implementation of the algorithm in the reference solution provided:

1class Solution:
2    def lowestCommonAncestor(
3        self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
4    ) -> 'TreeNode':
5        if root is None or root == p or root == q:
6            return root
7        left = self.lowestCommonAncestor(root.left, p, q)
8        right = self.lowestCommonAncestor(root.right, p, q)
9        return root if left and right else (left or right)

In the provided code snippet, the if condition handles the base case, while the calls to lowestCommonAncestor(root.left, p, q) and lowestCommonAncestor(root.right, p, q) implement the recursive search. The final return statement decides which node to return based on whether the left and/or right calls found the nodes p and q.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the following binary tree:

1        A
2       / \
3      B   C
4     / \
5    D   E

In this binary tree, let's say we want to find the lowest common ancestor (LCA) of the nodes D and E.

1. We start our recursive function lowestCommonAncestor at the root node A.

2. Since the root is neither null, nor is it D or E, we proceed to make recursive calls to both the left and right subtrees of A.

3. The left recursive call goes to node B. Again, B isn't null, D, or E, so we continue.

4. Recursively, for node B, we go left to D and right to E. Node D matches one of our target nodes, so the left call returns D to the call on B. Similarly, on the right side, the node E matches the other target node, so the right call returns E to the call on B.

5. With both sides of B returning a non-null node (D on the left and E on the right), we determine that B must be the LCA because it's the node where both target nodes D and E subtrees split. The function returns node B up to the call on A.

6. Since the recursive call on the left of A returned B (non-null) and the call on the right of A (to C) will return null (since neither D nor E is in that subtree), the final decision at A is based on whether one or both sides are non-null.

7. Since the right call returns null, and the left call returns B (non-null), the function finally returns B, the LCA of D and E.

Following the recursive definition used in our solution, we can confirm that node B is the lowest common ancestor of nodes D and E in this binary tree.

Solution Implementation

Time and Space Complexity

The time complexity of the given code for finding the lowest common ancestor (LCA) in a binary tree is O(N), where N is the number of nodes in the tree. This complexity arises because, in the worst-case scenario, the code will have to visit each node once to determine the LCA.

The space complexity of the code is O(H), where H is the height of the binary tree. This is due to the recursive calls on the stack while the algorithm traverses down to find p and q. In the worst case of a skewed tree, H can be N, thereby having a space complexity of O(N).

Learn more about how to find time and space complexity quickly using problem constraints.