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.
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8} TreeNode;
9
10int findBottomLeftValue(TreeNode* root) {
11 TreeNode** queue = (TreeNode**)malloc(sizeof(TreeNode*) * 10000);
12 int front = 0, rear = 0;
13 queue[rear++] = root;
14 TreeNode* node;
15 while (front < rear) {
16 node = queue[front++];
17 if (node->right) queue[rear++] = node->right;
18 if (node->left) queue[rear++] = node->left;
19 }
20 free(queue);
21 return node->val;
22}This C solution implements a BFS using a dynamically allocated array to simulate a queue. Nodes are enqueued right-to-left at each level, ensuring the last node processed is the leftmost 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.
1#include
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 implements DFS via recursion, carrying along depth and maximal depth pointers, modifying leftmost value at maximum depth, favoring left traversals first.