Find Largest Value in Each Tree Row

▶

Steps

setup

Initialize queue with root node

The algorithm starts by checking if the root is null. Since it is not, it initializes the result list and the queue with the root node (value 1).

💡 Initializing the queue with the root node sets up the BFS traversal starting point.

Line:

res = []
queue = deque([root])

💡 The queue will control the order of node processing, starting from the root.

fill_row

Start processing level 0

The algorithm notes the current queue length (1) as the number of nodes at level 0 and initializes level_max to negative infinity.

💡 Knowing the number of nodes at the current level lets us process exactly that many nodes before moving to the next level.

Line:

level_max = float('-inf')
for _ in range(len(queue)):

💡 This step sets up the boundary for processing all nodes at the current level.

fill_cells

Process node 1 at level 0

Node 1 is dequeued from the queue. The level_max is updated from -inf to 1, the value of node 1. Its children nodes 2 and 3 are enqueued.

💡 Processing each node updates the max value for the level and queues children for the next level.

Line:

node = queue.popleft()
level_max = max(level_max, node.val)
if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 The max value for the level is updated as nodes are processed, and children are prepared for the next level.

fill_row

Finish level 0 and append max

All nodes at level 0 have been processed. The maximum value found (1) is appended to the result list.

💡 Appending the max value after processing the entire level records the largest value for that row.

Line:

res.append(level_max)

💡 The result list grows level by level, capturing the largest values.

fill_row

Start processing level 1

The algorithm notes the queue length (2) for level 1 nodes and resets level_max to negative infinity for this new level.

💡 Resetting level_max is necessary to find the max value for the new level independently.

Line:

level_max = float('-inf')
for _ in range(len(queue)):

💡 Each level's max is tracked separately to avoid mixing values across levels.

fill_cells

Process node 2 at level 1

Node 2 (value 3) is dequeued. level_max updates from -inf to 3. Its children nodes 4 and 5 are enqueued for the next level.

💡 Processing nodes updates the max and queues children for the next level.

Line:

node = queue.popleft()
level_max = max(level_max, node.val)
if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 The max value for the level updates as nodes are processed.

fill_cells

Process node 3 at level 1

Node 3 (value 2) is dequeued. level_max remains 3 since max(3,2) = 3. It has no left child but has right child node 6, which is enqueued.

💡 Even if a node's value is smaller, it does not change the max. Children are still enqueued if present.

Line:

node = queue.popleft()
level_max = max(level_max, node.val)
if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 Max tracking ignores smaller values but children are always enqueued if they exist.

fill_row

Finish level 1 and append max

All nodes at level 1 have been processed. The maximum value found (3) is appended to the result list.

💡 Appending the max value after processing the entire level records the largest value for that row.

Line:

res.append(level_max)

💡 The result list now contains max values for levels 0 and 1.

fill_row

Start processing level 2

The algorithm notes the queue length (3) for level 2 nodes and resets level_max to negative infinity for this new level.

💡 Resetting level_max is necessary to find the max value for the new level independently.

Line:

level_max = float('-inf')
for _ in range(len(queue)):

💡 Each level's max is tracked separately to avoid mixing values across levels.

fill_cells

Process node 4 at level 2

Node 4 (value 5) is dequeued. level_max updates from -inf to 5. It has no children, so nothing is enqueued.

💡 Leaf nodes update max but do not add children to the queue.

Line:

node = queue.popleft()
level_max = max(level_max, node.val)
if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 Leaf nodes contribute to max but do not extend the queue.

fill_cells

Process node 5 at level 2

Node 5 (value 3) is dequeued. level_max remains 5 since max(5,3) = 5. It has no children.

💡 Max value only updates if current node's value is larger.

Line:

node = queue.popleft()
level_max = max(level_max, node.val)

💡 Max tracking ignores smaller values.

fill_cells

Process node 6 at level 2

Node 6 (value 9) is dequeued. level_max updates from 5 to 9. It has no children.

💡 A larger value updates the max for the level.

Line:

node = queue.popleft()
level_max = max(level_max, node.val)

💡 Max tracking captures the largest value in the level.

fill_row

Finish level 2 and append max

All nodes at level 2 have been processed. The maximum value found (9) is appended to the result list.

💡 Appending the max value after processing the entire level records the largest value for that row.

Line:

res.append(level_max)

💡 The result list now contains max values for all levels.

reconstruct

Queue empty, return result

The queue is empty, meaning all levels have been processed. The algorithm returns the result list containing the largest values per level.

💡 Returning the result ends the BFS traversal and provides the final answer.

Line:

return res

💡 The BFS traversal completes when no more nodes remain to process.

from collections import deque
from typing import Optional, List

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

def largestValues(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []  # STEP 1: Check for empty tree
    res = []  # STEP 1: Initialize result list
    queue = deque([root])  # STEP 1: Initialize queue with root
    while queue:  # STEP 2: While there are nodes to process
        level_max = float('-inf')  # STEP 2: Reset max for current level
        for _ in range(len(queue)):  # STEP 2: Process all nodes at current level
            node = queue.popleft()  # STEP 3: Dequeue node
            level_max = max(level_max, node.val)  # STEP 3: Update max
            if node.left:  # STEP 3: Enqueue left child if exists
                queue.append(node.left)
            if node.right:  # STEP 3: Enqueue right child if exists
                queue.append(node.right)
        res.append(level_max)  # STEP 4: Append max of level to result
    return res  # STEP 5: Return final result

# Example usage:
root = TreeNode(1,
                TreeNode(3, TreeNode(5), TreeNode(3)),
                TreeNode(2, null, TreeNode(9)))
print(largestValues(root))  # Output: [1, 3, 9]

📊

Find Largest Value in Each Tree Row - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each node and level makes it clear how BFS explores the tree and how the largest values per row are found without missing any nodes.

132539

BFS Queue

N1 (L0)

132539

BFS Queue

N1 (L0)

Current node: 1

132539

BFS Queue

N2 (L1)N3 (L1)

132539

BFS Queue

N2 (L1)N3 (L1)

Result: [1]

132539

BFS Queue

N2 (L1)N3 (L1)

Result: [1]

Current node: 2

132539

BFS Queue

N3 (L1)N4 (L2)N5 (L2)

Result: [1]

Current node: 3

132539

BFS Queue

N4 (L2)N5 (L2)N6 (L2)

Result: [1]

132539

BFS Queue

N4 (L2)N5 (L2)N6 (L2)

Result: [1, 3]

132539

BFS Queue

N4 (L2)N5 (L2)N6 (L2)

Result: [1, 3]

Current node: 4

132539

BFS Queue

N5 (L2)N6 (L2)

Result: [1, 3]

Current node: 5

132539

BFS Queue

N6 (L2)

Result: [1, 3]

Current node: 6

132539

Result: [1, 3]

132539

Result: [1, 3, 9]

132539

Result: [1, 3, 9]

Return: [1,3,9]

Key Takeaways

✓ BFS processes nodes level by level, allowing easy aggregation of values per row.

This insight is hard to see from code alone because the queue operations and level boundaries are implicit without visualization.

✓ Tracking the max value inline during level traversal avoids extra passes or storage.

Seeing max update step-by-step clarifies how the algorithm efficiently finds the largest value without sorting or extra data structures.

✓ Enqueuing children as nodes are processed ensures the next level is ready for traversal.

The trace shows how BFS naturally expands the frontier, which can be confusing when reading code without seeing the queue state.

Practice

1. You need to find the visible nodes when looking at a binary tree from the right side, returning the nodes that appear at each depth level from top to bottom. Which approach guarantees an optimal solution that captures the rightmost nodes at each level efficiently?

easy

A. Perform a DFS traversal visiting right child first and add the first node encountered at each depth level.

B. Use a BFS traversal but add the first node encountered at each level instead of the last.

C. Perform a DFS traversal visiting left child first and overwrite the node value at each depth level.

D. Use a BFS traversal and collect all nodes at each level, then pick the leftmost node.

Solution

1. Step 1: Understand traversal order impact

   Visiting the right child first ensures the first node encountered at each depth is the rightmost node visible from the right side.

2. Step 2: Why first node per level matters

   By adding the first node at each depth, we avoid overwriting with left nodes that are hidden behind right nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Right-first DFS captures rightmost nodes without overwriting [OK]

Hint: Right-first DFS adds first node per level [OK]

Common Mistakes:

• Visiting left child first and overwriting nodes causes left nodes to replace right nodes
• Using BFS but picking first node instead of last at each level
• Collecting leftmost nodes instead of rightmost

2. Consider the following Python code for vertical order traversal of a binary tree:

from collections import deque
from sortedcontainers import SortedDict

def verticalOrder(root):
    if not root:
        return []
    col_table = SortedDict()
    queue = deque([(root, 0)])
    while queue:
        node, col = queue.popleft()
        if col not in col_table:
            col_table[col] = []
        col_table[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return list(col_table.values())

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

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(verticalOrder(root))

What is the output of this code?

easy

A. [[9], [3, 15], [20], [7]]

B. [[9], [3, 20, 15], [7]]

C. [[9], [3], [15, 20], [7]]

D. [[9], [3], [20, 15], [7]]

Solution

1. Step 1: Trace queue and col_table updates

   Start with root (3, col=0). Append 3 to col 0. Enqueue left child (9, col=-1), right child (20, col=1).

2. Step 2: Process nodes in BFS order

   Process (9, -1): append 9 to col -1. No children. Process (20, 1): append 20 to col 1. Enqueue (15, 0), (7, 2). Process (15, 0): append 15 to col 0. Process (7, 2): append 7 to col 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Columns sorted: -1:[9], 0:[3,15], 1:[20], 2:[7] matches [[9], [3, 15], [20], [7]] [OK]

Hint: BFS preserves top-to-bottom order in each column [OK]

Common Mistakes:

• Mixing order of nodes in same column
• Misassigning column indices for children

3. What is the time complexity of the optimal BFS with column tracking and ordered map approach for vertical order traversal of a binary tree with n nodes and k distinct columns?

medium

A. O(n log n)

B. O(n)

C. O(n log k)

D. O(k log n)

Solution

1. Step 1: Identify main operations

   Each node is processed once (O(n)). For each node, insertion into ordered map (SortedDict) costs O(log k) where k is number of columns.

2. Step 2: Combine complexities

   Total time is O(n) * O(log k) = O(n log k). Sorting all nodes (O(n log n)) is avoided here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Ordered map insertion dominates, giving O(n log k) [OK]

Hint: Ordered map insertion per node costs log k, not log n [OK]

Common Mistakes:

• Assuming O(n) ignoring map insertion cost
• Confusing k (columns) with n (nodes) in complexity

4. Suppose the problem changes: instead of finding the minimum depth to any leaf, you must find the minimum depth to a leaf node with a specific target value. Which modification to the BFS approach is correct?

hard

A. Continue BFS until the first leaf is found, then check if its value matches target; if not, continue BFS

B. Use DFS to explore all paths and return the minimum depth of leaves matching the target value

C. Modify BFS to enqueue only nodes whose values are less than or equal to the target value

D. Stop BFS at the first node with the target value, regardless of whether it is a leaf

Solution

1. Step 1: Understand the new requirement

   We want the minimum depth to a leaf node with a specific value, not just any leaf.

2. Step 2: Modify BFS to check leaf value before returning

   BFS should stop only when it finds a leaf node whose value matches the target; otherwise, continue searching.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS guarantees shortest path; checking leaf value before stopping is correct [OK]

Hint: BFS with conditional leaf check for target value [OK]

Common Mistakes:

• Stopping at first leaf regardless of value
• Pruning BFS incorrectly by node values
• Switching to DFS losing BFS optimality

5. Suppose the problem is extended so that the tree nodes can have multiple children (not just binary), and you need to check if the tree is symmetric around its center. Which modification to the BFS approach is necessary to correctly handle this case?

hard

A. Enqueue children in normal order and compare corresponding children pairs directly

B. Enqueue children in mirrored order and compare pairs from opposite ends of the children list

C. Use a recursive approach only, as BFS cannot handle multiple children

D. Check symmetry only at the root level and ignore deeper levels

Solution

1. Step 1: Understand symmetry in multi-child trees

   Symmetry means the first child on the left subtree mirrors the last child on the right subtree, second mirrors second last, etc.

2. Step 2: Modify BFS to enqueue children in mirrored order

   Enqueue children pairs from opposite ends of the children list to compare mirrored positions correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Mirrored enqueue order for multiple children preserves symmetry checks [OK]

Hint: Multi-child symmetry requires mirrored child pair comparisons [OK]

Common Mistakes:

• Enqueuing children in normal order causing false positives
• Assuming BFS cannot be adapted for multi-child trees
• Ignoring deeper levels of the tree