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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

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

1class TreeNode:
2    def __init__(self, value):
3        self.value = value
4        self.left = None
5        self.right = None
6
7
8class Solution:
9    def lowestCommonAncestor(self, root: TreeNode, node1: TreeNode, node2: TreeNode) -> TreeNode:
10        # If the root is None, or the root is one of the nodes we're looking for,
11        # we return the root as the LCA (Lowest Common Ancestor)
12        if root is None or root == node1 or root == node2:
13            return root
14
15        # Look for the LCA in the left subtree
16        left_lca = self.lowestCommonAncestor(root.left, node1, node2)
17
18        # Look for the LCA in the right subtree
19        right_lca = self.lowestCommonAncestor(root.right, node1, node2)
20
21        # If both left and right LCA are non-null, it means one node is in the left
22        # subtree and the other is in the right, so root is the LCA
23        if left_lca and right_lca:
24            return root
25
26        # Otherwise, if one of the LCAs is non-null, return that one
27        return left_lca if left_lca else right_lca
28
1// Definition for a binary tree node.
2class TreeNode {
3    int val;           // The value of the node
4    TreeNode left;     // Reference to the left child
5    TreeNode right;    // Reference to the right child
6
7    // Constructor to initialize the node with a value
8    TreeNode(int x) { 
9        val = x; 
10    }
11}
12
13class Solution {
14    /**
15     * Finds the lowest common ancestor of two nodes in a binary tree.
16     * @param root The root node of the binary tree.
17     * @param p The first node to find the ancestor for.
18     * @param q The second node to find the ancestor for.
19     * @return The lowest common ancestor node or null if not found.
20     */
21    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
22        // If the root is null or root is either p or q, then root is the LCA
23        if (root == null || root == p || root == q) return root;
24      
25        // Recurse on the left subtree to find the LCA of p and q
26        TreeNode left = lowestCommonAncestor(root.left, p, q);
27        // Recurse on the right subtree to find the LCA of p and q
28        TreeNode right = lowestCommonAncestor(root.right, p, q);
29      
30        // If finding LCA in the left subtree returns null, the LCA is in the right subtree
31        if (left == null) return right;
32        // If finding LCA in the right subtree returns null, the LCA is in the left subtree
33        if (right == null) return left;
34      
35        // If both left and right are non-null, we've found the LCA at the root
36        return root;
37    }
38}
39
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int value;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
8 * };
9 */
10
11class Solution {
12public:
13    /* Function to find the lowest common ancestor (LCA) of two given nodes in a binary tree.
14     * 
15     * @param root The root node of the binary tree.
16     * @param firstNode The first node for which the LCA is to be found.
17     * @param secondNode The second node for which the LCA is to be found.
18     * @return The LCA of the two nodes.
19     */
20    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* firstNode, TreeNode* secondNode) {
21        // If root is nullptr or root is one of the nodes, then root itself is the LCA.
22        if (!root || root == firstNode || root == secondNode) return root;
23
24        // Recursively find the LCA in the left subtree.
25        TreeNode* leftLCA = lowestCommonAncestor(root->left, firstNode, secondNode);
26        // Recursively find the LCA in the right subtree.
27        TreeNode* rightLCA = lowestCommonAncestor(root->right, firstNode, secondNode);
28
29        // If both the left and right subtrees contain one of the nodes each, then the current root is the LCA.
30        if (leftLCA && rightLCA) return root;
31
32        // If only one subtree contains both the nodes, return that subtree's LCA.
33        return leftLCA ? leftLCA : rightLCA;
34    }
35};
36
1// Definition for a binary tree node.
2class TreeNode {
3    val: number
4    left: TreeNode | null
5    right: TreeNode | null
6
7    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8        this.val = (val === undefined ? 0 : val);
9        this.left = (left === undefined ? null : left);
10        this.right = (right === undefined ? null : right);
11    }
12}
13
14/**
15 * Finds the lowest common ancestor (LCA) of two nodes in a binary tree.
16 * The LCA is defined as the lowest node in T that has both p and q as descendants
17 * (where we allow a node to be a descendant of itself).
18 * 
19 * @param root - The root node of the binary tree.
20 * @param p - The first node to find the LCA for.
21 * @param q - The second node to find the LCA for.
22 * @return The LCA node or null if either p or q is not present in the tree.
23 */
24function lowestCommonAncestor(
25    root: TreeNode | null,
26    p: TreeNode | null,
27    q: TreeNode | null,
28): TreeNode | null {
29    /**
30     * Recursively searches the binary tree to find the LCA of nodes p and q.
31     * 
32     * @param currentNode - The current node being inspected in the binary tree.
33     * @return The LCA TreeNode, if it exists or null if not.
34     */
35    function findLCA(currentNode: TreeNode | null): TreeNode | null {
36        // If the current node is null, or we have found either p or q, return the current node
37        if (currentNode === null || currentNode === p || currentNode === q) {
38            return currentNode;
39        }
40
41        // Recursively search in the left subtree for one of the nodes
42        const leftSubtree = findLCA(currentNode.left);
43        // Recursively search in the right subtree for the other node
44        const rightSubtree = findLCA(currentNode.right);
45
46        // If both the left and right subtree calls return non-null, it means we have found the nodes p and q in both subtrees, 
47        // so the current node is the LCA.
48        if (leftSubtree !== null && rightSubtree !== null) {
49            return currentNode;
50        }
51
52        // If only one of the subtrees contains one of the nodes, return that subtree; if neither contains any, return null.
53        return leftSubtree !== null ? leftSubtree : rightSubtree;
54    }
55
56    // Start the LCA search from the root node
57    return findLCA(root);
58}
59

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.


Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄