Binary Tree Right Side View

📋

Problem

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.

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

Edge cases: Single node tree → output is the single node's valueAll nodes only have left children → output is all nodes in top-down orderAll nodes only have right children → output is all nodes in top-down order

</>

IDE

def rightSideView(root: Optional[TreeNode]) -> List[int]:public List<Integer> rightSideView(TreeNode root)vector<int> rightSideView(TreeNode* root)function rightSideView(root)

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    # Write your solution here
    pass

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> rightSideView(TreeNode* root) {
    // Write your solution here
    return {};
}

function rightSideView(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,2,5]Greedy approach picking leftmost node at each level instead of rightmost.✅ Traverse right child before left child in DFS or pick last node in BFS level traversal.

Wrong: [1,3]Off-by-one error in depth tracking causing last level nodes to be missed.✅ Ensure depth increments correctly and update rightmost node at each level accordingly.

Wrong: [1,2,3]Not handling skewed trees properly, missing nodes on one side.✅ Include checks for null children and traverse both left and right children.

Wrong: Exception or crashNo null root check causing runtime error on empty tree input.✅ Add base case to return empty list if root is null.

Wrong: Timeout or no outputExponential or repeated traversal causing TLE on large input.✅ Use O(n) BFS or DFS with level tracking to ensure linear time complexity.

✓

Test Cases

Focus on handling null and minimal trees correctly before moving on.

Think about tricky tree shapes that can fool greedy or naive traversals.

Optimize your traversal to linear time and avoid repeated work.

t1_01basic

Input{"root":[1,2,3,null,5,null,4]}

Expected[1,3,4]

⏱ Performance - must finish in 2000ms

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.

💡 Think about traversing the tree level by level and capturing the last node at each level.

💡 Use BFS or DFS with tracking of depth to identify the rightmost node per level.

💡 Collect the last node visited at each depth to form the right side view.

Why it failed: Output missing or incorrect nodes at some levels; likely not capturing the rightmost node per level. Fix by ensuring traversal records the last node at each depth.

✓ Correctly identifies the rightmost node at each level.

t1_02basic

Input{"root":[1,2,3,4,5,6,7]}

Expected[1,3,7]

⏱ Performance - must finish in 2000ms

Complete binary tree: rightmost nodes per level are 1 (root), 3 (right child), and 7 (rightmost leaf).

💡 Check the rightmost node at each level in a complete binary tree.

💡 A level order traversal with queue can help identify the last node at each level.

💡 Return the last node value encountered at each depth.

Why it failed: Incorrect output due to not selecting the rightmost node at each level; possibly returning leftmost or first node. Fix by updating the node value at each level as traversal proceeds.

✓ Correctly returns rightmost nodes for a complete binary tree.

t2_01edge

Input{"root":null}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree has no visible nodes, so output is an empty list.

💡 Consider the case when the root is null or empty.

💡 The function should handle null input gracefully and return an empty list.

💡 Add a base case to return [] if root is None.

Why it failed: Function crashes or returns non-empty output on null root. Fix by adding a null check at the start and returning []. This is the empty input test.

✓ Correctly returns empty list for empty tree.

t2_02edge

Input{"root":[42]}

Expected[42]

⏱ Performance - must finish in 2000ms

Single node tree; the only node is visible from the right side.

💡 Test the simplest non-empty tree with one node.

💡 The output should be a list containing just that node's value.

💡 Ensure the function handles single-node trees without error.

Why it failed: Output missing or incorrect for single node tree; possibly empty or multiple values. Fix by returning root.val in a single-element list when no children exist. This is the single element test.

✓ Correctly returns single node value for single node tree.

t2_03edge

Input{"root":[1,2,null,3,null,4,null,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

All nodes only have left children; right side view is all nodes top-down since no right children block view.

💡 Consider a tree skewed to the left only.

💡 Right side view should include all nodes since no right nodes obscure them.

💡 Traverse levels and pick the last node at each level, which will be the left child in this case.

Why it failed: Output missing nodes or incorrect order due to assuming right child presence. Fix by including left child nodes when right child is absent. This is the all-left children test.

✓ Correctly returns all nodes in top-down order for left-skewed tree.

t3_01corner

Input{"root":[1,null,2,null,3,null,4,null,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

All nodes only have right children; right side view is all nodes top-down.

💡 Test a tree skewed to the right only.

💡 Right side view should include all nodes since they are all visible.

💡 Ensure traversal does not skip right children and collects all levels.

Why it failed: Output missing nodes due to incorrect traversal or skipping right children. Fix by always including right child nodes at each level. This is the all-right children test.

✓ Correctly returns all nodes in top-down order for right-skewed tree.

t3_02corner

Input{"root":[1,2,3,4,null,null,5,null,6]}

Expected[1,3,5,6]

⏱ Performance - must finish in 2000ms

Tree where greedy approach picking first child per level fails; rightmost nodes are 1,3,5,6.

💡 Beware of greedy approach that picks first child at each level instead of rightmost.

💡 Use BFS or DFS that tracks all nodes per level to find the rightmost.

💡 Collect the last node visited at each depth, not the first.

Why it failed: Output missing rightmost nodes due to greedy left-first traversal. Fix by traversing right child before left or using level order traversal to get last node per level. This is the greedy trap test.

✓ Correctly identifies rightmost nodes despite left children presence.

t3_03corner

Input{"root":[1,2,3,4,5,6,7,8,null,null,null,null,null,null,9]}

Expected[1,3,7,9]

⏱ Performance - must finish in 2000ms

Test for off-by-one errors in level tracking; rightmost nodes are 1,3,7,9.

💡 Check your indexing and depth tracking carefully.

💡 Ensure depth increments correctly and nodes are assigned to correct levels.

💡 Verify that the last node at each level is recorded, not the first.

Why it failed: Output missing last level nodes due to off-by-one depth errors. Fix by correctly incrementing depth and updating rightmost node at each level. This is the off-by-one depth test.

✓ Correctly tracks levels and rightmost nodes.

t4_01performance

Input{"root":[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Right-skewed tree with n=100 nodes; O(n) BFS or DFS must complete within 2 seconds.

💡 Use O(n) BFS or DFS traversal to avoid timeouts.

💡 Avoid exponential or repeated work; do not traverse nodes multiple times.

💡 Use iterative BFS with queue or DFS with recursion and depth tracking.

Why it failed: TLE due to exponential or repeated traversal; fix by using O(n) BFS or DFS with level tracking. This is the performance complexity test.

✓ Algorithm runs in O(n) time confirming expected complexity.

Practice

1. You are given a binary tree and asked to compute the average value of nodes on each level. Which algorithmic approach guarantees an optimal solution that processes nodes level-by-level and efficiently computes these averages?

easy

A. Depth-first search (DFS) without tracking levels, summing all nodes and dividing by total count.

B. Breadth-first search (BFS) using a queue to traverse nodes level-by-level, summing values per level and dividing by the number of nodes at that level.

C. Greedy approach that picks the maximum node value at each level and averages those maximums.

D. Dynamic programming that stores partial sums of subtrees and combines them bottom-up.

Solution

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

   The problem asks for averages per level, so nodes must be grouped by their depth in the tree.

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

   BFS uses a queue to process nodes level-by-level, allowing summing and counting nodes at each level before moving on.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS naturally groups nodes by level, enabling correct average calculation [OK]

Hint: Level order traversal = BFS with queue [OK]

Common Mistakes:

• Using DFS without level tracking loses level grouping
• Greedy max per level ignores all other nodes
• Bottom-up DP is unnecessary and complex here

2. You are given a binary tree and need to determine if it is symmetric around its center. Which approach best guarantees an optimal solution by comparing nodes in pairs using a queue and terminating early when asymmetry is detected?

easy

A. Recursive depth-first traversal comparing left subtree to left subtree

B. Dynamic programming storing subtree symmetry states bottom-up

C. Greedy traversal checking only the root and immediate children

D. Iterative breadth-first search using a queue to compare mirrored node pairs with early termination

Solution

1. Step 1: Understand the problem requirement

   The problem requires checking if a tree is symmetric, which means the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes efficiently

   Using an iterative BFS with a queue to compare pairs of nodes from left and right subtrees simultaneously allows early detection of asymmetry and avoids unnecessary traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Iterative BFS with paired nodes and early termination is optimal for symmetry check [OK]

Hint: Symmetry requires mirrored node pair comparison [OK]

Common Mistakes:

• Comparing left subtree to left subtree instead of mirrored right subtree
• Using greedy checks that miss deeper asymmetry
• Assuming symmetry can be checked by root and immediate children only

3. The following code attempts to compute the average of levels in a binary tree. Identify the line containing the subtle bug that causes incorrect averages when the tree is empty or null.

medium

A. Line 2: Missing check for empty tree before initializing queue

B. Line 5: Incorrect initialization of level_sum to zero

C. Line 9: Using popleft() instead of pop() on queue

D. Line 13: Appending average without converting to float

Solution

1. Step 1: Check for empty tree handling

   Code initializes queue with root without checking if root is None, causing queue to contain None.

2. Step 2: Consequence of missing check

   When root is None, popleft() returns None, and accessing node.val causes an error.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding "if not root: return []" fixes the bug [OK]

Hint: Always check for empty input before queue initialization [OK]

Common Mistakes:

• Forgetting empty tree check
• Misusing queue methods
• Integer division truncation (not here)

4. Consider this buggy BFS code for finding largest values in each tree row:

def largestValues(root):
    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

What subtle bug could cause incorrect results when running multiple test cases in the same environment?

medium

A. Not resetting the queue between test cases causing leftover nodes to be processed

B. Appending level_max before processing all nodes at the current level

C. Forgetting to check if node.left or node.right is None before appending

D. Using a global variable for res without clearing it before each call

Solution

1. Step 1: Identify use of global variables

   If res is declared globally and not cleared before each call, results accumulate across tests.

2. Step 2: Confirm other lines are correct

   Queue is local and reset per call; children are checked for None; level_max appended after level processed.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Global res not cleared -> incorrect cumulative results [OK]

Hint: Global variables must be reset between test runs [OK]

Common Mistakes:

• Forgetting to clear global or static variables
• Assuming local variables persist incorrectly
• Misunderstanding queue initialization scope

5. What is the time complexity of the optimal iterative BFS approach using two queues for N-ary tree level order traversal, where n is the number of nodes in the tree?

medium

A. O(n) because each node is visited exactly once

B. O(n²) because each node's children are enqueued multiple times

C. O(n log n) due to sorting nodes at each level

D. O(n + m) where m is the maximum number of children per node

Solution

1. Step 1: Identify operations per node

   Each node is enqueued and dequeued exactly once, and its children are iterated once.

2. Step 2: Sum over all nodes

   Since total nodes are n, total operations scale linearly with n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal visits each node once -> O(n) time [OK]

Hint: BFS visits each node once, no repeated work [OK]

Common Mistakes:

• Assuming children are enqueued multiple times causing O(n²)