Given the root of a binary tree, return the leftmost value in the last row of the tree.
Example 1:
Input: root = [2,1,3] Output: 1
Example 2:
Input: root = [1,2,3,4,null,5,6,null,null,7] Output: 7
Constraints:
[1, 104].-231 <= Node.val <= 231 - 1Problem Overview: Given the root of a binary tree, return the value of the leftmost node in the last row of the tree. The challenge is identifying the first node that appears at the deepest level while traversing the tree efficiently.
This problem is a classic traversal task on a tree. Since the target node depends on depth and position, both level-order and depth-first traversal strategies work well. The goal is to track which node appears first at the deepest level.
Approach 1: Breadth-First Search (BFS) Level Order Traversal (O(n) time, O(w) space)
Breadth-first traversal processes the tree level by level using a queue. The key idea is that the first node you encounter at each level is the leftmost node. While performing level-order traversal, record the first element of every level and keep updating it as you move deeper. When the traversal finishes, the stored value from the last processed level is the answer.
Implementation uses a queue where each iteration processes all nodes currently in the queue (one level). The first node in that iteration represents the leftmost node for that depth. BFS is intuitive for problems involving level-based properties because it naturally groups nodes by depth. Time complexity is O(n) since every node is visited once, and space complexity is O(w), where w is the maximum width of the tree due to the queue.
This approach relies on Breadth-First Search and is usually the most straightforward way to reason about level-specific values.
Approach 2: Depth-First Search (DFS) with Depth Tracking (O(n) time, O(h) space)
Depth-first traversal explores the tree recursively while tracking the current depth. The trick is to traverse the left subtree before the right subtree and update the answer whenever you encounter a node at a depth greater than any previously visited depth. Because the recursion visits left children first, the first node encountered at a new depth will always be the leftmost node.
You maintain two variables: maxDepth and bottomLeftValue. When the recursion reaches a node deeper than maxDepth, update both variables. Continue exploring the tree until all nodes are processed. This ensures the first node discovered at the deepest level is stored.
This strategy uses Depth-First Search recursion. Time complexity remains O(n) because each node is visited once. Space complexity is O(h), where h is the height of the tree due to the recursion stack. For balanced trees this is O(log n), but in worst-case skewed trees it becomes O(n).
Recommended for interviews: BFS is often the quickest solution to explain because the problem explicitly refers to the "last row" of the tree, which maps directly to level-order traversal. DFS shows deeper understanding of recursion and depth tracking. Strong candidates usually mention both approaches and implement the one they are most comfortable with.
Using a BFS approach, we can efficiently explore each level of the tree from top to bottom. At each level, we keep track of the first value. The leftmost value in the last row will be the first value at the deepest level, which is the last processed level in BFS.
This Python solution uses a queue to perform a BFS. Starting from the root, it processes each level while storing nodes in the queue from right to left. The last processed node's value will be the leftmost node at the deepest level.
Python
C
Java
JavaScript
C#
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) in the worst case, for the queue storing nodes at the deepest level.
For the DFS approach, we explore as deep as possible, preferring left subtrees over right. We track the maximum depth, updating the leftmost value encountered at each depth level. This ensures the leftmost node at the deepest level is found.
This Python DFS solution recursively traverses the tree, increasing depth at each level. Whenever a greater depth is reached, it updates the leftmost value. Left children are processed before right.
Python
C
Java
JavaScript
C#
Time Complexity: O(n), as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to recursive call stack.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n), where n is the number of nodes, as each node is visited once. |
| Depth-First Search (DFS) Approach | Time Complexity: O(n), as each node is visited once. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(w) | Best when reasoning about tree levels or when you want the leftmost node at each depth directly. |
| Depth-First Search with Depth Tracking | O(n) | O(h) | Useful when recursion is preferred or when minimizing auxiliary data structures like queues. |
Find Bottom Left Tree Value - Leetcode 513 - Python • NeetCode • 17,604 views views
Watch 9 more video solutions →Practice Find Bottom Left Tree Value with our built-in code editor and test cases.
Practice on FleetCode