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 - 1In #513 Find Bottom Left Tree Value, the goal is to determine the value of the leftmost node in the last row of a binary tree. Since the problem focuses on the deepest level, traversal strategies work well.
A common strategy is Breadth-First Search (BFS) using a queue. By processing the tree level by level, you can track the first node encountered at each level. The first node in the final level will represent the required value. Another effective approach is Depth-First Search (DFS). During recursion, maintain the current depth and update the answer whenever you encounter a node at a deeper level than previously seen, prioritizing the left child before the right child.
Both approaches ensure every node is visited once, making them efficient for binary tree traversal problems. The key idea is correctly tracking depth or level order while ensuring the leftmost node is captured.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(n) |
| Depth-First Search (Recursive) | O(n) | O(h) |
NeetCode
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.
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.
1from collections import deque
2
3def findBottomLeftValue(root):
4 queue = deque([root])
5 while queue:
6 node = queue.popleft()
7 if node.right:
8 queue.append(node.right)
9 if node.left:
10 queue.append(node.left)
11 return node.valThis 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.
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.
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.
1public class Solution {
2 private int maxDepth = -1;
private int leftmostValue;
public int FindBottomLeftValue(TreeNode root) {
leftmostValue = root.val;
DFS(root, 0);
return leftmostValue;
}
private void DFS(TreeNode node, int depth) {
if (node == null) return;
if (depth > maxDepth) {
maxDepth = depth;
leftmostValue = node.val;
}
DFS(node.left, depth + 1);
DFS(node.right, depth + 1);
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
BFS processes nodes level by level, which aligns perfectly with finding values at the deepest level of the tree. By observing the first node at each level, you can easily identify the leftmost node of the final level.
Yes, variations of this problem appear in coding interviews at major tech companies. Interviewers often use it to evaluate understanding of binary tree traversal, recursion, and the ability to reason about levels and depth in trees.
A queue is commonly used when implementing the BFS approach because it supports level-order traversal of the tree. For the DFS approach, recursion and the call stack are used along with variables to track depth and the current leftmost value.
The optimal approaches are Breadth-First Search (level-order traversal) or Depth-First Search with depth tracking. BFS naturally processes nodes level by level, making it easy to capture the first node at each level, while DFS tracks the deepest leftmost node during recursion.
This C# solution integrates recursive DFS to oversee the traversal, adjusting leftmost value upon surpassing previous maximal depth at newfound levels, preferring left nodes initially.