Find Bottom Left Tree Value
Problem
Given the root of a binary tree, return the leftmost value in the last row (deepest level).
tree = [2, 1, 3, 4, null, 5, 6, 7]7from collections import deque
def find_bottom_left_value(root):
q = deque([root])
node = root
while q:
node = q.popleft()
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
return node.valfunction findBottomLeftValue(root) {
const q = [root];
let node = root;
while (q.length) {
node = q.shift();
if (node.right) q.push(node.right);
if (node.left) q.push(node.left);
}
return node.val;
}class Solution {
public int findBottomLeftValue(TreeNode root) {
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
TreeNode node = root;
while (!q.isEmpty()) {
node = q.poll();
if (node.right != null) q.offer(node.right);
if (node.left != null) q.offer(node.left);
}
return node.val;
}
}int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
TreeNode* node = root;
while (!q.empty()) {
node = q.front(); q.pop();
if (node->right) q.push(node->right);
if (node->left) q.push(node->left);
}
return node->val;
}Explanation
We want the leftmost value on the deepest level. A normal BFS would need to track levels and remember the first node of each row. There's a slicker trick that skips all that bookkeeping.
The idea is to do a BFS but enqueue right before left. With that ordering, the queue always drains a level from right to left, and the very last node we dequeue in the whole traversal is the leftmost node of the bottom row.
So the loop is tiny: pop a node into node, push its right child, then its left child. We keep overwriting node on every step. When the queue empties, node is exactly the answer.
Why does this work? The deepest level is processed last, and because we always added right children ahead of left ones, the left side of that last level comes out at the very end.
Example: [2, 1, 3, 4, null, 5, 6, 7]. The deepest level contains only node 7, and since it is the final node dequeued, the function returns 7.