865. Smallest Subtree with all the Deepest Nodes

MediumTreeDepth-First SearchBreadth-First SearchHash TableBinary Tree
Leetcode Link

Problem Description

The problem requires us to find the smallest subtree in a given binary tree which includes all the deepest nodes. The definition of the depth of a node is the distance from the node to the root of the tree. The deepest nodes are the ones that are the farthest from the root, i.e., they have the highest depth. The subtree must include the node and all of its descendants.

Flowchart Walkthrough

Let's analyze LeetCode 865. Smallest Subtree with all the Deepest Nodes using the Flowchart. Here's a step-by-step walkthrough of decisions:

Is it a graph?

  • Yes: The binary tree can be treated as a graph where each node has edges connecting to its children.

Is it a tree?

  • Yes: This problem specifically involves a tree structure, as it is based on a binary tree.

Following the flowchart:

Is the problem related to finding the Smallest Subtree with all the Deepest Nodes using DFS pattern?

  • Yes: We are looking for a specific subtree, implying a need for a traversal method that examines the structure and properties of tree nodes such as depth.

Conclusion: Since we have concluded that the problem involves a tree and requires an analysis of node properties (depth in this case), the flowchart points us to using DFS (Depth-First Search) for this problem.

Intuition

To solve this problem, we can utilize a depth-first search (DFS) to navigate through the tree. The key is to identify the depth of the deepest nodes and to find the lowest common ancestor (LCA) of all the deepest nodes. Here's the intuition behind the solution:

  1. Start at the root and traverse the tree using DFS.
  2. For each node, calculate the depth of its left and right child recursively.
  3. Compare the depth of the left and right children:
    • If one child is deeper, return that child's node and its depth.
    • If both children are at the same depth, it means this node is the LCA of the deepest nodes (as it's common to all of them), so return the current node and its depth.
  4. The base case for the recursion occurs when we reach a leaf node (no children), where we return the node itself and depth as 0.
  5. Continue this process until all nodes have been visited.
  6. The result of the entire function will be the LCA node where the depth of the left and right subtrees are equal and highest indicating it's the smallest subtree which contains all the deepest nodes.

Using this approach, the dfs function traverses the tree and effectively finds the depths of all nodes, bubbling up the necessary information to identify both the depth of the deepest nodes and the LCA, which is the root of the smallest subtree containing all the deepest nodes.

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

Solution Approach

The implementation of the solution uses a recursive depth-first search (DFS) algorithm to navigate through the binary tree and determine the depths of all nodes, as well as to find the subtree that contains all the deepest nodes.

Here is the step-by-step approach:

  1. DFS Function dfs(root): The helper function dfs is defined within the subtreeWithAllDeepest method. It takes a node (initially the root) as an argument and returns two values: the node itself and the depth of that node. It operates recursively until it hits the base case, which is when root is None. At this point, it returns None for the node and 0 for the depth.

  2. Left and Right Recursion Calls: Within the dfs function, it first calls itself on root.left to explore the left subtree and root.right to explore the right subtree. Each call returns a tuple containing a node and its respective depth.

  3. Comparison of Depths:

    • If the left subtree's depth is greater than the right subtree's depth, the left child node is part of the subtree containing all deepest nodes, and therefore returns the left child node and its depth incremented by 1 (to account for the current node's depth).
    • If the right subtree's depth is greater than the left subtree's depth, the right child node is part of the subtree containing all deepest nodes, and it returns the right child node and its depth incremented by 1.
    • If both depths are equal, it means that the current node is the lowest common ancestor (LCA) of the deepest nodes, as it is at the same distance from the deepest nodes of both subtrees. In this case, it returns the current node and one of the depths incremented by 1.

  4. Returning Result: After traversing the entire tree and applying the above logic at each node, the wrapper function subtreeWithAllDeepest returns the first element of the tuple returned by dfs(root), which is the LCA node of all deepest nodes, hence the root of the smallest subtree containing all the deepest nodes.

By following these steps, the solution provided efficiently uses DFS and concepts of tree depth and Lowest Common Ancestor to arrive at the smallest subtree encompassing all deepest nodes of the binary 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 consider a small binary tree for this walkthrough to illustrate the solution approach:

    3
   / \
  9  20
    /  \
   15   7
         \
          4

In this tree, the deepest nodes are 9, 15, and 4, all with a depth of 2. We need to find the smallest subtree that includes all these nodes. Following the solution approach:

  1. Start DFS with Root (Node 3):

    • dfs(3) is called.
    • Inside dfs, recursive calls will be made for dfs(9) and dfs(20).

  2. DFS on Left Subtree (Node 9):

    • dfs(9) is a leaf node; thus, it returns (9, 1).

  3. DFS on Right Subtree (Node 20):

    • Calls are made to dfs(15) and dfs(7).

  4. DFS on Node 15:

    • It is a leaf node; thus, it returns (15, 1).

  5. DFS on Node 7:

    • Calls are made to its left child (which is None) and dfs(4).
    • dfs(4) is a leaf node; thus, it returns (4, 1).

  6. Comparison of Depths of Children of Node 7:

    • Since node 7's left child is None and the right child has a depth of 1, it returns (4, 2) (depth incremented by 1).

  7. Comparison of Depths of Children of Node 20:

    • dfs(15) returned (15, 1) and dfs(7) returned (4, 2).
    • Since node 7's (right child) subtree is deeper, dfs(20) returns (4, 3) (depth incremented by 1).

  8. Comparison of Depths of Children of Node 3:

    • The left child returned (9, 1) and the right child returned (4, 3).
    • Since the right child is deeper, dfs(3) would return (4, 4).

At this point, it may seem like node 4 is the answer, but we have not yet considered the fact that the answer should include all deepest nodes, not just the deepest one.

  1. However, there's an oversight:

    • When comparing depths of node 3's children, we find the left and right subtrees have unequal depths (1 and 3).
    • According to our solution approach, if both children have the same depth, then the current node is the LCA.
    • But since the depths are different, we mistakenly consider the right subtree to hold all the deepest nodes, which is not the case.

To correct this, we should identify that the node 7 being part of that subtree results in a deeper subtree but doesn't include all the deepest nodes. Hence, while node 4 is the deepest, the subtree rooted at node 3 is the smallest subtree that contains all deepest nodes (9, 15, and 4).

  1. Correcting the Depth Equality Condition:
  • To ensure we are not merely finding the deepest node, we would need to refactor the logic such that, when the depth of the deepest nodes are equal (like for 9, 15, and 4 at depth 2), we return the current node as the LCA.
  • For node 20, as its children nodes 15 and 4 are deepest nodes, it should return (20, 3).
  • For node 3, since its children nodes 9 and 20 include all deepest nodes, it should correctly return (3, 4).

After implementing this correction, the function identifies node 3 as the root of the smallest subtree containing all the deepest nodes (9, 15, and 4), which is what the problem asks for.

In the actual DFS implementation, the comparison step would need to account for this logic to ensure that when there are multiple deepest nodes with equal maximum depth, the node that connects them (their LCA) is returned.

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 subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
10        # Helper function to perform depth-first search and find deepest nodes
11        def depth_first_search(node):
12            # Base case: if the node is None, return None and depth 0
13            if not node:
14                return None, 0
15          
16            # Recursively find the deepest nodes and their depth in the left subtree
17            left_subtree, left_depth = depth_first_search(node.left)
18            # Recursively find the deepest nodes and their depth in the right subtree
19            right_subtree, right_depth = depth_first_search(node.right)
20          
21            # If the left subtree is deeper, return the left subtree and its depth
22            if left_depth > right_depth:
23                return left_subtree, left_depth + 1
24            # If the right subtree is deeper, return the right subtree and its depth
25            elif left_depth < right_depth:
26                return right_subtree, right_depth + 1
27            # If both subtrees have the same depth, return the current node as the common ancestor
28            else:
29                return node, left_depth + 1
30
31        # Call the helper function and return the first element of the tuple,
32        # which is the subtree that contains all the deepest nodes
33        return depth_first_search(root)[0]
34
1import javafx.util.Pair;
2
3// Definition for a binary tree node.
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8
9    TreeNode() {}
10
11    TreeNode(int val) { 
12        this.val = val; 
13    }
14
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23    // Entry method to find the smallest subtree that contains all the deepest nodes.
24    public TreeNode subtreeWithAllDeepest(TreeNode root) {
25        return deepSubtreeDfs(root).getKey();
26    }
27
28    // Helper method that returns the smallest subtree containing all the deepest nodes 
29    // along with the depth of that subtree.
30    private Pair<TreeNode, Integer> deepSubtreeDfs(TreeNode node) {
31        // Base case: if the current node is null, return a pair of null and 0 depth.
32        if (node == null) {
33            return new Pair<>(null, 0);
34        }
35      
36        // Recursively find the pair of subtree and depth for the left child.
37        Pair<TreeNode, Integer> leftPair = deepSubtreeDfs(node.left);
38        // Recursively find the pair of subtree and depth for the right child.
39        Pair<TreeNode, Integer> rightPair = deepSubtreeDfs(node.right);
40      
41        // Depth of left subtree.
42        int leftDepth = leftPair.getValue();
43        // Depth of right subtree.
44        int rightDepth = rightPair.getValue();
45
46        // If left subtree is deeper, return the left child and its depth increased by one.
47        if (leftDepth > rightDepth) {
48            return new Pair<>(leftPair.getKey(), leftDepth + 1);
49        }
50      
51        // If right subtree is deeper, return the right child and its depth increased by one.
52        if (leftDepth < rightDepth) {
53            return new Pair<>(rightPair.getKey(), rightDepth + 1);
54        }
55      
56        // If both subtrees have the same depth, the current node is the LCA of the deepest nodes, 
57        // so return the current node and the depth increased by one.
58        return new Pair<>(node, leftDepth + 1);
59    }
60}
61
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13// Utility type to hold a pair of TreeNode* and int (depth)
14using TreeNodeDepthPair = pair<TreeNode*, int>;
15
16class Solution {
17public:
18    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
19        return depthFirstSearch(root).first;
20    }
21
22    TreeNodeDepthPair depthFirstSearch(TreeNode* node) {
23        // Base case: if the node is null, return pair of nullptr and depth 0
24        if (!node) return {nullptr, 0};
25      
26        // Recursively find the deepest subtree for the left and right children
27        TreeNodeDepthPair leftSubtree = depthFirstSearch(node->left);
28        TreeNodeDepthPair rightSubtree = depthFirstSearch(node->right);
29      
30        // Compare the depths
31        int leftDepth = leftSubtree.second, rightDepth = rightSubtree.second;
32      
33        // If the left subtree is deeper, return the left subtree with depth increased by 1
34        if (leftDepth > rightDepth) return {leftSubtree.first, leftDepth + 1};
35      
36        // If the right subtree is deeper, return the right subtree with depth increased by 1
37        if (leftDepth < rightDepth) return {rightSubtree.first, rightDepth + 1};
38      
39        // If both subtrees have the same depth, the current node is the common ancestor
40        // Return the current node with the increased depth
41        return {node, leftDepth + 1};
42    }
43};
44
1interface TreeNode {
2  val: number;
3  left: TreeNode | null;
4  right: TreeNode | null;
5}
6
7// Type to represent a pair of TreeNode and depth
8type TreeNodeDepthPair = [TreeNode | null, number];
9
10/**
11 * Finds the subtree that contains all the deepest nodes.
12 * @param root - The root of the binary tree.
13 * @returns The subtree with all deepest nodes.
14 */
15function subtreeWithAllDeepest(root: TreeNode | null): TreeNode | null {
16  return depthFirstSearch(root)[0];
17}
18
19/**
20 * Performs a depth-first search to find the deepest subtree.
21 * @param node - The current node in the binary tree.
22 * @returns A tuple containing the deepest subtree and its depth.
23 */
24function depthFirstSearch(node: TreeNode | null): TreeNodeDepthPair {
25  // Base case: if the node is null, return tuple of null and depth 0
26  if (!node) return [null, 0];
27
28  // Recursively find the deepest subtree for the left and right children
29  const leftSubtree: TreeNodeDepthPair = depthFirstSearch(node.left);
30  const rightSubtree: TreeNodeDepthPair = depthFirstSearch(node.right);
31
32  // Extract the depths from the left and right subtree
33  const leftDepth: number = leftSubtree[1], rightDepth: number = rightSubtree[1];
34
35  // If the left subtree is deeper, return the left subtree with depth increased by 1
36  if (leftDepth > rightDepth) return [leftSubtree[0], leftDepth + 1];
37
38  // If the right subtree is deeper, return the right subtree with depth increased by 1
39  if (leftDepth < rightDepth) return [rightSubtree[0], rightDepth + 1];
40
41  // If both subtrees have the same depth, the current node is the common ancestor
42  // Return the current node with the increased depth
43  return [node, leftDepth + 1];
44}
45```
46
47Additionally, a `TreeNode` constructor function may be used to create TreeNode instances in TypeScript:
48
49```typescript
50function createTreeNode(
51  val: number, 
52  left: TreeNode | null = null, 
53  right: TreeNode | null = null
54): TreeNode {
55  return {
56    val,
57    left,
58    right
59  };
60}
61

Time and Space 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 recursive dfs function traverses every node exactly once to compute the depth of the deepest leaves and to find the common ancestor.

The space complexity of the code is also O(N) in the worst case, which occurs in the case of a skewed tree (where each node has only one child except for the leaf node). This is because the recursion stack would then contain N function calls. In the average case of a balanced tree, the space complexity would be O(log N), which corresponds to the height of the tree.

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

Which data structure is used 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

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

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