Find Largest Value in Each Tree Row

🎯

Find Largest Value in Each Tree Row

mediumTREEAmazonGoogleFacebook

Imagine you are analyzing a forest canopy and want to find the tallest tree visible at each horizontal layer. This problem mimics that by finding the largest value at each level of a binary tree.

💡 This problem is a classic example of level order traversal (BFS) on trees. Beginners often struggle because they may not know how to traverse level-by-level or how to aggregate values per level efficiently.

📋

Problem Statement

Given the root of a binary tree, return an array of the largest value in each row (level) of the tree. The root is considered level 0, its children level 1, and so on.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers in the range [-2^31, 2^31 - 1].

💡

Example

Input"root = [1,3,2,5,3,null,9]"

Output[1, 3, 9]

Level 0 has value 1, level 1 has values 3 and 2 (max 3), level 2 has values 5, 3, and 9 (max 9).

• Single node tree → output is the root value
• All nodes have the same value → output is repeated value per level
• Tree is skewed (all left or all right) → output is values along that path
• Tree with negative values → output correctly handles negatives

⚠️

Common Mistakes

Not tracking levels correctly in DFS

Incorrect max values or index errors in result list

✅ Pass level parameter correctly and check if level exists in result before updating

Using BFS but not processing nodes level by level

Mixing values from different levels, wrong max values

✅ Use a loop over current queue size to isolate each level's nodes

Forgetting to check for null children before enqueueing

Runtime errors or infinite loops

✅ Always check if child node is not null before adding to queue

Using global variables without resetting between test cases

Incorrect results when running multiple tests

✅ Initialize result containers inside function scope

🧠

Brute Force (DFS with Level Tracking)

💡 This approach uses a simple depth-first search to explore all nodes, tracking the level to update the maximum value per level. It is intuitive but less efficient than BFS for this problem.

Intuition

Traverse the tree recursively, passing the current level. For each node, update the maximum value found so far at that level.

Algorithm

1. Initialize an empty list to store max values per level.
2. Define a recursive DFS function that takes a node and its level.
3. If the current level is not yet in the list, append the node's value.
4. Otherwise, update the max value for that level if current node's value is larger.
5. Recursively call DFS on left and right children with level + 1.
6. Return the list of max values after traversal.

💡 The recursion and level tracking can be tricky to visualize at first, but it ensures every node is visited exactly once.

</>

Code

from typing import Optional, List

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

def largestValues(root: Optional[TreeNode]) -> List[int]:
    res = []
    def dfs(node, level):
        if not node:
            return
        if level == len(res):
            res.append(node.val)
        else:
            res[level] = max(res[level], node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return res

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

Line Notes

def dfs(node, level):Defines recursive helper to traverse nodes with current level info

if not node:Base case to stop recursion at leaf's child

if level == len(res):First time visiting this level, so append current node's value

res[level] = max(res[level], node.val)Update max value for this level if current node's value is larger

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }
    private void dfs(TreeNode node, int level, List<Integer> res) {
        if (node == null) return;
        if (level == res.size()) {
            res.add(node.val);
        } else {
            res.set(level, Math.max(res.get(level), node.val));
        }
        dfs(node.left, level + 1, res);
        dfs(node.right, level + 1, res);
    }

    // Example usage
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);
        Solution sol = new Solution();
        System.out.println(sol.largestValues(root)); // Output: [1, 3, 9]
    }
}

Line Notes

private void dfs(TreeNode node, int level, List<Integer> res)Recursive DFS helper with level and result list

if (node == null) return;Stops recursion at null nodes

if (level == res.size()) {First time visiting this level, add node's value

res.set(level, Math.max(res.get(level), node.val));Update max value for this level if current node's value is larger

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void dfs(TreeNode* node, int level, vector<int>& res) {
    if (!node) return;
    if (level == (int)res.size()) {
        res.push_back(node->val);
    } else {
        res[level] = max(res[level], node->val);
    }
    dfs(node->left, level + 1, res);
    dfs(node->right, level + 1, res);
}

vector<int> largestValues(TreeNode* root) {
    vector<int> res;
    dfs(root, 0, res);
    return res;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);
    vector<int> result = largestValues(root);
    for (int val : result) cout << val << " ";
    cout << endl; // Output: 1 3 9
    return 0;
}

Line Notes

void dfs(TreeNode* node, int level, vector<int>& res)DFS helper with level and reference to result vector

if (!node) return;Base case to stop recursion at null nodes

if (level == (int)res.size()) {First time visiting this level, push current node's value

res[level] = max(res[level], node->val);Update max value for this level if current node's value is larger

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function largestValues(root) {
    const res = [];
    function dfs(node, level) {
        if (!node) return;
        if (level === res.length) {
            res.push(node.val);
        } else {
            res[level] = Math.max(res[level], node.val);
        }
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return res;
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(3, new TreeNode(5), new TreeNode(3)),
    new TreeNode(2, null, new TreeNode(9))
);
console.log(largestValues(root)); // Output: [1, 3, 9]

Line Notes

function dfs(node, level) {Recursive DFS helper with current node and level

if (!node) return;Stops recursion when node is null

if (level === res.length) {First time visiting this level, add node's value

res[level] = Math.max(res[level], node.val);Update max value for this level if current node's value is larger

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, so time is O(n). Space is O(h) due to recursion stack, where h is tree height.

💡 For a tree with 20 nodes, this means about 20 operations and stack depth up to 20 in worst case.

Interview Verdict: Accepted

This approach is accepted but recursion stack can be large for skewed trees; still good for understanding.

🧠

Level Order Traversal Using Queue (BFS)

💡 This approach uses a queue to traverse the tree level by level, which naturally fits the problem of processing nodes per row.

Intuition

Use a queue to process nodes in FIFO order, at each level find the max value among all nodes in that level before moving to the next.

Algorithm

1. Initialize a queue and add the root node.
2. While the queue is not empty, process all nodes currently in the queue (one level).
3. Track the maximum value among these nodes.
4. Add their children to the queue for the next level.
5. Append the maximum value found to the result list.
6. Return the result list after processing all levels.

💡 The key is to process nodes level by level, which the queue naturally supports.

</>

Code

from collections import deque
from typing import Optional, List

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

def largestValues(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_max = float('-inf')
        for _ in range(level_size):
            node = queue.popleft()
            level_max = max(level_max, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level_max)
    return res

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

Line Notes

queue = deque([root])Initialize queue with root to start BFS

while queue:Process nodes level by level until queue is empty

for _ in range(level_size):Iterate over all nodes in current level

level_max = max(level_max, node.val)Track max value in current level

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int levelMax = Integer.MIN_VALUE;
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelMax = Math.max(levelMax, node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            res.add(levelMax);
        }
        return res;
    }

    // Example usage
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);
        Solution sol = new Solution();
        System.out.println(sol.largestValues(root)); // Output: [1, 3, 9]
    }
}

Line Notes

Queue<TreeNode> queue = new LinkedList<>();Initialize queue for BFS traversal

while (!queue.isEmpty()) {Process nodes level by level until queue is empty

for (int i = 0; i < levelSize; i++) {Iterate over all nodes in current level

levelMax = Math.max(levelMax, node.val);Track max value in current level

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> largestValues(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();
        int levelMax = INT_MIN;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            levelMax = max(levelMax, node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(levelMax);
    }
    return res;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);
    vector<int> result = largestValues(root);
    for (int val : result) cout << val << " ";
    cout << endl; // Output: 1 3 9
    return 0;
}

Line Notes

queue<TreeNode*> q;Queue to hold nodes for BFS traversal

while (!q.empty()) {Process nodes level by level until queue is empty

for (int i = 0; i < levelSize; i++) {Iterate over all nodes in current level

levelMax = max(levelMax, node->val);Track max value in current level

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function largestValues(root) {
    if (!root) return [];
    const res = [];
    const queue = [root];
    while (queue.length > 0) {
        const levelSize = queue.length;
        let levelMax = -Infinity;
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            levelMax = Math.max(levelMax, node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        res.push(levelMax);
    }
    return res;
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(3, new TreeNode(5), new TreeNode(3)),
    new TreeNode(2, null, new TreeNode(9))
);
console.log(largestValues(root)); // Output: [1, 3, 9]

Line Notes

const queue = [root];Initialize queue with root node for BFS

while (queue.length > 0) {Process nodes level by level until queue is empty

for (let i = 0; i < levelSize; i++) {Iterate over all nodes in current level

levelMax = Math.max(levelMax, node.val);Track max value in current level

⏱

Complexity

TimeO(n)

SpaceO(w)

Each node is visited once, so time is O(n). Space is O(w), where w is the maximum width of the tree (max nodes at any level).

💡 For a balanced tree with 20 nodes, max width is about 10, so space is about 10 nodes in the queue at once.

Interview Verdict: Accepted

This is the preferred approach in interviews for level order problems due to clarity and efficiency.

🧠

Optimized BFS with Inline Max Tracking

💡 This approach is a slight optimization of BFS by tracking max inline without extra variables or data structures beyond the queue and result list.

Intuition

While processing each level, update the max value inline and append it after processing the level.

Algorithm

1. Initialize a queue with the root node.
2. While queue is not empty, get the number of nodes at current level.
3. Initialize level max to negative infinity.
4. For each node in the level, update level max and enqueue children.
5. After processing the level, append level max to result.
6. Return the result list.

💡 This approach is almost identical to BFS but emphasizes clean inline max tracking.

</>

Code

from collections import deque
from typing import Optional, List

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

def largestValues(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_max = float('-inf')
        for _ in range(len(queue)):
            node = queue.popleft()
            level_max = max(level_max, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level_max)
    return res

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

Line Notes

for _ in range(len(queue))Process all nodes currently in the queue (current level)

level_max = max(level_max, node.val)Update max value inline while processing nodes

queue.append(node.left)Add left child for next level processing

queue.append(node.right)Add right child for next level processing

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelMax = Integer.MIN_VALUE;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelMax = Math.max(levelMax, node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            res.add(levelMax);
        }
        return res;
    }

    // Example usage
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);
        Solution sol = new Solution();
        System.out.println(sol.largestValues(root)); // Output: [1, 3, 9]
    }
}

Line Notes

int levelSize = queue.size();Capture current level size before processing

for (int i = 0; i < levelSize; i++) {Process all nodes in current level

levelMax = Math.max(levelMax, node.val);Update max value inline during traversal

queue.offer(node.left);Add left child for next level

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> largestValues(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelMax = INT_MIN;
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            levelMax = max(levelMax, node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(levelMax);
    }
    return res;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);
    vector<int> result = largestValues(root);
    for (int val : result) cout << val << " ";
    cout << endl; // Output: 1 3 9
    return 0;
}

Line Notes

int levelSize = q.size();Store current level size before processing nodes

for (int i = 0; i < levelSize; i++) {Process all nodes in current level

levelMax = max(levelMax, node->val);Update max value inline during traversal

q.push(node->left);Add left child for next level

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function largestValues(root) {
    if (!root) return [];
    const res = [];
    const queue = [root];
    while (queue.length > 0) {
        let levelMax = -Infinity;
        const levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            levelMax = Math.max(levelMax, node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        res.push(levelMax);
    }
    return res;
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(3, new TreeNode(5), new TreeNode(3)),
    new TreeNode(2, null, new TreeNode(9))
);
console.log(largestValues(root)); // Output: [1, 3, 9]

Line Notes

const levelSize = queue.length;Capture current level size before processing

for (let i = 0; i < levelSize; i++) {Process all nodes in current level

levelMax = Math.max(levelMax, node.val);Update max value inline during traversal

queue.push(node.left);Add left child for next level

⏱

Complexity

TimeO(n)

SpaceO(w)

Same as BFS, each node visited once, space depends on max width of tree.

💡 For 20 nodes, this means about 20 operations and queue size up to max width ~10.

Interview Verdict: Accepted

This is the cleanest BFS variant and recommended for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, BFS (Approach 2 or 3) is preferred for clarity and efficiency. DFS (Approach 1) is good for understanding but risks stack overflow.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS with Level Tracking)	O(n)	O(h) recursion stack	Yes (deep recursion)	N/A	Mention to show understanding, rarely code fully
2. BFS with Queue	O(n)	O(w) queue size	No	N/A	Preferred approach to code in interviews
3. Optimized BFS with Inline Max Tracking	O(n)	O(w)	No	N/A	Best BFS variant to code for clarity and conciseness

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then move to BFS for optimal solution. Practice coding and explaining each step clearly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force DFS approach with level tracking.Step 3: Explain the BFS approach using a queue for level order traversal.Step 4: Code the BFS solution, explaining each step.Step 5: Test with sample and edge cases, discuss complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, ability to track and aggregate data per level, and code correctness and efficiency.

Common Follow-ups

• What if the tree is very deep? → Use iterative BFS to avoid stack overflow.
• Can you find the smallest value in each row? → Modify max tracking to min tracking.

💡 Follow-ups often test your flexibility with traversal methods and aggregation logic.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree traversal, 2) Need to process nodes level by level, 3) Need aggregation per level (max, min, sum), 4) Output is per tree row.

Signature Phrases

'largest value in each tree row''per level of the tree''level order traversal'

NOT This Pattern When

DFS-only problems without level aggregation, or problems requiring path sums or subtree properties.

Similar Problems

Binary Tree Level Order Traversal - outputs all nodes per levelFind Bottom Left Tree Value - BFS with level tracking for leftmost nodeAverage of Levels in Binary Tree - BFS aggregation per level

Practice

1. You need to traverse a binary tree level by level, but alternate the order of nodes between left-to-right and right-to-left on each level. Which approach guarantees an optimal solution that avoids reversing lists after each level?

easy

A. Use a breadth-first search with a deque, appending nodes at either end depending on the current level's direction.

B. Perform a standard level order traversal using a queue and reverse the list of nodes at every other level after traversal.

C. Use a depth-first search with recursion, collecting nodes by depth and reversing every other level after traversal.

D. Use two stacks to alternate the order of node processing between levels, pushing children in specific order to maintain zigzag pattern.

Solution

1. Step 1: Understand the zigzag requirement

   The problem requires alternating the traversal direction at each level, which reversing after traversal can achieve but is inefficient.

2. Step 2: Identify approach that avoids reversing

   Using two stacks allows pushing children in an order that naturally produces the zigzag pattern without reversing lists.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two stacks method directly controls order -> no reversing needed [OK]

Hint: Two stacks avoid reversing by controlling push order [OK]

Common Mistakes:

• Assuming reversing after BFS is optimal
• Using DFS and reversing levels post-traversal

2. You are given a tree where each node can have multiple children. You need to collect the values of nodes level by level, starting from the root, and return them as a list of lists. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach selecting nodes with the highest value at each level

B. Depth-first search (DFS) with backtracking to collect nodes at each depth

C. Dynamic programming to store and reuse subtree results

D. Breadth-first search (BFS) using a queue to traverse nodes level by level

Solution

1. Step 1: Understand the problem requires level-wise traversal

   Collecting nodes level by level means visiting all nodes at depth d before nodes at depth d+1.

2. Step 2: Identify BFS as the natural approach for level order traversal

   BFS uses a queue to process nodes in order of their depth, ensuring correct grouping by levels.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS naturally processes nodes level by level [OK]

Hint: Level order traversal is BFS, not DFS or greedy [OK]

Common Mistakes:

• Confusing DFS with BFS for level order traversal

3. What is the time complexity of the iterative DFS solution that uses a stack to count good nodes in a binary tree with n nodes and height h?

medium

A. O(n log n) due to repeated max value comparisons

B. O(nh) because max value must be tracked along paths of length h

C. O(n) because each node is visited once and max value updates are O(1)

D. O(h) since only the height of the tree affects traversal

Solution

1. Step 1: Identify number of node visits

   Each node is pushed and popped exactly once from the stack, so O(n) visits.

2. Step 2: Analyze max value update cost

   Updating max_val is a constant time operation per node, no extra traversal per node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node [OK]

Hint: Each node processed once, max_val update O(1) [OK]

Common Mistakes:

• Assuming max_val tracking adds O(h) per node
• Confusing recursion stack space with time
• Thinking max_val comparisons cause O(n log n)

4. Suppose the binary tree can have nodes with duplicate values and you want to return the right side view but also include all nodes visible from the right side at each depth (not just the first). Which modification to the optimal DFS approach correctly handles this variant?

hard

A. Use DFS with right-first traversal but overwrite the node value at each depth to keep the last visited node.

B. Use BFS level order traversal and collect the last node at each level only.

C. Change DFS to visit left child first and append all nodes at each depth to a list.

D. Modify DFS to visit right child first and append every node encountered at each depth to a list instead of only the first.

Solution

1. Step 1: Understand requirement

   We want all nodes visible from the right side at each depth, not just the first.

2. Step 2: Modify DFS to collect all nodes per depth

   Visiting right child first ensures rightmost nodes are visited first, but we must append every node at that depth to a list, not just the first.

3. Step 3: Why other options fail

   Left-first traversal or overwriting values loses rightmost visibility; BFS collecting only last node misses duplicates.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Right-first DFS appending all nodes per depth captures all visible nodes [OK]

Hint: Right-first DFS appending all nodes per depth [OK]

Common Mistakes:

• Using left-first traversal loses rightmost nodes
• Appending only first or last node per depth misses duplicates
• Overwriting values loses multiple visible nodes

5. 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