Binary Tree Right Side View

LeetCode 199: Binary Tree Right Side View Solution & Explanation

Problem Overview

TL;DR: Perform a Level Order Traversal (BFS) and record the value of the last node visited at each depth level to construct the view from the right side.

The Binary Tree Right Side View problem asks us to determine which nodes are visible when looking at a binary tree from the right side. This essentially means selecting the rightmost node at every depth of the tree. If the right branch is missing or shorter than the left branch, the nodes from the left branch at deeper levels become visible.

This is a popular interview question that tests your ability to traverse tree data structures and manipulate level-based logic. It is designated as LeetCode 199.

Brute Force Approach for Binary Tree Right Side View

A common naive approach (and a frequent mistake) is to assume the "right side view" simply consists of the nodes found by traversing only the right child pointers starting from the root.

Naive Algorithm Description

1. Start at the root.
2. Add the current node to the result list.
3. Move to node.right.
4. Repeat until the current node is null.

Pseudo-code

function naiveRightView(root):
    result = []
    current = root
    while current is not null:
        result.add(current.val)
        current = current.right
    return result

Complexity Analysis

• Time Complexity: $O(H)$, where $H$ is the height of the tree (specifically the length of the rightmost path).
• Space Complexity: $O(1)$ auxiliary space (excluding result storage).

Why It Fails

This approach fails the correctness test. It assumes the right side view is blocked solely by the immediate right children. However, a binary tree can have a left subtree that is significantly deeper than the right subtree. In such cases, the nodes in the left subtree extend below the right subtree and become visible from the right side. The naive approach completely ignores the left subtree, leading to an incomplete answer.

Algorithm Strategy: Tree BFS - Level Order Traversal

To implement the optimal solution using the BFS pattern:

1. Queue Initialization: Use a queue to facilitate Breadth-First Search. Initialize it with the root node (if not null).
2. Level-by-Level Processing: Use a standard BFS while loop. Inside this loop, determine the number of nodes currently in the queue (levelSize). This count represents exactly one horizontal level of the tree.
3. Inner Loop: Iterate exactly levelSize times to process all nodes at the current depth.
   • Dequeue the current node.
   • Add its children (left, then right) to the queue for the next level.
4. Capture Rightmost Node: Inside the inner loop, check if the current index is the last index of the level (i.e., i == levelSize - 1). If true, add this node's value to the result list.
5. Termination: The algorithm terminates when the queue is empty, meaning all levels have been processed.

Execution Flow

1. Check Edge Case: If root is null, return an empty list immediately.
2. Setup: Create an empty list result. Create a queue q and push root into it.
3. Traverse: While q is not empty:
   • Capture the current size of the queue: n = q.size().
   • Iterate i from 0 to n - 1:
     • Pop node from the front of q.
     • Identification Step: If i equals n - 1, append node.val to result.
     • If node.left exists, push it to q.
     • If node.right exists, push it to q.
4. Return: Return result.

Proof of Correctness

The correctness relies on the FIFO (First-In-First-Out) property of the queue and the order of insertion.

• Invariant: At the start of the outer loop, the queue contains all nodes at depth $D$ and only nodes at depth $D$.
• Ordering: We insert children in Left $\to$ Right order. Consequently, for any depth $D+1$, nodes are stored in the queue ordered from left to right.
• Selection: By iterating through the exact number of nodes present at the start of the level, we ensure we process the entire depth $D$. The last node processed in this iteration is the one that was inserted last for this level, which corresponds to the rightmost physical position in the tree.
• Thus, the algorithm correctly captures exactly one node per level, which is the rightmost one.

Pattern Reuse Notes

The Tree BFS - Level Order Traversal pattern is highly reusable. Understanding how to iterate level-by-level using a queue size snapshot allows you to solve several related LeetCode problems:

• LeetCode 102: Binary Tree Level Order Traversal: The base pattern; simply collects all nodes instead of just the last one.
• LeetCode 103: Binary Tree Zigzag Level Order Traversal: Adds a direction flag to the standard BFS to reverse order every other level.
• LeetCode 515: Find Largest Value in Each Tree Row: Instead of picking the last node, you track the maximum value seen in the inner loop.
• LeetCode 1161: Maximum Level Sum of a Binary Tree: Sums the values in the inner loop to find the level with the highest aggregate value.

Reference Implementation

C++ Solution for LeetCode 199

1#include <vector>
2#include <queue>
3
4using namespace std;
5
6/**
7 * Definition for a binary tree node.
8 * struct TreeNode {
9 *     int val;
10 *     TreeNode *left;
11 *     TreeNode *right;
12 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
13 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
15 * };
16 */
17class Solution {
18public:
19    vector<int> rightSideView(TreeNode* root) {
20        vector<int> result;
21        if (!root) return result;
22        
23        queue<TreeNode*> q;
24        q.push(root);
25        
26        while (!q.empty()) {
27            int levelSize = q.size();
28            
29            for (int i = 0; i < levelSize; ++i) {
30                TreeNode* currentNode = q.front();
31                q.pop();
32                
33                // If it's the last node in the current level, add to result
34                if (i == levelSize - 1) {
35                    result.push_back(currentNode->val);
36                }
37                
38                // Add children to queue for the next level
39                if (currentNode->left) q.push(currentNode->left);
40                if (currentNode->right) q.push(currentNode->right);
41            }
42        }
43        
44        return result;
45    }
46};

Java Solution for LeetCode 199

1import java.util.ArrayList;
2import java.util.LinkedList;
3import java.util.List;
4import java.util.Queue;
5
6/**
7 * Definition for a binary tree node.
8 * public class TreeNode {
9 *     int val;
10 *     TreeNode left;
11 *     TreeNode right;
12 *     TreeNode() {}
13 *     TreeNode(int val) { this.val = val; }
14 *     TreeNode(int val, TreeNode left, TreeNode right) {
15 *         this.val = val;
16 *         this.left = left;
17 *         this.right = right;
18 *     }
19 * }
20 */
21class Solution {
22    public List<Integer> rightSideView(TreeNode root) {
23        List<Integer> result = new ArrayList<>();
24        if (root == null) return result;
25        
26        Queue<TreeNode> queue = new LinkedList<>();
27        queue.offer(root);
28        
29        while (!queue.isEmpty()) {
30            int levelSize = queue.size();
31            
32            for (int i = 0; i < levelSize; i++) {
33                TreeNode currentNode = queue.poll();
34                
35                // If this is the last node in the current level, record it
36                if (i == levelSize - 1) {
37                    result.add(currentNode.val);
38                }
39                
40                if (currentNode.left != null) queue.offer(currentNode.left);
41                if (currentNode.right != null) queue.offer(currentNode.right);
42            }
43        }
44        
45        return result;
46    }
47}

Python Solution for LeetCode 199

1from collections import deque
2from typing import Optional, List
3
4# Definition for a binary tree node.
5# class TreeNode:
6#     def __init__(self, val=0, left=None, right=None):
7#         self.val = val
8#         self.left = left
9#         self.right = right
10
11class Solution:
12    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
13        result = []
14        if not root:
15            return result
16        
17        queue = deque([root])
18        
19        while queue:
20            level_size = len(queue)
21            
22            for i in range(level_size):
23                node = queue.popleft()
24                
25                # If this is the last node in the current level, add to result
26                if i == level_size - 1:
27                    result.append(node.val)
28                
29                if node.left:
30                    queue.append(node.left)
31                if node.right:
32                    queue.append(node.right)
33                    
34        return result