Right Side View of Binary Tree in DSA C++

Mental Model

We want to see the nodes visible when looking at the tree from the right side, which means the rightmost node at each level.

Analogy: Imagine standing on the right side of a tall building with many floors; you only see the windows on the right edge of each floor.

      1
     / \
    2   3
     \   \
      5   4

Right side view: 1 -> 3 -> 4

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3; 2 -> null, 5; 3 -> null, 4

Goal: Find the rightmost node at each level to form the right side view list

Step 1: Start level order traversal at root (level 0)

Level 0: [1]
Rightmost node: 1

Why: We begin from the root to explore each level

Step 2: Move to level 1, nodes are 2 and 3

Level 1: [2 -> 3]
Rightmost node: 3

Why: We want the rightmost node at this level, which is 3

Step 3: Move to level 2, nodes are 5 and 4 (children of 2 and 3)

Level 2: [5 -> 4]
Rightmost node: 4

Why: At this level, 4 is the rightmost visible node

Result:

Right side view: 1 -> 3 -> 4

Annotated Code

DSA C++

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

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

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

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);

    vector<int> view = rightSideView(root);
    for (int val : view) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

if (!root) return result;

handle empty tree by returning empty result

q.push(root);

start level order traversal from root

int levelSize = q.size();

determine number of nodes at current level

TreeNode* node = q.front(); q.pop();

process current node and remove from queue

if (node->left) q.push(node->left); if (node->right) q.push(node->right);

enqueue children for next level traversal

if (i == levelSize - 1) { result.push_back(node->val); }

record rightmost node value at this level

Output

1 3 4 

Complexity Analysis

Time: O(n) because we visit each node once during level order traversal

Space: O(n) because the queue can hold up to all nodes at the widest level

vs Alternative: Compared to DFS approach, BFS naturally processes nodes level by level, making it straightforward to pick rightmost nodes without extra depth tracking

Edge Cases

Empty tree

Returns empty list since there are no nodes

DSA C++

if (!root) return result;

Tree with only root node

Returns list with only root value

DSA C++

if (!root) return result;

Tree where some nodes have only left children

Still returns rightmost nodes at each level, which may be left children if no right child exists

DSA C++

if (node->left) q.push(node->left);

When to Use This Pattern

When asked to find visible nodes from one side of a tree, use level order traversal and pick the last node at each level to get the side view.

Common Mistakes

Mistake: Collecting the first node at each level instead of the last for right side view
Fix: Change condition to record node value only when processing the last node at the current level

Mistake: Using preorder DFS without tracking depth and overwriting values incorrectly
Fix: Use BFS or DFS with depth tracking and overwrite values only when deeper level is reached

Summary

Finds the rightmost node at each level of a binary tree to show the right side view.

Use when you need to see which nodes are visible from the right side of a tree.

The key insight is to traverse level by level and pick the last node at each level.