Find Bottom Left Tree Value — Solution in Python, Java & C++
Find Bottom Left Tree Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find Bottom Left Tree Value is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a non-empty binary tree, return the value of the leftmost node in its last row — among the nodes at the greatest depth, the one furthest to the left.
Example 1
Input: root = [2,1,3]
Output: 1
Explanation: The last row is 1, 3; its leftmost value is 1.
Example 2
Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7
Explanation: The deepest row holds only 7, the left child of 5.
Example 3
Input: root = [1,null,2,3,4]
Output: 3
Explanation: The bottom row is 3, 4 — both in the root's right subtree. The leftmost node of the last row need not be a left child of anything near the root.
Constraints
The number of nodes in the tree is in the range [1, 10^4]-2^31 <= Node.val <= 2^31 - 1
Hints for Find Bottom Left Tree Value
Hint 1
A level-order (breadth-first) walk visits the tree row by row, each row from left to right.
Hint 2
The first node of the last row is the answer — so remember the first value of every row; the last one remembered wins.
Hint 3
A neat variant: walk each row right to left (enqueue the right child before the left). Then the very last node dequeued is the answer.
How to solve Find Bottom Left Tree Value
Breadth-first search processes the tree one row at a time. If each row is processed from right to left, the final node taken off the queue lies in the deepest row and is the leftmost one there.
Approach
- Put the root in a queue.
- Repeatedly dequeue a node, record its value, then enqueue its right child and then its left child (when present).
- When the queue is empty, the last recorded value is the answer.
Why it works
BFS dequeues all nodes of one depth before any node of the next depth, so the last node dequeued is in the deepest row. Within a row, enqueuing right before left makes the row come out right to left, so the last node of the deepest row is its leftmost.
Complexity
- Time —
O(n) - Space —
O(w), where w is the widest row — O(n) at worst
Pitfalls
- The answer is the leftmost node of the deepest row, not the deepest node reached by always going left.
- Values span the whole 32-bit range; never use a value such as 0 or -1 as a 'not found' marker.
Reference solution
Python
from collections import deque
from typing import Optional
def findBottomLeftValue(root: Optional[TreeNode]) -> int:
queue = deque([root])
ans = root.val
while queue:
node = queue.popleft()
ans = node.val
if node.right is not None:
queue.append(node.right)
if node.left is not None:
queue.append(node.left)
return ansJava
public static int findBottomLeftValue(TreeNode root) {
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int ans = root.val;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
ans = node.val;
if (node.right != null) queue.add(node.right);
if (node.left != null) queue.add(node.left);
}
return ans;
}C++
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int ans = root->val;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
ans = node->val;
if (node->right) q.push(node->right);
if (node->left) q.push(node->left);
}
return ans;
}JavaScript
var findBottomLeftValue = function(root) {
var queue = [root], head = 0, ans = root.val;
while (head < queue.length) {
var node = queue[head++];
ans = node.val;
if (node.right !== null) queue.push(node.right);
if (node.left !== null) queue.push(node.left);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)