NeetCode #455LC-513MediumTrees
← Back to All Problems#455 · #513 · Find Bottom Left Tree Value(找树左下角的值)
📌 Problem Statement & Constraints
Given the root of a binary tree, return the value of the bottom-left node: the leftmost node in the deepest level. Constraints: the number of nodes is in
[1, 10^4], -2^31 <= Node.val <= 2^31 - 1.💡 Core Algorithmic Approaches
- A level-order traversal that records the first node of each level gives the answer after the loop, since the last recorded value belongs to the deepest level.
- Alternatively, a DFS that goes right-then-left and records the last node seen at a new depth works too.
- BFS is the most direct: keep updating the answer with
level[0]. - Both are O(n).
💻 Benchmark Python3 Implementation
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
from collections import deque
q = deque([root])
res = root.val
while q:
n = len(q)
for i in range(n):
node = q.popleft()
if i == 0: # leftmost node of this level
res = node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res # the last level's leftmost value
# DFS variant: visit right first, so the last new depth recorded is the leftmost
class Solution2:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
self.res = root.val
self.max_depth = -1
def dfs(node: Optional[TreeNode], depth: int) -> None:
if not node:
return
if depth > self.max_depth: # first node seen at a deeper level
self.max_depth = depth
self.res = node.val
dfs(node.left, depth + 1) # left first -> leftmost wins ties
dfs(node.right, depth + 1)
dfs(root, 0)
return self.res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(w) for the BFS queue, or O(h) for the DFS recursion.
⚠️ Interview Pitfalls & Follow-ups
- Recording the last node of each level: that gives the bottom-right value.
- Using
i == n - 1: same issue; the leftmost is at index 0. - Assuming the tree is complete: the bottom-left node is defined by the deepest level, whatever its shape.
- In the DFS variant, visiting right before left: the rightmost node would win ties.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.