Binary Tree Right Side View

🎯

Binary Tree Right Side View

mediumTREEFacebookAmazonBloomberg

Imagine standing on the right side of a tall building and wanting to see which windows are visible on each floor. This problem asks you to find the nodes visible when looking at a binary tree from its right side.

💡 This problem is about traversing a binary tree level by level and picking the rightmost node at each level. Beginners often struggle because they may not immediately see how to combine tree traversal with level tracking to get the right side view.

📋

Problem Statement

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

The number of nodes in the tree is in the range [1, 10^5].-100 <= Node.val <= 100

💡

Example

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

Output[1,3,4]

At level 0, node 1 is visible; at level 1, node 3 is the rightmost; at level 2, node 4 is the rightmost visible node.

• Single node tree → output is the single node's value
• All nodes only have left children → output is all nodes in top-down order
• All nodes only have right children → output is all nodes in top-down order
• Empty tree (null root) → output is an empty list

⚠️

Common Mistakes

Visiting left child before right in DFS and recording first node per level

Incorrect right side view because left nodes overwrite right nodes

✅ Visit right child before left in DFS to ensure first node per level is rightmost

Not handling empty tree input

Code may throw null pointer exception or runtime error

✅ Check if root is null and return empty list immediately

Using DFS with overwriting but traversing right child before left

Overwrites cause left nodes to replace right nodes incorrectly

✅ If using overwriting approach, traverse left child before right

Not correctly identifying last node at each level in BFS

Wrong nodes added to result, failing test cases

✅ Use loop index to detect last node at level and add its value

🧠

Brute Force (DFS with Level Tracking and Overwriting)

💡 This approach uses a simple depth-first search to explore all nodes, keeping track of the level and overwriting the value for each level to ensure the rightmost node is recorded. It helps beginners understand the problem by directly simulating the view from the right side.

Intuition

Traverse the tree depth-first, and for each level, overwrite the stored value with the current node's value. Because DFS explores right before left, the last node visited at each level will be the rightmost node.

Algorithm

1. Initialize a list to store the rightmost node value at each level.
2. Perform DFS starting from root with level 0.
3. At each node, overwrite the value at the current level in the list.
4. After traversal, return the list containing rightmost nodes per level.

💡 The key difficulty is realizing that overwriting values at each level during DFS ensures the rightmost node is recorded, even though we visit right children first.

</>

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 rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightmost_value_at_depth = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightmost_value_at_depth):
            rightmost_value_at_depth.append(node.val)
        else:
            rightmost_value_at_depth[depth] = node.val
        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return rightmost_value_at_depth

# Example usage:
# Construct tree [1,2,3,null,5,null,4]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
print(rightSideView(root))  # Output: [1,3,4]

Line Notes

def rightSideView(root: Optional[TreeNode]) -> List[int]:Defines the main function with type hints for clarity

rightmost_value_at_depth = []Stores the rightmost node value at each depth level

def dfs(node, depth):Helper function to perform DFS with current node and depth

if not node:Base case: if node is None, stop recursion

if depth == len(rightmost_value_at_depth):If first time visiting this depth, append node value

rightmost_value_at_depth[depth] = node.valOverwrite existing value to keep rightmost node at this depth

dfs(node.right, depth + 1)Traverse right subtree first to ensure rightmost nodes overwrite left

dfs(node.left, depth + 1)Traverse left subtree after right

dfs(root, 0)Start DFS from root at depth 0

return rightmost_value_at_depthReturn the collected rightmost nodes per level

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightmostValueAtDepth = new ArrayList<>();
        dfs(root, 0, rightmostValueAtDepth);
        return rightmostValueAtDepth;
    }
    private void dfs(TreeNode node, int depth, List<Integer> rightmostValueAtDepth) {
        if (node == null) return;
        if (depth == rightmostValueAtDepth.size()) {
            rightmostValueAtDepth.add(node.val);
        } else {
            rightmostValueAtDepth.set(depth, node.val);
        }
        dfs(node.right, depth + 1, rightmostValueAtDepth);
        dfs(node.left, depth + 1, rightmostValueAtDepth);
    }
    // Example main method
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(4);
        Solution sol = new Solution();
        System.out.println(sol.rightSideView(root)); // Output: [1, 3, 4]
    }
}

Line Notes

public List<Integer> rightSideView(TreeNode root)Main method signature returning list of rightmost nodes

List<Integer> rightmostValueAtDepth = new ArrayList<>();Stores rightmost node values per depth

if (node == null) return;Base case for recursion

if (depth == rightmostValueAtDepth.size())If first time at this depth, add node value

rightmostValueAtDepth.set(depth, node.val);Overwrite to keep rightmost node at this depth

dfs(node.right, depth + 1, rightmostValueAtDepth);Traverse right subtree first to ensure rightmost nodes overwrite left

dfs(node.left, depth + 1, rightmostValueAtDepth);Traverse left subtree after right

public static void main(String[] args)Driver code to test the solution

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> rightmostValueAtDepth;
        dfs(root, 0, rightmostValueAtDepth);
        return rightmostValueAtDepth;
    }
private:
    void dfs(TreeNode* node, int depth, vector<int>& rightmostValueAtDepth) {
        if (!node) return;
        if (depth == rightmostValueAtDepth.size()) {
            rightmostValueAtDepth.push_back(node->val);
        } else {
            rightmostValueAtDepth[depth] = node->val;
        }
        dfs(node->right, depth + 1, rightmostValueAtDepth);
        dfs(node->left, depth + 1, rightmostValueAtDepth);
    }
};

// Example usage
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution sol;
    vector<int> res = sol.rightSideView(root);
    for (int v : res) cout << v << " "; // Output: 1 3 4
    cout << endl;
    return 0;
}

Line Notes

vector<int> rightmostValueAtDepth;Stores rightmost node values per depth

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

if (depth == rightmostValueAtDepth.size())First time visiting this depth, add node value

rightmostValueAtDepth[depth] = node->val;Overwrite to keep rightmost node at this depth

dfs(node->right, depth + 1, rightmostValueAtDepth);Traverse right subtree first to ensure rightmost nodes overwrite left

dfs(node->left, depth + 1, rightmostValueAtDepth);Traverse left subtree after right

int main()Driver code to test the solution

for (int v : res) cout << v << " ";Print the right side view nodes

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rightSideView(root) {
    const rightmostValueAtDepth = [];
    function dfs(node, depth) {
        if (!node) return;
        if (depth === rightmostValueAtDepth.length) {
            rightmostValueAtDepth.push(node.val);
        } else {
            rightmostValueAtDepth[depth] = node.val;
        }
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
    dfs(root, 0);
    return rightmostValueAtDepth;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(4);
console.log(rightSideView(root)); // Output: [1, 3, 4]

Line Notes

function rightSideView(root)Main function to compute right side view

const rightmostValueAtDepth = [];Stores rightmost node values per depth

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

if (depth === rightmostValueAtDepth.length)First time visiting this depth, add node value

rightmostValueAtDepth[depth] = node.val;Overwrite to keep rightmost node at this depth

dfs(node.right, depth + 1);Traverse right subtree first to ensure rightmost nodes overwrite left

dfs(node.left, depth + 1);Traverse left subtree after right

console.log(rightSideView(root));Print the right side view nodes

⏱

Complexity

TimeO(n)

SpaceO(h)

We visit each node once, so time is O(n). The recursion stack can go as deep as the tree height h, so space is O(h).

💡 For a tree with 1000 nodes and height 10, this means about 1000 operations and stack depth up to 10.

Interview Verdict: Accepted

This approach is accepted but can be improved for clarity and iterative style.

🧠

Better (BFS Level Order Traversal with Rightmost Node Capture)

💡 Using BFS to traverse level by level naturally fits the problem of capturing the rightmost node at each level. This approach is easier to understand and implement iteratively, which is often preferred in interviews.

Intuition

Perform a breadth-first search level by level, and at each level, record the last node's value. This last node is the rightmost visible node from that level.

Algorithm

1. Initialize a queue and add the root node.
2. While the queue is not empty, process nodes level by level.
3. For each level, iterate through all nodes and enqueue their children.
4. Record the value of the last node processed at each level.
5. Return the list of recorded values.

💡 The challenge is to correctly identify the last node at each level during BFS and store its value.

</>

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 rightSideView(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    queue = deque([root])
    rightside = []
    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            if i == level_length - 1:
                rightside.append(node.val)
    return rightside

# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
print(rightSideView(root))  # Output: [1,3,4]

Line Notes

if not root:Handle empty tree edge case immediately

queue = deque([root])Initialize queue with root for BFS

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

level_length = len(queue)Number of nodes at current level

for i in range(level_length):Iterate over all nodes at current level

node = queue.popleft()Dequeue node to process

if node.left: queue.append(node.left)Add left child to queue if exists

if node.right: queue.append(node.right)Add right child to queue if exists

if i == level_length - 1: rightside.append(node.val)Record last node's value at this level

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightside = new ArrayList<>();
        if (root == null) return rightside;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelLength = queue.size();
            for (int i = 0; i < levelLength; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                if (i == levelLength - 1) rightside.add(node.val);
            }
        }
        return rightside;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(4);
        Solution sol = new Solution();
        System.out.println(sol.rightSideView(root)); // Output: [1, 3, 4]
    }
}

Line Notes

if (root == null) return rightside;Handle empty tree early

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

while (!queue.isEmpty())Process levels until no nodes left

int levelLength = queue.size();Number of nodes at current level

for (int i = 0; i < levelLength; i++)Iterate over nodes at current level

TreeNode node = queue.poll();Dequeue node for processing

if (node.left != null) queue.offer(node.left);Add left child if exists

if (node.right != null) queue.offer(node.right);Add right child if exists

if (i == levelLength - 1) rightside.add(node.val);Add last node's value at this level

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> rightside;
        if (!root) return rightside;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int levelLength = q.size();
            for (int i = 0; i < levelLength; i++) {
                TreeNode* node = q.front(); q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
                if (i == levelLength - 1) rightside.push_back(node->val);
            }
        }
        return rightside;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution sol;
    vector<int> res = sol.rightSideView(root);
    for (int v : res) cout << v << " "; // Output: 1 3 4
    cout << endl;
    return 0;
}

Line Notes

if (!root) return rightside;Return empty vector if tree is empty

queue<TreeNode*> q;Queue for BFS traversal

while (!q.empty())Process nodes level by level

int levelLength = q.size();Number of nodes at current level

for (int i = 0; i < levelLength; i++)Iterate over all nodes at this level

TreeNode* node = q.front(); q.pop();Dequeue node for processing

if (node->left) q.push(node->left);Add left child if exists

if (node->right) q.push(node->right);Add right child if exists

if (i == levelLength - 1) rightside.push_back(node->val);Add last node's value at this level

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rightSideView(root) {
    if (!root) return [];
    const queue = [root];
    const rightside = [];
    while (queue.length > 0) {
        const levelLength = queue.length;
        for (let i = 0; i < levelLength; i++) {
            const node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
            if (i === levelLength - 1) rightside.push(node.val);
        }
    }
    return rightside;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(4);
console.log(rightSideView(root)); // Output: [1, 3, 4]

Line Notes

if (!root) return [];Handle empty tree case

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

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

const levelLength = queue.length;Number of nodes at current level

for (let i = 0; i < levelLength; i++)Iterate over all nodes at this level

const node = queue.shift();Dequeue node for processing

if (node.left) queue.push(node.left);Add left child if exists

if (node.right) queue.push(node.right);Add right child if exists

if (i === levelLength - 1) rightside.push(node.val);Add last node's value at this level

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, so time is O(n). The queue can hold up to the maximum number of nodes at any level, which can be O(n) in worst case.

💡 For a balanced tree with 1000 nodes, the queue size is roughly the max width, about 500, so space is manageable.

Interview Verdict: Accepted

This is the most intuitive and commonly accepted approach in interviews.

🧠

Optimal (DFS with Right-First Traversal and Level Check)

💡 This approach uses DFS but visits the right child before the left child, ensuring the first node visited at each level is the rightmost node. This avoids overwriting and is elegant and efficient.

Intuition

Traverse the tree depth-first, but visit right children before left. For each level, record the first node visited only, which is guaranteed to be the rightmost node.

Algorithm

1. Initialize a list to store the rightmost node value at each level.
2. Perform DFS starting from root with level 0, visiting right child first.
3. If the current level is not yet recorded, add the node's value.
4. Continue recursively for right and left children.
5. Return the list after traversal.

💡 The key insight is that visiting right child first ensures the first node at each level is the rightmost, so no overwriting is needed.

</>

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 rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightside):
            rightside.append(node.val)
        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return rightside

# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
print(rightSideView(root))  # Output: [1,3,4]

Line Notes

rightside = []Stores the first node value seen at each depth (rightmost)

def dfs(node, depth):Helper DFS function with current node and depth

if not node:Base case to stop recursion

if depth == len(rightside):If first node at this depth, record its value

dfs(node.right, depth + 1)Traverse right child first to get rightmost nodes

dfs(node.left, depth + 1)Traverse left child after right

dfs(root, 0)Start DFS from root at depth 0

return rightsideReturn collected rightmost nodes

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightside = new ArrayList<>();
        dfs(root, 0, rightside);
        return rightside;
    }
    private void dfs(TreeNode node, int depth, List<Integer> rightside) {
        if (node == null) return;
        if (depth == rightside.size()) {
            rightside.add(node.val);
        }
        dfs(node.right, depth + 1, rightside);
        dfs(node.left, depth + 1, rightside);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(4);
        Solution sol = new Solution();
        System.out.println(sol.rightSideView(root)); // Output: [1, 3, 4]
    }
}

Line Notes

List<Integer> rightside = new ArrayList<>();Stores first node value at each depth

if (node == null) return;Base case to stop recursion

if (depth == rightside.size())Record first node at this depth

dfs(node.right, depth + 1, rightside);Traverse right child first

dfs(node.left, depth + 1, rightside);Traverse left child after right

public static void main(String[] args)Driver code to test solution

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> rightside;
        dfs(root, 0, rightside);
        return rightside;
    }
private:
    void dfs(TreeNode* node, int depth, vector<int>& rightside) {
        if (!node) return;
        if (depth == rightside.size()) {
            rightside.push_back(node->val);
        }
        dfs(node->right, depth + 1, rightside);
        dfs(node->left, depth + 1, rightside);
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution sol;
    vector<int> res = sol.rightSideView(root);
    for (int v : res) cout << v << " "; // Output: 1 3 4
    cout << endl;
    return 0;
}

Line Notes

vector<int> rightside;Stores first node value at each depth

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

if (depth == rightside.size())Record first node at this depth

dfs(node->right, depth + 1, rightside);Traverse right child first

dfs(node->left, depth + 1, rightside);Traverse left child after right

int main()Driver code to test solution

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rightSideView(root) {
    const rightside = [];
    function dfs(node, depth) {
        if (!node) return;
        if (depth === rightside.length) {
            rightside.push(node.val);
        }
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
    dfs(root, 0);
    return rightside;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(4);
console.log(rightSideView(root)); // Output: [1, 3, 4]

Line Notes

const rightside = [];Stores first node value at each depth

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

if (depth === rightside.length)Record first node at this depth

dfs(node.right, depth + 1);Traverse right child first

dfs(node.left, depth + 1);Traverse left child after right

console.log(rightSideView(root));Print the right side view nodes

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, so time is O(n). The recursion stack depth is at most the height h of the tree.

💡 For a balanced tree with 1000 nodes and height 10, this means 1000 operations and stack depth up to 10.

Interview Verdict: Accepted

This approach is elegant and efficient, often preferred in interviews for its clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (BFS) or Approach 3 (DFS right-first) are best to code in interviews for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS with overwriting right-first)	O(n)	O(h)	Yes (deep recursion)	N/A	Mention only - helps understand problem but less clean
2. Better (BFS level order traversal)	O(n)	O(n)	No	N/A	Good to code - intuitive and iterative
3. Optimal (DFS right-first, record first node)	O(n)	O(h)	Yes (deep recursion)	N/A	Best for elegance and clarity

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice all approaches. Start by clarifying the problem, then explain brute force, and progressively improve your solution. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and ask about input format and constraints.Step 2: Describe the brute force DFS approach with level tracking and overwriting.Step 3: Explain the BFS level order traversal approach and why it works.Step 4: Present the optimal DFS approach visiting right child first.Step 5: Code your chosen approach and test with examples and edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, level tracking, and ability to identify the rightmost node per level. They also assess your coding skills and handling of edge cases.

Common Follow-ups

• What if you want the left side view instead? → Traverse left child first in DFS or pick first node in BFS level.
• Can you do this iteratively without recursion? → Use BFS with queue as shown in approach 2.

💡 These follow-ups test your flexibility with traversal order and iterative vs recursive implementations.

🔍

Pattern Recognition

When to Use

Use this pattern when asked to find nodes visible from one side of a binary tree, especially when problem mentions 'right side view' or 'left side view'.

Signature Phrases

'right side of the tree''nodes visible from the right''per level rightmost node'

NOT This Pattern When

Problems asking for bottom view or top view of binary tree, which require different traversal and data structures.

Similar Problems

Binary Tree Left Side View - same concept but from left sideBinary Tree Level Order Traversal - BFS level by level traversalBinary Tree Zigzag Level Order Traversal - variation with alternating order

Practice

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

2. Consider the following code snippet for counting good nodes in a binary tree. Given the tree with root value 3, left child 1 (with left child 3), and right child 4 (with left child 1 and right child 5), what is the final returned count?

easy

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Trace stack operations and count updates

   Start with stack=[(3,3)]. Pop (3,3), count=1. Push right (4,3), left (1,3). Pop (1,3), node.val=1 < 3 no count. Push left (3,3). Pop (3,3), node.val=3 >=3 count=2. Pop (4,3), node.val=4 >=3 count=3. Push right (5,4), left (1,4). Pop (1,4), node.val=1 <4 no count. Pop (5,4), node.val=5 >=4 count=4.

2. Step 2: Final count after traversal

   Count is 4 after visiting all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count matches expected good nodes in example [OK]

Hint: Track max_val updates carefully during stack pops [OK]

Common Mistakes:

• Off-by-one counting
• Ignoring max_val update before pushing children
• Mixing left and right child order

3. Given the following code snippet and the binary tree below, what is the final returned value? Tree structure: 1 / \ 2 3 / \ 4 5

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])
        node = None
        while queue:
            node = queue.popleft()
            if node.right:
                queue.append(node.right)
            if node.left:
                queue.append(node.left)
        return node.val

root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
sol = Solution()
print(sol.findBottomLeftValue(root))

easy

A. 2

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace queue operations

   Start with queue=[1]. Pop 1, enqueue right=3 then left=2 -> queue=[3,2]. Pop 3, enqueue right=5 then left=4 -> queue=[2,5,4]. Pop 2 (no children) -> queue=[5,4]. Pop 5 (no children) -> queue=[4]. Pop 4 (no children) -> queue=[]. Last popped node is 4.

2. Step 2: Identify last popped node value

   Last popped node is 4, so return 4.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Last node popped is 4, confirming BFS with right-to-left insertion finds bottom-left node [OK]

Hint: Trace queue pops and inserts carefully to find last node [OK]

Common Mistakes:

• Confusing order of enqueueing children
• Assuming left child is processed before right in BFS
• Returning first node at last level instead of last popped

4. The following code attempts to perform vertical order traversal using BFS and column tracking. Identify the line containing the subtle bug that causes incorrect grouping of nodes by column.

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 in col_table:
            col_table[col] = []  # Bug here
        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())

medium

A. Line: if not root: return []

B. Line: if col in col_table: col_table[col] = []

C. Line: queue.append((node.left, col - 1))

D. Line: queue = deque([(root, 0)])

Solution

1. Step 1: Analyze col_table initialization

   The condition resets col_table[col] to empty list if col already exists, erasing previous nodes in that column.

2. Step 2: Understand impact on output

   This causes nodes in the same column to be overwritten, breaking vertical grouping.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct code initializes list only if col not in col_table [OK]

Hint: Resetting list on existing key erases previous nodes [OK]

Common Mistakes:

• Confusing 'if col not in col_table' with 'if col in col_table'
• Not initializing column list properly

5. Examine the following code snippet for level order traversal of an N-ary tree. Which line contains a subtle bug that causes incorrect grouping of nodes by level?

medium

A. Line with 'if not root: return []'

B. Line with 'level_nodes.append(node.val)'

C. Line with 'current_level.append(child) # Bug here'

D. Line with 'current_level, next_level = next_level, deque()'

Solution

1. Step 1: Identify how children are enqueued

   Children should be added to next_level queue, not current_level, to separate levels.

2. Step 2: Understand consequence of bug

   Appending children to current_level causes mixing nodes of different levels in the same queue, breaking level grouping.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct BFS uses separate queues for current and next level [OK]

Hint: Children must be enqueued in next_level, not current_level [OK]

Common Mistakes:

• Appending children to current_level instead of next_level