1123. Lowest Common Ancestor of Deepest Leaves

MediumTreeDepth-First SearchBreadth-First SearchHash TableBinary Tree
Leetcode Link

Problem Description

In this problem, we're given the root of a binary tree. Our goal is to find the lowest common ancestor (LCA) of its deepest leaves. We are considering the following:

  • A leaf node is defined as a node with no children.
  • The root node has a depth of 0. If a node is at depth d, then its children's depth is d + 1.
  • The lowest common ancestor for a set of nodesS is the deepest node A such that every node from S is in the subtree rooted with A.

We need to determine this common ancestor and return it.

Intuition

The solution approach is a depth-first search (DFS) algorithm that proceeds as follows:

  1. Starting from the root, we perform DFS to explore the tree.

  2. Each step of the DFS returns two values: the possible LCA node at this point and the depth of the deepest leaf node in the current node's subtree.

  3. We compare the depths of left and right subtrees.

  4. The current node could be:

    • The LCA if both left and right subtree depths are equal, meaning they both contain leaves of the deepest level.
    • Not the LCA if one subtree is deeper than the other. In this case, the potential LCA is in the deeper subtree.

  5. The depth is incremented as we return back up the tree.

  6. Once the DFS is complete, the first element of the return value from the DFS initiated at the root will be the LCA of the deepest leaves.

By following this approach, the solution effectively finds the deepest level of the tree and then tracks back up the tree to find the lowest common ancestor of the nodes at this level.

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

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

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Solution Approach

The provided solution uses a recursive depth-first search (DFS) strategy for traversing the binary tree, which we implement in the dfs helper function. Here's a step-by-step approach to how the algorithm works:

  1. The dfs function is called recursively for each node starting with the root. This function returns two things:

    • The potential LCA node at the current subtree.
    • The depth of the deepest leaf in the current subtree.

  2. On each call of the dfs function:

    • We check if the current node is None (base case):
      • If it is, we return None and a depth of 0.
    • Otherwise, we recursively call dfs on the left child and right child.

  3. Each recursive call will provide us with:

    • The potential LCA nodes l and r from the left and right subtrees, respectively.
    • The depths d1 and d2 representing the maximum depths in those subtrees.

  4. We then compare the depths of the deepest leaves in the left and right subtrees:

    • If d1 > d2, the left subtree is deeper, so we return l (the left child's LCA) and d1 + 1 (the new depth).
    • If d1 < d2, the right subtree is deeper, so we return r (the right child's LCA) and d2 + 1.
    • If d1 == d2, both left and right subtrees have leaves at the same depth, hence, the current root node is their LCA, and we return root and either d1 + 1 or d2 + 1 (as they are equal).

  5. At the top level of the recursion, we call dfs(root) and are interested only in the first item of the tuple, which represents the lowest common ancestor of the deepest leaves.

This approach leverages the nature of DFS to explore and evaluate potential LCA nodes at varying depths of the tree, effectively utilizing recursion and tuple-unpacking to concisely express the critical decision logic within a binary tree traversal algorithm.

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

Which two pointer technique does Quick Sort use?

Example Walkthrough

Let's consider a simple binary tree to illustrate the solution approach:

1        A
2       / \
3      B   C
4     / \
5    D   E
6   /     \
7  F       G

In this tree, the deepest leaves are F and G, both at depth 3 from the root A. We wish to find their lowest common ancestor.

  1. Begin the DFS with the root node A.

  2. Call dfs(A), which proceeds to its children:

    • Call dfs(B).

      • Call dfs(D):
        • Call dfs(F):
          • Reached a leaf node, return (F, 1) (node, depth).
      • dfs(D) returns (F, 1) and now we check D's right branch.
        • Call dfs(E).
          • Call dfs(None) on left and returns (None, 0).
          • Call dfs(G) on right:
            • Reached a leaf node, return (G, 1).
          • dfs(E) compares depths 0 and 1, and returns (G, 2).
      • Now dfs(B) compares the info from D and E. 1 and 2 are not the same, so it takes the larger (from E), and returns (G, 3).

    • dfs(A) now needs to check the right subtree with dfs(C):

      • Call dfs(C) on left and right and returns (None, 1) for both as C is a leaf node.

  3. Back to dfs(A), we now compare the results from B and C, which are (G, 3) and (C, 1).

    • We see the left subtree has a greater depth, so we take its LCA (node G) and increment the depth for return, which becomes (G, 4).

  4. Since A is the top-level call, we return the first element, G, the LCA of the deepest leaves (F and G).

So the lowest common ancestor of the deepest leaves F and G is node E. However, notice that E is not the root; hence, the algorithm will correctly identify A as the actual LCA. The reason is that A is the lowest common ancestor that also contains E and hence F and G, which are the deepest leaves.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
10        # Helper function to perform a depth-first search on the tree.
11        def dfs(node):
12            # Base case: if the current node is None, it corresponds to a depth of 0.
13            if node is None:
14                return None, 0
15          
16            # Recursively find the lowest common ancestor and depth of the left subtree.
17            left_lca, left_depth = dfs(node.left)
18            # Recursively find the lowest common ancestor and depth of the right subtree.
19            right_lca, right_depth = dfs(node.right)
20          
21            # If the left subtree is deeper, return the left LCA and its depth increased by one.
22            if left_depth > right_depth:
23                return left_lca, left_depth + 1
24            # If the right subtree is deeper, return the right LCA and its depth increased by one.
25            if left_depth < right_depth:
26                return right_lca, right_depth + 1
27          
28            # If both subtrees have the same depth, then this node is the lowest common ancestor.
29            # Return the current node and the depth of the subtree.
30            return node, left_depth + 1
31
32        # Call the DFS helper function and return the lowest common ancestor. The second value of the tuple is ignored.
33        return dfs(root)[0]
34
1/**
2 * Definition for a binary tree node.
3 */
4public class TreeNode {
5     int val;
6     TreeNode left;
7     TreeNode right;
8     TreeNode() {}
9     TreeNode(int val) { this.val = val; }
10     TreeNode(int val, TreeNode left, TreeNode right) {
11         this.val = val;
12         this.left = left;
13         this.right = right;
14     }
15}
16
17class Solution {
18    /**
19     * Finds the lowest common ancestor (LCA) of the deepest leaves in a binary tree.
20     *
21     * @param root the root of the binary tree.
22     * @return the TreeNode representing the LCA of the deepest leaves.
23     */
24    public TreeNode lcaDeepestLeaves(TreeNode root) {
25        return depthFirstSearch(root).getKey();
26    }
27
28    /**
29     * Helper method to perform depth-first search to find the LCA of the deepest leaves.
30     *
31     * @param node the current node under consideration.
32     * @return a Pair containing the current LCA node and the depth of the subtree rooted at the node.
33     */
34    private Pair<TreeNode, Integer> depthFirstSearch(TreeNode node) {
35        if (node == null) {
36            // Base case: if the current node is null, return a pair of (null, 0)
37            return new Pair<>(null, 0);
38        }
39        // Recursively find the depth and LCA in the left subtree
40        Pair<TreeNode, Integer> leftPair = depthFirstSearch(node.left);
41        // Recursively find the depth and LCA in the right subtree
42        Pair<TreeNode, Integer> rightPair = depthFirstSearch(node.right);
43      
44        int leftDepth = leftPair.getValue(), rightDepth = rightPair.getValue();
45      
46        if (leftDepth > rightDepth) {
47            // If the left subtree is deeper, return the LCA and depth of the left subtree
48            return new Pair<>(leftPair.getKey(), leftDepth + 1);
49        }
50        if (leftDepth < rightDepth) {
51            // If the right subtree is deeper, return the LCA and depth of the right subtree
52            return new Pair<>(rightPair.getKey(), rightDepth + 1);
53        }
54        // If both subtrees have the same depth, the current node is the LCA
55        return new Pair<>(node, leftDepth + 1);
56    }
57}
58
59/**
60 * A helper class to store a pair of objects.
61 *
62 * @param <K> the type of the first element.
63 * @param <V> the type of the second element.
64 */
65class Pair<K, V> {
66    private K key;
67    private V value;
68
69    public Pair(K key, V value) {
70        this.key = key;
71        this.value = value;
72    }
73  
74    public K getKey() {
75        return key;
76    }
77  
78    public V getValue() {
79        return value;
80    }
81}
82
1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    TreeNode() : val(0), left(nullptr), right(nullptr) {}
7    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
9};
10
11class Solution {
12public:
13    // Function to find the lowest common ancestor of the deepest leaves.
14    TreeNode* lcaDeepestLeaves(TreeNode* root) {
15        return depthFirstSearch(root).first;
16    }
17
18    // Helper function to perform depth-first search.
19    // It will return a pair consisting of the lowest common ancestor at the current subtree and the depth of the deepest leaves.
20    pair<TreeNode*, int> depthFirstSearch(TreeNode* node) {
21        if (!node) {
22            // If the node is null, return a pair of nullptr and depth 0.
23            return {nullptr, 0};
24        }
25      
26        // Recursively look for deepest leaves in the left and right subtrees.
27        auto [leftSubtreeLCA, leftDepth] = depthFirstSearch(node->left);
28        auto [rightSubtreeLCA, rightDepth] = depthFirstSearch(node->right);
29      
30        if (leftDepth > rightDepth) {
31            // If the left subtree is deeper, return the left subtree's LCA and depth.
32            return {leftSubtreeLCA, leftDepth + 1};
33        } else if (leftDepth < rightDepth) {
34            // If the right subtree is deeper, return the right subtree's LCA and depth.
35            return {rightSubtreeLCA, rightDepth + 1};
36        } else {
37            // If both subtrees have the same depth, return the current node as the LCA, as both its left and right subtree have the deepest leaves.
38            return {node, leftDepth + 1};
39        }
40    }
41};
42
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// Finds the lowest common ancestor of the deepest leaves in a binary tree.
15function lcaDeepestLeaves(root: TreeNode | null): TreeNode | null {
16    // A depth-first search function that returns both the potential lowest common ancestor and the depth.
17    const depthFirstSearch = (node: TreeNode | null): [TreeNode | null, number] => {
18        // If the current node is null, return null and depth 0.
19        if (node === null) {
20            return [null, 0];
21        }
22        // Recursively find the left and right children's deepest nodes and depths.
23        const [leftAncestor, leftDepth] = depthFirstSearch(node.left);
24        const [rightAncestor, rightDepth] = depthFirstSearch(node.right);
25
26        // If the left subtree is deeper, return the left child's ancestor and increase the depth by 1.
27        if (leftDepth > rightDepth) {
28            return [leftAncestor, leftDepth + 1];
29        }
30        // If the right subtree is deeper, return the right child's ancestor and increase the depth by 1.
31        if (leftDepth < rightDepth) {
32            return [rightAncestor, rightDepth + 1];
33        }
34        // If both subtrees have the same depth, the current node is their lowest common ancestor, depth is increased by 1.
35        return [node, leftDepth + 1];
36    };
37
38    // Start the depth-first search from the root and return the lowest common ancestor.
39    return depthFirstSearch(root)[0];
40}
41
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N) where N is the number of nodes in the tree. This is because the depth-first search (dfs) function visits every node exactly once to calculate the deepest leaf nodes.

Space Complexity

The space complexity of the code is O(H) where H is the height of the tree. This space is used by the recursion stack of the depth-first search. In the worst case (a skewed tree), the space complexity can be 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:

Which type of traversal does breadth first search do?

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

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

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 ๐Ÿ‘จโ€๐Ÿซ