⚡Flashcard Drill➔
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

  1. 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.
  2. Alternatively, a DFS that goes right-then-left and records the last node seen at a new depth works too.
  3. BFS is the most direct: keep updating the answer with level[0].
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems