Find Bottom Left Tree Value

▶

Steps

setup

Initialize queue with root node

We start by initializing the queue with the root node (value 2). This sets up the BFS traversal.

💡 Initializing the queue with the root is essential to start the BFS traversal from the top of the tree.

Line:

queue = deque([root])

💡 The queue now contains the root node, ready for BFS processing.

traverse

Pop node 2 from queue to process

We pop the first node (value 2) from the queue to process its children.

💡 Popping the front node simulates visiting nodes level by level in BFS.

Line:

node = queue.popleft()

💡 Node 2 is now the current node being processed.

fill_cells

Add right child (3) of node 2 to queue

Since node 2 has a right child (3), we add it to the queue first to ensure right-to-left processing.

💡 Adding right child first reverses the usual BFS order to track bottom-left node correctly.

Line:

if node.right:
    queue.append(node.right)

💡 Queue order now has node 3 before node 1, reversing normal BFS child insertion order.

fill_cells

Add left child (1) of node 2 to queue

Next, we add the left child (1) of node 2 to the queue after the right child.

💡 Adding left child after right child ensures left nodes are processed last at each level.

Line:

if node.left:
    queue.append(node.left)

💡 Queue now contains nodes [3, 1], ready for next BFS pops.

traverse

Pop node 3 from queue to process

We pop node 3 from the queue to process its children next.

💡 Processing node 3 next follows the right-to-left BFS order.

Line:

node = queue.popleft()

💡 Node 3 is now the current node being processed.

compare

Node 3 has no right child to add

Node 3 does not have a right child, so no node is added to the queue here.

💡 Checking for right child is necessary before adding to queue to avoid errors.

Line:

if node.right:
    queue.append(node.right)

💡 Queue remains unchanged at this step.

compare

Node 3 has no left child to add

Node 3 does not have a left child, so no node is added to the queue here.

💡 Checking for left child is necessary before adding to queue to avoid errors.

Line:

if node.left:
    queue.append(node.left)

💡 Queue remains unchanged at this step.

traverse

Pop node 1 from queue to process

We pop node 1 from the queue to process its children next.

💡 Processing node 1 last at this level ensures leftmost node is processed last.

Line:

node = queue.popleft()

💡 Node 1 is now the current node being processed.

compare

Node 1 has no right child to add

Node 1 does not have a right child, so no node is added to the queue here.

💡 Checking for right child is necessary before adding to queue to avoid errors.

Line:

if node.right:
    queue.append(node.right)

💡 Queue remains unchanged at this step.

compare

Node 1 has no left child to add

Node 1 does not have a left child, so no node is added to the queue here.

💡 Checking for left child is necessary before adding to queue to avoid errors.

Line:

if node.left:
    queue.append(node.left)

💡 Queue is now empty, BFS will end after this step.

reconstruct

Return value of last popped node (1)

The queue is empty, so we return the value of the last popped node, which is 1.

💡 Returning the last popped node value gives the bottom-left node value.

Line:

return node.val

💡 The bottom-left value of the tree is 1.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        queue = deque([root])  # STEP 1: Initialize queue with root
        node = None
        while queue:  # STEP 2-10: BFS loop
            node = queue.popleft()  # STEP 2,5,8: Pop node
            if node.right:  # STEP 3,6,9: Add right child first
                queue.append(node.right)
            if node.left:  # STEP 4,7,10: Add left child second
                queue.append(node.left)
        return node.val  # STEP 11: Return last popped node value

📊

Find Bottom Left Tree Value - Watch the Algorithm Execute, Step by Step

Watching each queue operation and node processing reveals how the algorithm cleverly reverses child insertion order to find the bottom-left node without extra bookkeeping.

213

Current node: 1

213

DFS Stack

1 (entered)

Current node: 1

213

DFS Stack

1 (right_done)

213

Current node: 3

213

DFS Stack

3 (entered)

Current node: 3

213

DFS Stack

3 (right_done)

213

Current node: 2

213

DFS Stack

2 (entered)

Current node: 2

213

DFS Stack

2 (right_done)

213

213

Return: 1

Key Takeaways

✓ The last node popped from the queue in this right-to-left BFS order is the bottom-left node.

This insight is hard to see from code alone because the reversed child insertion order is subtle but critical.

✓ Adding the right child before the left child reverses the BFS order to ensure the leftmost node at the bottom level is processed last.

Visualizing the queue order clarifies why this reversed insertion order works.

✓ When the queue becomes empty, the last popped node's value is returned as the answer.

Seeing the empty queue and final return step together shows how the algorithm terminates and produces the result.

Practice

1. Given a binary tree, you need to return the values of its nodes level by level starting from the bottom-most level up to the root. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Perform a standard level order traversal (BFS) and then reverse the collected levels at the end.

B. Use a depth-first search (DFS) with level tracking to collect nodes per level, then reverse the levels after traversal.

C. Apply a greedy approach by always visiting the right child before the left child to get bottom-up order.

D. Use dynamic programming to store subtrees' bottom-up levels and merge them.

Solution

1. Step 1: Understand problem requirements

   The problem requires collecting nodes level by level from bottom to top, which is not a simple BFS traversal order.

2. Step 2: Identify approach that naturally collects levels bottom-up

   Performing a standard BFS collects nodes level by level from top to bottom. Reversing the collected levels at the end yields the bottom-up order efficiently and straightforwardly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS with reversal is optimal and simple [OK]

Hint: Bottom-up levels are easiest with BFS and reversal [OK]

Common Mistakes:

• Assuming DFS alone gives bottom-up order without reversal
• Using greedy traversal order incorrectly

2. You are given a binary tree and need to find the maximum width among all levels. The width is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), including null nodes in between. Which approach guarantees an optimal solution for this problem?

easy

A. Use BFS with indexing of nodes to track their positions and normalize indices at each level to avoid overflow.

B. Perform a simple level order traversal counting only non-null nodes at each level and take the maximum count.

C. Use DFS to traverse the tree and track the minimum and maximum node indices at each depth to compute width.

D. Apply a greedy approach that always picks the widest subtree at each node to estimate maximum width.

Solution

1. Step 1: Understand the problem constraints

   The width includes null nodes between end-nodes, so counting only non-null nodes per level underestimates width.

2. Step 2: Identify the approach that tracks positions

   BFS with indexing assigns position indices to nodes, allowing calculation of width as the difference between first and last indices at each level. Normalizing indices prevents integer overflow on deep trees.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Indexing with normalization handles sparse trees and deep levels correctly [OK]

Hint: Index nodes with BFS and normalize indices [OK]

Common Mistakes:

• Counting only non-null nodes per level
• Using DFS without proper indexing
• Ignoring index normalization causing overflow

3. What is the time complexity of the optimal BFS approach with indexing and normalization to find the maximum width of a binary tree with n nodes?

medium

A. O(n log n) because of sorting indices at each level

B. O(n) because each node is visited exactly once in BFS

C. O(n^2) due to repeated index normalization at each level

D. O(n) but with extra O(n) space for the queue and index tracking

Solution

1. Step 1: Analyze BFS traversal

   Each node is enqueued and dequeued exactly once, so BFS visits all n nodes in O(n) time.

2. Step 2: Consider index normalization cost

   Index normalization is a constant-time arithmetic operation per node, not sorting or scanning the entire level.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time traversal with constant work per node [OK]

Hint: BFS visits each node once, normalization is O(1) per node [OK]

Common Mistakes:

• Assuming sorting indices per level adds log factor
• Confusing normalization with expensive operations
• Mistaking queue size for nested loops causing O(n^2)

4. Suppose the binary tree nodes can be dynamically added or removed during traversal, or the tree is extremely deep (height > 10^5). Which modification to the level order traversal algorithm is most appropriate to handle these constraints efficiently?

hard

A. Use the recursive DFS with level tracking approach as is, since it handles all cases optimally.

B. Switch to an iterative BFS approach using a queue to avoid recursion stack overflow and handle dynamic changes.

C. Use a naive recursive approach without level tracking and sort nodes by level after traversal.

D. Use a depth-limited DFS that stops at a fixed depth to avoid deep recursion.

Solution

1. Step 1: Identify issues with recursive DFS on very deep trees

   Recursive DFS risks stack overflow on very deep trees and does not handle dynamic changes well.

2. Step 2: Evaluate iterative BFS suitability

   Iterative BFS with a queue avoids recursion stack issues and can handle dynamic node additions/removals during traversal.

3. Step 3: Discard naive and depth-limited approaches

   Naive recursion and sorting is inefficient; depth-limited DFS misses nodes beyond limit.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Iterative BFS is robust for deep or dynamic trees [OK]

Hint: Iterative BFS avoids recursion limits and handles dynamic trees [OK]

Common Mistakes:

• Assuming recursion always works
• Ignoring stack overflow risk
• Using depth limits that lose nodes

5. Suppose the vertical order traversal problem is extended so that nodes can appear multiple times if they have the same column and row but different parents (e.g., in a graph-like structure with shared nodes). Which modification to the BFS with column tracking approach correctly handles this scenario?

hard

A. Modify BFS to track (node, column, row) and store nodes in a list keyed by (column, row), then sort by parent ID

B. Use DFS with sorting by column, row, and parent to order nodes

C. Use BFS with column tracking but ignore row and parent, just append nodes as visited

D. Use BFS with column tracking and a visited set to avoid revisiting nodes

Solution

1. Step 1: Understand problem extension

   Nodes can appear multiple times if they share column and row but differ by parent, so row and parent info must be tracked.

2. Step 2: Evaluate modifications

   Tracking (node, column, row) and sorting by parent ID ensures correct ordering. Ignoring row or parent loses correctness. Visited set prevents duplicates but may skip valid repeats.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tracking row and parent allows correct ordering of duplicates [OK]

Hint: Track row and parent to distinguish duplicates in BFS [OK]

Common Mistakes:

• Ignoring row or parent info leads to incorrect grouping
• Using visited set that skips valid repeated nodes