N-ary Tree Level Order Traversal

🎯

N-ary Tree Level Order Traversal

mediumTREEFacebookAmazon

Imagine you are organizing a company hierarchy meeting and want to invite employees level by level, starting from the CEO down to the lowest level employees.

💡 This problem requires traversing a tree level by level, which can be tricky for beginners because unlike binary trees, each node can have multiple children, making it less straightforward to manage traversal order without a queue.

📋

Problem Statement

Given an n-ary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). The input is the root of the n-ary tree. Output a list of lists, where each inner list contains the values of nodes at that level.

The number of nodes in the tree is in the range [1, 10^5].0 <= Node.val <= 10^5The height of the n-ary tree is less than or equal to 1000.

💡

Example

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

Output[[1],[3,2,4],[5,6]]

Level 0 has node 1; Level 1 has nodes 3, 2, 4; Level 2 has nodes 5, 6.

• Empty tree (root = null) → []
• Tree with only one node → [[root.val]]
• Tree where nodes have varying number of children → correctly group by levels
• Deep tree with single child chains → output each node in its own level list

⚠️

Common Mistakes

Not checking for empty tree (null root)

Code throws null pointer exception or returns incorrect result

✅ Add a check at the start to return empty list if root is null

Mixing levels by not separating nodes properly in BFS

All nodes get added to a single list instead of grouped by level

✅ Use level size to process nodes level by level or use two queues

Using recursion without limiting depth

Stack overflow on deep trees

✅ Prefer iterative BFS for large or deep trees

Forgetting to enqueue all children

Some nodes are never visited, incomplete traversal

✅ Ensure loop over all children and enqueue each

Using shift() in JavaScript without considering performance

Inefficient code with O(n^2) time due to array shifting

✅ Use a queue data structure or maintain indices to avoid costly shifts

🧠

Brute Force (Recursive Level Collection)

💡 This approach uses recursion to collect nodes at each level by traversing the tree multiple times. It is intuitive but inefficient for large trees.

Intuition

We recursively visit nodes and keep track of the current level. For each node, we add its value to a list corresponding to that level. This requires traversing the tree and managing lists for each level.

Algorithm

1. Define a helper function that takes a node and its level.
2. If the current level list does not exist, create it.
3. Add the node's value to the list for that level.
4. Recursively call the helper for each child with level + 1.

💡 The recursion depth corresponds to the tree height, and managing the level lists is key to grouping nodes correctly.

</>

Code

from collections import deque

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

def levelOrder(root):
    res = []
    def helper(node, level):
        if not node:
            return
        if len(res) == level:
            res.append([])
        res[level].append(node.val)
        for child in node.children:
            helper(child, level + 1)
    helper(root, 0)
    return res

# Example usage:
if __name__ == '__main__':
    root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])
    print(levelOrder(root))

Line Notes

def helper(node, level):Defines recursive function to process nodes by level

if len(res) == level:Checks if we need to add a new list for the current level

res[level].append(node.val)Adds current node's value to its level list

for child in node.children:Recursively processes all children at next level

import java.util.*;

class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) { val = _val; }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

public class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(root, 0, res);
        return res;
    }
    private void helper(Node node, int level, List<List<Integer>> res) {
        if (node == null) return;
        if (res.size() == level) res.add(new ArrayList<>());
        res.get(level).add(node.val);
        for (Node child : node.children) {
            helper(child, level + 1, res);
        }
    }

    // Example usage
    public static void main(String[] args) {
        Node root = new Node(1, Arrays.asList(
            new Node(3, Arrays.asList(new Node(5), new Node(6))),
            new Node(2),
            new Node(4)
        ));
        Solution sol = new Solution();
        System.out.println(sol.levelOrder(root));
    }
}

Line Notes

private void helper(Node node, int level, List<List<Integer>> res)Recursive helper to process nodes by level

if (res.size() == level) res.add(new ArrayList<>());Create new list for current level if needed

res.get(level).add(node.val);Add node value to corresponding level list

for (Node child : node.children)Recurse on all children with incremented level

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

class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) : val(_val) {}
    Node(int _val, vector<Node*> _children) : val(_val), children(_children) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        helper(root, 0, res);
        return res;
    }
private:
    void helper(Node* node, int level, vector<vector<int>>& res) {
        if (!node) return;
        if (res.size() == level) res.push_back(vector<int>());
        res[level].push_back(node->val);
        for (Node* child : node->children) {
            helper(child, level + 1, res);
        }
    }
};

int main() {
    Node* root = new Node(1, {new Node(3, {new Node(5), new Node(6)}), new Node(2), new Node(4)});
    Solution sol;
    vector<vector<int>> result = sol.levelOrder(root);
    for (auto& level : result) {
        for (int val : level) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

void helper(Node* node, int level, vector<vector<int>>& res)Recursive helper to traverse nodes by level

if (res.size() == level) res.push_back(vector<int>());Add new vector for current level if missing

res[level].push_back(node->val);Append current node's value to its level vector

for (Node* child : node->children)Recurse on each child with incremented level

class Node {
    constructor(val, children = []) {
        this.val = val;
        this.children = children;
    }
}

function levelOrder(root) {
    const res = [];
    function helper(node, level) {
        if (!node) return;
        if (res.length === level) res.push([]);
        res[level].push(node.val);
        for (const child of node.children) {
            helper(child, level + 1);
        }
    }
    helper(root, 0);
    return res;
}

// Example usage
const root = new Node(1, [new Node(3, [new Node(5), new Node(6)]), new Node(2), new Node(4)]);
console.log(levelOrder(root));

Line Notes

function helper(node, level)Recursive helper to process nodes by level

if (res.length === level) res.push([]);Create new array for current level if needed

res[level].push(node.val);Add current node's value to its level array

for (const child of node.children)Recursively call helper on each child with incremented level

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, and we store all nodes in the result. The recursion stack can go as deep as the tree height.

💡 For n=20 nodes, this means roughly 20 visits and storing 20 values, but recursion depth depends on tree height.

Interview Verdict: Accepted but not optimal for very deep trees due to recursion stack

This approach works but risks stack overflow on very deep trees; it is good to understand recursion but not always practical.

🧠

Iterative BFS Using Queue

💡 This approach uses a queue to traverse the tree level by level iteratively, which is more efficient and avoids recursion stack issues.

Intuition

Use a queue to hold nodes of the current level. Dequeue nodes one by one, enqueue their children, and collect values level-wise.

Algorithm

1. Initialize a queue and add the root node if it exists.
2. While the queue is not empty, process nodes level by level:
3. For each node in the current level, dequeue it, add its value to the current level list, and enqueue its children.
4. Add the current level list to the result.

💡 The queue ensures nodes are processed in the exact order of their levels, making grouping straightforward.

</>

Code

from collections import deque

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

def levelOrder(root):
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_nodes = []
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            for child in node.children:
                queue.append(child)
        res.append(level_nodes)
    return res

# Example usage:
if __name__ == '__main__':
    root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])
    print(levelOrder(root))

Line Notes

if not root:Handles empty tree edge case immediately

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

for _ in range(level_size):Process all nodes currently in queue as one level

for child in node.children:Add all children of current node to queue for next level

import java.util.*;

class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) { val = _val; }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

public class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                level.add(node.val);
                for (Node child : node.children) {
                    queue.offer(child);
                }
            }
            res.add(level);
        }
        return res;
    }

    // Example usage
    public static void main(String[] args) {
        Node root = new Node(1, Arrays.asList(
            new Node(3, Arrays.asList(new Node(5), new Node(6))),
            new Node(2),
            new Node(4)
        ));
        Solution sol = new Solution();
        System.out.println(sol.levelOrder(root));
    }
}

Line Notes

if (root == null) return res;Return empty list if tree is empty

Queue<Node> queue = new LinkedList<>();Use queue to hold nodes for BFS

for (int i = 0; i < size; i++)Process all nodes at current level

for (Node child : node.children)Add children to queue for next level processing

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

class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) : val(_val) {}
    Node(int _val, vector<Node*> _children) : val(_val), children(_children) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            for (int i = 0; i < size; i++) {
                Node* node = q.front(); q.pop();
                level.push_back(node->val);
                for (Node* child : node->children) {
                    q.push(child);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

int main() {
    Node* root = new Node(1, {new Node(3, {new Node(5), new Node(6)}), new Node(2), new Node(4)});
    Solution sol;
    vector<vector<int>> result = sol.levelOrder(root);
    for (auto& level : result) {
        for (int val : level) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

if (!root) return res;Handle empty tree case early

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

for (int i = 0; i < size; i++)Process all nodes at current level

for (Node* child : node->children)Enqueue all children for next level

class Node {
    constructor(val, children = []) {
        this.val = val;
        this.children = children;
    }
}

function levelOrder(root) {
    if (!root) return [];
    const res = [];
    const queue = [root];
    while (queue.length > 0) {
        const size = queue.length;
        const level = [];
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            level.push(node.val);
            for (const child of node.children) {
                queue.push(child);
            }
        }
        res.push(level);
    }
    return res;
}

// Example usage
const root = new Node(1, [new Node(3, [new Node(5), new Node(6)]), new Node(2), new Node(4)]);
console.log(levelOrder(root));

Line Notes

if (!root) return [];Return empty array if tree is empty

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

for (let i = 0; i < size; i++)Process all nodes at current level

for (const child of node.children)Add children to queue for next level

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is enqueued and dequeued exactly once. The queue holds at most the number of nodes at the largest level.

💡 For n=20 nodes, this means 20 enqueue and dequeue operations, with memory proportional to the widest level.

Interview Verdict: Accepted and preferred approach in interviews

This approach is efficient, easy to understand, and avoids recursion stack issues, making it ideal for interviews.

🧠

Iterative BFS Using Two Queues

💡 This approach uses two queues to separate current level nodes from next level nodes, making level management explicit.

Intuition

Use one queue to hold nodes of the current level and another to hold nodes of the next level. After processing current level, swap queues.

Algorithm

1. Initialize two queues: currentLevel and nextLevel.
2. Add root to currentLevel if it exists.
3. While currentLevel is not empty, process all nodes in it:
4. For each node, add its value to current level list and enqueue its children to nextLevel.
5. After processing currentLevel, add the level list to result and swap queues.

💡 Swapping queues after each level clearly separates processing stages, which can be easier to reason about.

</>

Code

from collections import deque

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

def levelOrder(root):
    if not root:
        return []
    res = []
    current_level = deque([root])
    next_level = deque()
    while current_level:
        level_nodes = []
        while current_level:
            node = current_level.popleft()
            level_nodes.append(node.val)
            for child in node.children:
                next_level.append(child)
        res.append(level_nodes)
        current_level, next_level = next_level, deque()
    return res

# Example usage:
if __name__ == '__main__':
    root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])
    print(levelOrder(root))

Line Notes

current_level = deque([root])Initialize queue for current level with root

while current_level:Process nodes level by level

for child in node.children:Add children to next level queue

current_level, next_level = next_level, deque()Swap queues to move to next level

import java.util.*;

class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) { val = _val; }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

public class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<Node> currentLevel = new LinkedList<>();
        Queue<Node> nextLevel = new LinkedList<>();
        currentLevel.offer(root);
        while (!currentLevel.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            while (!currentLevel.isEmpty()) {
                Node node = currentLevel.poll();
                level.add(node.val);
                for (Node child : node.children) {
                    nextLevel.offer(child);
                }
            }
            res.add(level);
            Queue<Node> temp = currentLevel;
            currentLevel = nextLevel;
            nextLevel = temp;
        }
        return res;
    }

    // Example usage
    public static void main(String[] args) {
        Node root = new Node(1, Arrays.asList(
            new Node(3, Arrays.asList(new Node(5), new Node(6))),
            new Node(2),
            new Node(4)
        ));
        Solution sol = new Solution();
        System.out.println(sol.levelOrder(root));
    }
}

Line Notes

Queue<Node> currentLevel = new LinkedList<>();Queue for nodes at current level

while (!currentLevel.isEmpty())Process all nodes in current level

for (Node child : node.children)Add children to next level queue

Queue<Node> temp = currentLevel; currentLevel = nextLevel; nextLevel = temp;Swap queues to move to next level

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

class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) : val(_val) {}
    Node(int _val, vector<Node*> _children) : val(_val), children(_children) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<Node*> currentLevel, nextLevel;
        currentLevel.push(root);
        while (!currentLevel.empty()) {
            vector<int> level;
            while (!currentLevel.empty()) {
                Node* node = currentLevel.front(); currentLevel.pop();
                level.push_back(node->val);
                for (Node* child : node->children) {
                    nextLevel.push(child);
                }
            }
            res.push_back(level);
            swap(currentLevel, nextLevel);
        }
        return res;
    }
};

int main() {
    Node* root = new Node(1, {new Node(3, {new Node(5), new Node(6)}), new Node(2), new Node(4)});
    Solution sol;
    vector<vector<int>> result = sol.levelOrder(root);
    for (auto& level : result) {
        for (int val : level) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

queue<Node*> currentLevel, nextLevel;Two queues to separate current and next level nodes

while (!currentLevel.empty())Process all nodes in current level queue

for (Node* child : node->children)Add children to next level queue

swap(currentLevel, nextLevel);Swap queues to move to next level

class Node {
    constructor(val, children = []) {
        this.val = val;
        this.children = children;
    }
}

function levelOrder(root) {
    if (!root) return [];
    const res = [];
    let currentLevel = [root];
    let nextLevel = [];
    while (currentLevel.length > 0) {
        const level = [];
        while (currentLevel.length > 0) {
            const node = currentLevel.shift();
            level.push(node.val);
            for (const child of node.children) {
                nextLevel.push(child);
            }
        }
        res.push(level);
        [currentLevel, nextLevel] = [nextLevel, []];
    }
    return res;
}

// Example usage
const root = new Node(1, [new Node(3, [new Node(5), new Node(6)]), new Node(2), new Node(4)]);
console.log(levelOrder(root));

Line Notes

let currentLevel = [root];Initialize current level queue with root

while (currentLevel.length > 0)Process nodes level by level

for (const child of node.children)Add children to next level queue

[currentLevel, nextLevel] = [nextLevel, []];Swap queues to move to next level

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is processed once. Two queues hold nodes of current and next levels, but total space is proportional to number of nodes.

💡 For n=20 nodes, this means 20 node visits and memory for at most two levels of nodes.

Interview Verdict: Accepted, alternative BFS approach

This approach is equally efficient as single queue BFS but sometimes easier to reason about level separation.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the iterative BFS using a single queue is the best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive Level Collection)	O(n)	O(n) + recursion stack O(h)	Yes (deep recursion)	N/A	Mention only - never code due to stack risk
2. Iterative BFS Using Queue	O(n)	O(n)	No	N/A	Preferred approach to code
3. Iterative BFS Using Two Queues	O(n)	O(n)	No	N/A	Alternative BFS approach, good to mention

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, followed by the optimal BFS approach. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the input format and output expectations.Step 2: Describe the brute force recursive approach to show understanding.Step 3: Introduce the iterative BFS approach using a queue as the optimal solution.Step 4: Write clean, readable code and explain each step.Step 5: Test your code with edge cases and explain the complexity.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, ability to manage multiple children, and your skill in using queues for BFS. They also assess your code clarity and testing thoroughness.

Common Follow-ups

• How would you modify the code to return the nodes in reverse level order? → Use a stack or prepend levels.
• Can you do this traversal without extra space? → Not possible for level order; BFS requires queue.

💡 Follow-ups test your flexibility with traversal order and space optimization understanding.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to traverse a tree level by level, especially when nodes have multiple children and output grouping by levels is required.

Signature Phrases

'return the level order traversal''from left to right, level by level'

NOT This Pattern When

Depth-first traversals like preorder or postorder, which do not group nodes by level.

Similar Problems

Binary Tree Level Order Traversal - simpler binary tree versionN-ary Tree Preorder Traversal - different traversal orderZigzag Level Order Traversal - level order with alternating directions

Practice

1. Consider the following code snippet for finding the minimum depth of a binary tree using BFS. Given the tree below, what is the value of depth when the first leaf node is dequeued? Tree structure: - Root (1) - Left child (2) - Right child (3) - Left child (4)

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

def minDepth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3, TreeNode(4))
print(minDepth(root))

easy

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Trace the BFS queue operations

   Initially queue = [(root(1), 1)]. Dequeue root: not leaf, enqueue left(2,2) and right(3,2).

2. Step 2: Dequeue next node and check leaf

   Dequeue (2,2). Node 2 has no children, so it is a leaf. Return depth = 2.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First leaf found at depth 2 -> correct BFS behavior [OK]

Hint: First leaf found at depth 2 in BFS traversal [OK]

Common Mistakes:

• Returning depth 1 because root is counted incorrectly
• Continuing BFS past first leaf node
• Confusing node values with depth

2. What is the time complexity of the optimal two-stacks zigzag level order traversal algorithm for a binary tree with n nodes?

medium

A. O(n), since each node is visited exactly once and pushed/popped at most twice

B. O(n^2), because pushing children in two stacks doubles the work per node

C. O(n log n), because each level requires reversing the node list

D. O(n), but with O(h) auxiliary space where h is the tree height due to recursion stack

Solution

1. Step 1: Identify node visits

   Each node is pushed and popped exactly once per stack, total constant times per node.

2. Step 2: Analyze operations per node

   Appending children and popping nodes are O(1) operations, no nested loops over nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear traversal with constant work per node -> O(n) time [OK]

Hint: Each node processed once, no repeated work [OK]

Common Mistakes:

• Assuming reversing adds O(n log n)
• Confusing stack pushes as doubling work

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 nodes can have negative values and the tree can be very deep (height up to 10^5). Which modification to the average-of-levels algorithm is necessary to handle this scenario efficiently and correctly?

hard

A. Use DFS with recursion and level tracking to avoid large queue memory usage.

B. Use BFS but store all node values per level in a list before averaging to handle negative values correctly.

C. Use BFS with a queue and floating point division as usual; no changes needed.

D. Use BFS with a queue but compute running averages incrementally to avoid integer overflow and large memory.

Solution

1. Step 1: Consider memory constraints with deep trees

   Deep trees can cause large queue sizes; BFS queue size depends on width, but deep trees may have small width.

2. Step 2: Handle negative values and large sums safely

   Running average calculation incrementally avoids integer overflow and handles negatives correctly without storing all values.

3. Step 3: Why other options fail

   DFS recursion risks stack overflow; storing all values wastes memory; no changes risks overflow or inefficiency.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Incremental running average with BFS is memory and overflow safe [OK]

Hint: Incremental averages avoid overflow and large memory [OK]

Common Mistakes:

• Using recursion on deep trees causes stack overflow
• Storing all values wastes memory
• Ignoring negative values impact on sums

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