Given the root of a binary tree, the depth of each node is the shortest distance to the root.
Return the smallest subtree such that it contains all the deepest nodes in the original tree.
A node is called the deepest if it has the largest depth possible among any node in the entire tree.
The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4] Explanation: We return the node with value 2, colored in yellow in the diagram. The nodes coloured in blue are the deepest nodes of the tree. Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.
Example 2:
Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree.
Example 3:
Input: root = [0,1,3,null,2] Output: [2] Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.
Constraints:
[1, 500].0 <= Node.val <= 500
Note: This question is the same as 1123: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
This approach leverages DFS to determine the depth of each node while recursively finding the subtree containing all the deepest nodes. By tracking depth, we can identify the lowest common ancestor of the deepest nodes, which will be the root of the smallest subtree containing them all.
The Python solution defines a DFS function that recursively traverses the tree, returning the lowest common ancestor and the maximum depth found. At each node, the function compares the maximum depths of its left and right children. If both have equal depth, the current node is part of the smallest subtree containing all deepest nodes.
Java
C++
C
C#
JavaScript
Time Complexity: O(N), since all nodes must be visited.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.
This solution calculates the height of the tree nodes starting from the leaves (bottom-up). By evaluating the heights of left and right subtrees, the method determines the lowest common ancestor (LCA) of the deepest nodes, thereby identifying the desired subtree.
The Python solution defines a helper function `height` to recursively compute the height from each node and a function `lcaDeepestLeaves` to find the node acting as the common ancestor of the deepest leaves. Comparisons between left and right heights guide the decision toward the correct subtree.
Java
C++
C
C#
JavaScript
Time Complexity: O(N^2) in the worst case due to repeated height calculations.
Space Complexity: O(H), corresponding to recursion use by `height` method.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) with Depth Calculation | Time Complexity: O(N), since all nodes must be visited. |
| Bottom-Up Approach Using Tree Height and LCA | Time Complexity: O(N^2) in the worst case due to repeated height calculations. |
Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Python • NeetCode • 274,690 views views
Watch 9 more video solutions →Practice Smallest Subtree with all the Deepest Nodes with our built-in code editor and test cases.
Practice on FleetCode