Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.
Recall that:
0. if the depth of a node is d, the depth of each of its children is d + 1.S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.
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 leaf-nodes of the tree. Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.
Example 2:
Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree, and it's the lca of itself.
Example 3:
Input: root = [0,1,3,null,2] Output: [2] Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.
Constraints:
[1, 1000].0 <= Node.val <= 1000
Note: This question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
This approach involves recursively finding the depth of the subtree at each node and returning the LCA of the deepest leaves.
The main idea is to perform a post-order traversal to determine the depth of left and right subtrees. If the depths are equal, the current node is the LCA. If the left subtree is deeper, recursively find the LCA in the left subtree, and similarly for the right subtree.
The code uses a depth-first search (DFS) to determine the depth of each subtree while simultaneously working out the LCA. The `dfs` function returns the maximum depth of the subtree and updates the `lca` when it finds a subtree with nodes as deep as the deepest nodes found so far, making this node the current LCA.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(H), where H is the height of the tree, representing the call stack in the worst-case scenario.
Instead of recursive DFS, another approach is to use Breadth-First Search (BFS) to traverse levels of the tree iteratively, keeping track of the nodes at the deepest level. This level-based traversal ensures we gather all deepest leaves in a set. Finally, we use a standard method to determine LCA from this set of nodes.
This C code uses basic queue operations to perform level-order traversal. The deepest leaves are at the end of traversal, thus, by tracking the last fully processed level in the queue, the common ancestor can be concluded.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), as each node is enqueued and dequeued once.
Space Complexity: O(N), associated with the storage requirements of the queue.
| Approach | Complexity |
|---|---|
| Recursive Deepest Leaves and LCA | Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited once. Space Complexity: O(H), where H is the height of the tree, representing the call stack in the worst-case scenario. |
| Iterative Deepest Leaves and LCA using BFS | Time Complexity: O(N), as each node is enqueued and dequeued once. Space Complexity: O(N), associated with the storage requirements of the queue. |
Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Python • NeetCode • 274,690 views views
Watch 9 more video solutions →Practice Lowest Common Ancestor of Deepest Leaves with our built-in code editor and test cases.
Practice on FleetCode