1676. Lowest Common Ancestor of a Binary Tree IV

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

The problem is based on a fundamental concept from graph theory applied to binary trees, known as the "lowest common ancestor" (LCA). Specifically, we are given the root node of a binary tree where all node values are unique, and an array of TreeNode objects that are present in the tree. Our task is to determine the LCA of all of these nodes. The LCA is defined as the lowest (deepest) node in the tree that has every given node in the array as a descendant (including the possibility of a node being a descendant of itself). The concept of "lowest" here refers to the deepest node in the hierarchy of the tree. In other words, we are looking for a shared ancestor of these nodes that is as far down the tree as possible.

Flowchart Walkthrough

First, let's analyze the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: A binary tree is a specialized form of a graph.

Is it a tree?

  • Yes: Specifically, the problem involves a binary tree.

DFS

  • Since the problem specifically involves finding the lowest common ancestor in a binary tree, Depth-First Search (DFS) is appropriate here. DFS is typically used in trees to explore possibilities from the root to the leaves (or vice versa), which fits our requirements to check nodes and find commonality between branches.

Conclusion: Based on the flowchart, the Depth-First Search (DFS) pattern is suitable for this problem as it allows us to traverse the structure of the tree efficiently to determine the lowest common ancestor of the given nodes.

Intuition

To solve this problem, we can use a depth-first search (DFS) algorithm that explores each subtree rooted at the provided root node. Since all node values are unique, we can use a set to store the values of all the nodes we're trying to find the LCA for. This allows us to efficiently check if a node is part of our target group.

The recursive DFS function will traverse down the tree in a post-order fashion (left, right, node). Here's what happens at each step:

  1. If we reach a None node or a node whose value is in our set of target nodes, we return that node up the call stack. Returning a target node signals that we've found one of the nodes we're interested in.
  2. We then call the DFS function on the left and the right children of the current node.
  3. Upon receiving the results from both subtrees:
    • If both calls returned a non-None node, it means that both subtrees contain at least one target node each. In this case, the current node is the LCA, as it is the lowest node that has descendants from both subtrees.
    • If only one of the calls returned a non-None node, it implies that all the target nodes are located in one subtree. Hence, the result from that subtree is the current LCA for the nodes encountered so far.
    • If both calls returned None, neither subtree contains any of the target nodes, and thus we also return None.
  4. Initially, the DFS is called on the root node and the set of values that correspond to our target nodes.
  5. Ultimately, the last non-None node that is returned by our DFS function is the LCA of all the target nodes.

This recursive algorithm effectively prunes branches of the tree that do not contain any of the target nodes to find the LCA efficiently.

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

Solution Approach

The implementation of the solution consists of a depth-first search (DFS) function called dfs, which is responsible for traversing the binary tree to find the lowest common ancestor (LCA) of the given set of nodes. Here's how the implementation unfolds in detail:

  1. A set s is created to store the values of the nodes provided in the list nodes. This is done to allow for quick membership checks, as we want to know whether we have encountered one of the target nodes during traversal.
s = {node.val for node in nodes}
  1. The dfs function is then defined to perform a recursive post-order traversal (visit left subtree, then right subtree, then the node itself):
def dfs(root):
    if root is None or root.val in s:
        return root
    left, right = dfs(root.left), dfs(root.right)
    if left and right:
        return root
    return left or right

  • The base case of the recursion checks if the current node is None or if its value is in the set s (meaning it's one of the target nodes). In either scenario, it returns the node itself – None indicates we're at a leaf's child, while a node with value in s is one of the desired LCA nodes.

  • If the current node is not None and not in the set s, the function recursively calls itself for the left and right children of the current node (dfs(root.left) and dfs(root.right) respectively).

  • After the recursive calls, if both left and right are not None, it means that we've found target nodes in both the left and right subtrees. Thus, the current node must be their LCA, and it is returned as the result.

  • If only one of left or right contains a target node (i.e., one of them is not None), that node is returned. This is because the tree branch that returned None doesn't contain any of the target nodes, so the LCA must be on the branch that returned a node.

  1. Finally, the dfs function is called with the root of the binary tree. The tree is traversed, and the lowest common ancestor of all the nodes in nodes is returned.
return dfs(root)

The dfs function effectively navigates the tree structure, identifying the points where paths to each of the target nodes diverge, pinpointing the node that serves as the common ancestor with the least depth.

By using a recursive approach, the algorithm avoids checking non-relevant parts of the tree and leverages the call stack to backtrack until it finds the common ancestor. The set data structure enables efficient lookups to determine if a node is part of the target group. Together, these approaches allow the provided solution to efficiently find the LCA with a time complexity that is proportional to the number of nodes in the tree, O(N), where N is the number of nodes in the tree.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Imagine a binary tree that looks like this:

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

Let's say we want to find the lowest common ancestor (LCA) of the nodes with values [5, 1, 6, 2, 0].

First, we create a set of these values, which is {5, 1, 6, 2, 0} for quick look-up during the traversal.

We then start with the dfs function on the root of the tree, which is the node with value 3.

  1. The current node 3 is not None, and its value is not in the set {5, 1, 6, 2, 0}, so we proceed with the recursive calls for its left and right children.

  2. For the left child (value 5):

    • The value 5 is in the set, so we return this node immediately without further recursion.

  3. For the right child (value 1):

    • The value 1 is in the set, so we return this node immediately without further recursion.

Since the value 5 node was found in the left subtree and the value 1 node was found in the right subtree, and the current node (value 3) is the parent to both subtrees, by the rules of the algorithm, node 3 is the LCA for nodes 5 and 1.

However, since we need to find the LCA of the nodes [5, 1, 6, 2, 0], we need to see if node 3 is also the LCA for the other values.

  1. For the left child (value 5):
    • Again, we return the node with value 5 as we did previously. This time, let's explore below it to account for 2 and 6.
    • Node 6 is in the set and is a left child, so it's returned.
    • Node 2 is in the set and is a right child, so it's returned.

Since both 6 and 2 are on the left subtree (under node 5), and node 5 is returned for both, node 5 is the LCA for values [5, 6, 2].

  1. For the right child (value 1):
    • Node 0 is in the set and is the left child, so it's returned.

Now, we have the LCAs for the left and right subtrees as node 5 and node 1, respectively.

  1. Finally, since node 3 is the parent of both 5 and 1, and no further common ancestors exist that are lower than node 3 for the entire set [5, 1, 6, 2, 0], node 3 remains the LCA for all specified nodes in the set.

Therefore, the function would return the node with value 3 as the LCA.

This example demonstrates how the dfs function operates to efficiently find the lowest common ancestor by first populating a set with the values of all the target nodes and then traversing the binary tree recursively to determine the node that serves as the common ancestor to all the target nodes.

Solution Implementation

1class TreeNode:
2     def __init__(self, value):
3         self.val = value
4         self.left = None
5         self.right = None
6
7class Solution:
8    def lowestCommonAncestor(self, root: TreeNode, nodes: List[TreeNode]) -> TreeNode:
9        # Perform depth-first search to find the lowest common ancestor.
10        def dfs(current_node):
11            # Base case: If current node is None or in target nodes set, return it.
12            if current_node is None or current_node in target_nodes_set:
13                return current_node
14          
15            # Recursively search the left and right subtrees.
16            left_ancestor = dfs(current_node.left)
17            right_ancestor = dfs(current_node.right)
18          
19            # If both left and right are not None, current node is the lowest common ancestor.
20            if left_ancestor and right_ancestor:
21                return current_node
22          
23            # Otherwise, return the non-None value or None.
24            return left_ancestor or right_ancestor
25
26        # Convert the list of nodes to a set for faster lookup.
27        # Note that the original code used node.val, assuming unique values for simplicity.
28        # Here we use the nodes themselves for the matching, which is more general.
29        target_nodes_set = set(nodes)
30      
31        # Start the depth-first search from the root.
32        return dfs(root)
33```
34
35Note: In the comment, it's mentioned that the original code assumed unique values for node `val`. However, the algorithm works directly on the node objects in the revised version. This provides a more direct approach in case the tree has non-unique values but distinct nodes.
36
37To run this code, you would need to import the `List` type from the `typing` module in Python 3 by adding the following line before the class definition:
38
39```python
40from typing import List
41
1class Solution {
2    // Use a set to keep track of the values of the nodes we're looking for.
3    private Set<Integer> targetNodeValues = new HashSet<>();
4
5    /**
6     * Finds the lowest common ancestor of all nodes in the array within the binary tree.
7     * 
8     * @param root  The root of the binary tree.
9     * @param nodes An array of nodes for which the lowest common ancestor is to be found.
10     * @return The lowest common ancestor node.
11     */
12    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
13        // Populate the set with the values of all target nodes.
14        for (TreeNode node : nodes) {
15            targetNodeValues.add(node.val);
16        }
17        // Start DFS to find the lowest common ancestor.
18        return findCommonAncestorDFS(root);
19    }
20
21    /**
22     * Recursive function to find the lowest common ancestor.
23     * 
24     * @param currentNode The node currently being visited in the DFS.
25     * @return The lowest common ancestor if it exists, or one of the target nodes, or null.
26     */
27    private TreeNode findCommonAncestorDFS(TreeNode currentNode) {
28        // If reached the end of a path or found one of the target nodes, return current node.
29        if (currentNode == null || targetNodeValues.contains(currentNode.val)) {
30            return currentNode;
31        }
32        // Recurse on left subtree.
33        TreeNode left = findCommonAncestorDFS(currentNode.left);
34        // Recurse on right subtree.
35        TreeNode right = findCommonAncestorDFS(currentNode.right);
36      
37        // If only one side returned a node, return that node.
38        if (left == null) {
39            return right;
40        }
41        if (right == null) {
42            return left;
43        }
44        // If nodes are found on both sides, current node is the lowest common ancestor.
45        return currentNode;
46    }
47}
48
49/**
50 * Definition for a binary tree node.
51 * public class TreeNode {
52 *     int val;
53 *     TreeNode left;
54 *     TreeNode right;
55 *     TreeNode(int x) { val = x; }
56 * }
57 */
58
1#include <unordered_set>
2#include <vector>
3#include <functional>
4
5// Definition for a binary tree node.
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17    // This function finds the lowest common ancestor (LCA) of a list of nodes in a binary tree.
18    TreeNode* lowestCommonAncestor(TreeNode* root, const std::vector<TreeNode*>& nodes) {
19      
20        // Create an unordered set to store the values of all target nodes for constant time checks.
21        std::unordered_set<int> targetNodesValues;
22        for (auto node : nodes) {
23            targetNodesValues.insert(node->val);
24        }
25      
26        // Define a depth-first search lambda function to find the LCA of the nodes.
27        std::function<TreeNode*(TreeNode*)> dfs = [&](TreeNode* currentNode) -> TreeNode* {
28            // If we've reached a nullptr or one of the target nodes, return the current node.
29            if (!currentNode || targetNodesValues.count(currentNode->val)) {
30                return currentNode;
31            }
32          
33            // Recur on the left and right subtrees.
34            TreeNode* leftLCA = dfs(currentNode->left);
35            TreeNode* rightLCA = dfs(currentNode->right);
36          
37            // If both sides return a non-nullptr, we've found the LCA.
38            if (leftLCA && rightLCA) {
39                return currentNode;
40            }
41          
42            // Otherwise, if one side is nullptr, return the non-nullptr result.
43            return leftLCA ? leftLCA : rightLCA;
44        };
45      
46        // Begin the search from the root of the tree.
47        return dfs(root);
48    }
49};
50
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 = null;
10        this.right = null;
11    }
12}
13
14/**
15 * Finds the lowest common ancestor (LCA) of a given set of nodes in a binary tree.
16 * @param {TreeNode | null} root - The root of the binary tree.
17 * @param {TreeNode[]} nodes - The list of nodes for which to find the LCA.
18 * @return {TreeNode | null} - The LCA node or null if not found.
19 */
20function lowestCommonAncestor(root: TreeNode | null, nodes: TreeNode[]): TreeNode | null {
21    // Create a set to store the values of the nodes for efficient lookup
22    const nodeValuesSet: Set<number> = new Set();
23    for (const node of nodes) {
24        nodeValuesSet.add(node.val);
25    }
26
27    // Helper function to recursively find the LCA
28    function dfs(currentNode: TreeNode | null): TreeNode | null {
29        // If the current node is null or the value is in the set, return the current node
30        if (!currentNode || nodeValuesSet.has(currentNode.val)) {
31            return currentNode;
32        }
33
34        // Recursively search in the left and right subtrees
35        const leftLCA: TreeNode | null = dfs(currentNode.left);
36        const rightLCA: TreeNode | null = dfs(currentNode.right);
37
38        // If both left and right LCA are found, the current node is the LCA
39        if (leftLCA && rightLCA) {
40            return currentNode;
41        }
42
43        // Otherwise, return whichever side LCA is found, or null if neither is found
44        return leftLCA || rightLCA;
45    }
46
47    // Start the LCA search from the root of the tree
48    return dfs(root);
49}
50
51// Example usage:
52// const root = new TreeNode(3);
53// root.left = new TreeNode(5);
54// root.right = new TreeNode(1);
55// const nodes = [root.left, root.right];
56// console.log(lowestCommonAncestor(root, nodes)); // Output should be TreeNode with val = 3
57

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N), where N is the number of nodes in the binary tree. This is because the Depth First Search (DFS) function dfs is called once for each node in the tree in the worst case. The search involves checking if a node's value is in the set s of the nodes' values we are looking for and then recursively searching left and right children. Since the set s uses a hash set for lookup, the check for if root.val in s is O(1), so it does not add more than a constant factor to the complexity.

Space Complexity

The space complexity of the code also is O(N) in the worst-case scenario. This consists of two parts:

  1. The space used by the set s, which in the worst case could contain all nodes and thus take up O(N) space.
  2. The call stack due to recursion, which in the worst case (a degenerate tree, for example) could go up to O(N).

The recursive calls could return early if the nodes are found quickly, which may lead to lower space usage in practice, but the worst-case space complexity remains O(N).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How many times is a tree node visited in a depth first search?

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

Want a Structured Path to Master System Design Too? Don’t Miss This!