1644. Lowest Common Ancestor of a Binary Tree II

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

The task is to find the lowest common ancestor (LCA) of two given nodes, p and q, in a binary tree. The LCA is defined as the lowest node (furthest from the root) that has both nodes p and q as descendants. It's important to note that a node can be a descendant of itself according to the problem statement. If either p or q doesn't exist in the tree, the result should be null. Every node in the tree has a unique value.

Intuition

To solve this problem, we can use a depth-first search (DFS) traversal. The main idea is to recursively explore the tree, starting from the root and moving towards the leaves, to find the nodes p and q. We should check three conditions during traversal:

  1. Whether the current node is p or q.
  2. Whether one of the node's left descendants is p or q.
  3. Whether one of the node's right descendants is p or q.

The lowest common ancestor will be the node where both the left and right subtree searches report finding either p or q. In other words, it's the point in the tree where paths from the root to p and q diverge.

If p and q are on the same branch, the LCA will be the one higher up on the path. If p is an ancestor of q, then p is the LCA and vice versa. To implement this, we can do a post-order traversal and return three possible values:

  • True if p or q is found,
  • False if neither is found,
  • A node if it is the ancestor of both p and q.

A global variable or a nonlocal in Python, which Python allows to be modified inside a nested function, is used to keep track of the answer. Once we find p and q, we assign the LCA to this variable.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The solution uses a Depth-First Search (DFS) traversal to go through each node in the binary tree and check for the presence of nodes p and q. To do this, we define a helper function dfs within the lowestCommonAncestor method.

Here is a breakdown of how the dfs function works:

  • The function takes three arguments: root, p, and q, where root is the current node of the tree that we are exploring.
  • It begins with a base case that checks if the root is None, meaning we have reached the end of a path without finding a node. If this is the case, it returns False.
  • Left Recursion: Recursively call dfs for the left child of the current node (root.left).
  • Right Recursion: Recursively call dfs for the right child of the current node (root.right).

These recursive calls will do a post-order traversal of the tree. After these calls, we have three pieces of information:

  • l: Whether node p or q has been found in the left subtree.
  • r: Whether node p or q has been found in the right subtree.
  • The value of the current node.

Using this information, we can detect the LCA:

  • If l and r are both True, it implies that p is found in one subtree and q in the other, making the current node their LCA, so we set ans to root.
  • If one of l or r is True and the current node's value matches p or q, the current node is the LCA - this happens when one is a descendant of the other.

After the visit to each node, we return a boolean to indicate if either p or q has been found in the current subtree or if the current node is p or q. This boolean is the OR of:

  • l (result from the left subtree),
  • r (result from the right subtree), and
  • a check whether the current root matches either p or q.

Finally, lowestCommonAncestor initializes a variable ans to None, which is used to store the LCA. We declare ans as nonlocal inside dfs so that it can be modified within the nested function. The dfs function is then called with the original root, p, and q. The ans is returned as the final result of the lowestCommonAncestor method. If p and q are both present in the tree, ans will be their lowest common ancestor; if either is not present, ans will remain None.

This approach efficiently utilizes the single pass post-order DFS traversal to not just search for p and q but also to identify the LCA without any additional storage or multiple passes through the tree.

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

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

Let's consider a binary tree and walk through the solution to find the lowest common ancestor (LCA) for two given nodes, p and q.

1    3
2   / \
3  5   1
4 /|   |\
56 2   0 8
6  |\
7  7 4

For our example, let's assume we want to find the LCA of nodes 5 and 4.

  1. We initiate the lowestCommonAncestor method with the root node (3) and nodes p (5) and q (4).
  2. We enter the dfs function with the current root (node 3) and check for p and q.
  3. Since root is not None, it's not the base case, so we proceed.
  4. Left Recursion: We call dfs(root.left, p, q) which is dfs(5, 5, 4).
    • Entering the dfs function again for node 5, we check the left and right children.
    • Left Recursion: Calling dfs(5.left, p, q) which is dfs(6, 5, 4) returns False.
    • Right Recursion: Calling dfs(5.right, p, q) which is dfs(2, 5, 4).
      • For node 2, we again explore its children.
      • Left Recursion: Calling dfs(2.left, p, q) which is dfs(7, 5, 4) returns False.
      • Right Recursion: Calling dfs(2.right, p, q) which is dfs(4, 5, 4) returns True because root matches q.
    • Since dfs(2, 5, 4) found q, it returns True to dfs(5, 5, 4) call.
  5. Returning to dfs(5, 5, 4), the left call returned False, but the right returned True, and since the current root is p (5), we find that 5 is indeed the LCA because it is an ancestor to q (4).
  6. The result of True is then carried up and we exit the left side of the root.
  7. Right Recursion: We now call dfs(root.right, p, q) which is dfs(1, 5, 4).
    • This path will not find either p or q, and will therefore return False.
  8. With dfs(3, 5, 4), since the l (Left Recursion) returned True and r (Right Recursion) returned False, and no match for p or q is found at the current node (3), we simply propagate the True back up.
  9. Since the LCA has been set to node 5 within dfs(5, 5, 4), the global ans variable will now hold the reference to the LCA.
  10. Finally, lowestCommonAncestor returns ans which is node 5, and this node is indeed the LCA of nodes 5 and 4 as per our tree structure.

In conclusion, the example walks through the DFS approach to efficiently find the LCA by using a helper dfs function that handles recursive traversal and updates an ancestor variable when both nodes are found within the subtrees.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, x):
4        self.val = x
5        self.left = None
6        self.right = None
7
8
9class Solution:
10    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
11        # This variable will hold the lowest common ancestor once it is found.
12        self.ancestor = None
13
14        def dfs(current_node):
15            """
16            Perform a depth-first search to find the lowest common ancestor.
17          
18            Args:
19            current_node (TreeNode): The current node being visited.
20          
21            Returns:
22            bool: True if the current node is ancestor or is a subtree containing p or q.
23            """
24            if current_node is None:
25                return False
26          
27            # Search left subtree for p or q
28            left = dfs(current_node.left)
29          
30            # Search right subtree for p or q
31            right = dfs(current_node.right)
32          
33            # Check if current node is either p or q
34            mid = current_node == p or current_node == q
35          
36            # If any two of the three flags left, right, mid are True, current_node is an ancestor
37            if mid + left + right >= 2:
38                self.ancestor = current_node
39          
40            # Return True if the current node is p, q, or if p or q is in the subtree rooted at current_node
41            return mid or left or right
42
43        # Call dfs to initiate the depth-first search
44        dfs(root)
45      
46        return self.ancestor
47
48# The provided solution can be used to find the lowest common ancestor (LCA) of two nodes in a binary tree.
49
1class Solution {
2
3    // The variable 'answer' will hold the solution.
4    private TreeNode answer;
5
6    // This method returns the lowest common ancestor of two nodes in the binary tree.
7    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
8        // Initiate the depth-first search.
9        findLowestCommonAncestor(root, p, q);
10        return answer;
11    }
12
13    // Helper method for a DFS to identify if the current node is part of the path to p or q.
14    private boolean findLowestCommonAncestor(TreeNode currentNode, TreeNode p, TreeNode q) {
15        // Base case: if the current node is null, return false.
16        if (currentNode == null) {
17            return false;
18        }
19      
20        // Traverse the left side of the tree and store if p or q was found in the left subtree.
21        boolean foundInLeftSubtree = findLowestCommonAncestor(currentNode.left, p, q);
22        // Traverse the right side of the tree and store if p or q was found in the right subtree.
23        boolean foundInRightSubtree = findLowestCommonAncestor(currentNode.right, p, q);
24
25        // If both left and right subtrees contain p or q, then the current node is the LCA.
26        if (foundInLeftSubtree && foundInRightSubtree) {
27            answer = currentNode;
28        }
29
30        // If either left or right subtree contains p or q, and the current node is either p or q,
31        // then the current node is the LCA.
32        if ((foundInLeftSubtree || foundInRightSubtree) && (currentNode.val == p.val || currentNode.val == q.val)) {
33            answer = currentNode;
34        }
35
36        // Return true if the current node is either p or q or if p or q is found in either subtree.
37        return foundInLeftSubtree || foundInRightSubtree || currentNode.val == p.val || currentNode.val == q.val;
38    }
39}
40
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13    /**
14     * Finds the lowest common ancestor (LCA) of two given nodes in a binary tree.
15     * @param root The root node of the binary tree.
16     * @param p The first node for which LCA is to be found.
17     * @param q The second node for which LCA is to be found.
18     * @return The LCA of nodes p and q.
19     */
20    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
21        findLowestCommonAncestor(root, p, q);
22        return ancestor;
23    }
24
25private:
26    TreeNode* ancestor = nullptr; // Holds the lowest common ancestor once found
27
28    /**
29     * Helper method to perform DFS to find LCA.
30     * @param current The current node being looked at.
31     * @param nodeP The first node for which LCA is to be found.
32     * @param nodeQ The second node for which LCA is to be found.
33     * @return True if the current subtree contains either nodeP or nodeQ.
34     */
35    bool findLowestCommonAncestor(TreeNode* current, TreeNode* nodeP, TreeNode* nodeQ) {
36        if (!current) {
37            return false; // Base case: reached the end of a branch
38        }
39
40        bool left = findLowestCommonAncestor(current->left, nodeP, nodeQ); // Search LCA in the left subtree
41        bool right = findLowestCommonAncestor(current->right, nodeP, nodeQ); // Search LCA in the right subtree
42      
43        // If both left and right are true, current is the LCA
44        if (left && right) {
45            ancestor = current;
46        }
47
48        // If either left or right is true and current is either nodeP or nodeQ, current is the LCA
49        if ((left || right) && (current->val == nodeP->val || current->val == nodeQ->val)) {
50            ancestor = current;
51        }
52
53        // Return true if current is nodeP or nodeQ or if left or right are true
54        return left || right || current->val == nodeP->val || current->val == nodeQ->val;
55    }
56};
57
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) {
8        this.val = val;
9        this.left = this.right = null;
10    }
11}
12
13/**
14 * Finds the lowest common ancestor (LCA) of two nodes in a binary tree.
15 * @param {TreeNode} root - The root of the binary tree.
16 * @param {TreeNode} node1 - The first node to find the LCA for.
17 * @param {TreeNode} node2 - The second node to find the LCA for.
18 * @return {TreeNode | null} - The LCA of node1 and node2, or null if none found.
19 */
20const lowestCommonAncestor = (
21    root: TreeNode,
22    node1: TreeNode,
23    node2: TreeNode
24): TreeNode | null => {
25    // Declaration of the LCA variable.
26    let answer: TreeNode | null = null;
27
28    // Depth-first search (DFS) function to traverse the tree and find the LCA.
29    const depthFirstSearch = (currentNode: TreeNode | null): boolean => {
30        if (!currentNode) {
31            // If the current node is null, return false indicating the node is not part of the ancestry of node1 or node2.
32            return false;
33        }
34
35        // Recursively search in the left subtree.
36        const leftSearch = depthFirstSearch(currentNode.left);
37        // Recursively search in the right subtree.
38        const rightSearch = depthFirstSearch(currentNode.right);
39
40        // If both left and right subtrees return true, the current node is the LCA.
41        if (leftSearch && rightSearch) {
42            answer = currentNode;
43        }
44
45        // If either the left or right subtree returns true and the current node equals one of the nodes we're looking for,
46        // the current node is the LCA.
47        if (
48            (leftSearch || rightSearch) &&
49            (currentNode.val === node1.val || currentNode.val === node2.val)
50        ) {
51            answer = currentNode;
52        }
53
54        // Return true if the current node is equal to node1 or node2 or if either the left or right subtree returns true.
55        return (
56            leftSearch || rightSearch || currentNode.val === node1.val || currentNode.val === node2.val
57        );
58    };
59
60    // Initialize the search.
61    depthFirstSearch(root);
62
63    // Return the identified LCA or null if none found.
64    return answer;
65};
66
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Time and Space Complexity

The provided code implements a Depth First Search (DFS) algorithm to find the lowest common ancestor (LCA) of two nodes in a binary tree.

Time Complexity:

To determine the time complexity, we consider that the function dfs is called recursively for every node in the tree until it finds the nodes p and q.

  • It visits each node exactly once.
  • The work done at each node is constant (comparisons and boolean checks).

Therefore, the time complexity is O(N), where N is the number of nodes in the binary tree.

Space Complexity:

The space complexity is determined by the depth of the recursion stack which is the height of the binary tree.

  • In the worst case for a skewed tree (like a linked list), the recursion stack could be as deep as the number of nodes, which would be O(N).
  • In the best case for a balanced tree, the height of the tree would be log(N), and thus the space complexity would be O(log(N)).

The space complexity of the algorithm is O(H), where H is the height of the tree, which is O(N) in the worst case and O(log(N)) in the best case.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching 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.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ