Right Side View of Binary Tree in DSA C - Execution Trace

Concept Flow - Right Side View of Binary Tree

Start at root node

↓

Traverse level by level

↓

At each level, visit nodes left to right

↓

Record the last node visited at this level

↓

Add recorded node to right side view list

↓

Move to next level

↓

Repeat until all levels visited

↓

Return right side view list

We visit the tree level by level, from left to right, and record the last node at each level to get the right side view.

Execution Sample

DSA C

void rightSideView(TreeNode* root) {
  if (!root) return;
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
      TreeNode* node = q.front(); q.pop();
      if (i == size - 1) printf("%d\n", node->val);
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
  }
}

This code prints the rightmost node at each level of the binary tree.

Execution Table

Step	Operation	Node Visited	Queue State	Right Side View	Visual State
1	Start at root	1	[1]	[]	1
2	Visit level 1, i=0	1	[]	[1]	1
3	Add children of 1	-	[2,3]	[1]	1 / \ 2 3
4	Visit level 2, i=0	2	[3]	[1]	1 / \ 2 3
5	Add children of 2	-	[3,5]	[1]	1 / \ 2 3 \ 5
6	Visit level 2, i=1	3	[5]	[1,3]	1 / \ 2 3 \ 5
7	Add children of 3	-	[5,4]	[1,3]	1 / \ 2 3 \ 5 \ 4
8	Visit level 3, i=0	5	[4]	[1,3]	1 / \ 2 3 \ 5 \ 4
9	Add children of 5	-	[4]	[1,3]	1 / \ 2 3 \ 5 \ 4
10	Visit level 3, i=1	4	[]	[1,3,4]	1 / \ 2 3 \ 5 \ 4
11	No children to add	-	[]	[1,3,4]	1 / \ 2 3 \ 5 \ 4
12	Queue empty, end	-	[]	[1,3,4]	1 / \ 2 3 \ 5 \ 4

💡 Queue is empty, all levels visited, right side view collected.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 10	Final
Queue	[1]	[]	[5]	[]	[]
Right Side View	[]	[1]	[1,3]	[1,3,4]	[1,3,4]
Node Visited	-	1	3	4	-

Key Moments - 3 Insights

Why do we record the node only when i == size - 1?

Because i == size - 1 means we are visiting the last node at the current level, which is the rightmost node visible from the right side. See execution_table rows 2, 6, and 10.

Why do we add left child before right child to the queue?

We add left child first to ensure nodes are visited left to right at each level. This way, the last node visited at each level is the rightmost node. See execution_table rows 3 and 7.

What happens if the tree is empty (root is NULL)?

The queue starts empty, so the while loop never runs and the right side view remains empty. This is why we check if root is NULL before starting. This case is not shown in the table but is important.

Visual Quiz - 3 Questions

Look at the execution_table at Step 6, which node is visited and what is the right side view list?

A Node 2 visited, right side view is [1]

B Node 3 visited, right side view is [1,3]

C Node 5 visited, right side view is [1,3]

D Node 4 visited, right side view is [1,3,4]

💡 Hint

Check the 'Node Visited' and 'Right Side View' columns at Step 6 in execution_table.

At which step does the right side view list first get updated?

A Step 2

B Step 1

C Step 4

D Step 6

💡 Hint

Look at the 'Right Side View' column in execution_table and find when it changes from empty to non-empty.

If we added right child before left child to the queue, how would the right side view change?

A It would show the rightmost nodes but in reverse order

B It would remain the same

C It would show the leftmost nodes instead

D It would show the rightmost nodes correctly

💡 Hint

Think about the order nodes are visited and which node is last at each level in execution_table.

Concept Snapshot

Right Side View of Binary Tree:
- Traverse tree level by level (BFS)
- Visit nodes left to right at each level
- Record last node visited at each level
- Collect these nodes as right side view
- Use a queue to track nodes per level

Full Transcript

The right side view of a binary tree is found by visiting the tree level by level, from left to right, and recording the last node visited at each level. We use a queue to hold nodes of the current level. For each level, we visit all nodes, adding their children to the queue for the next level. When visiting nodes at a level, the last node visited is the rightmost node visible from the right side. We collect these nodes into a list. The process repeats until all levels are visited and the queue is empty. This approach ensures we see the tree as if looking from the right side.

Practice

1. What does the "Right Side View" of a binary tree represent?

easy

A. All leaf nodes of the tree

B. Nodes visible when the tree is viewed from the left side

C. Nodes visible when the tree is viewed from the right side

D. Nodes at the deepest level only

Solution

1. Step 1: Understand the view perspective

   The right side view shows nodes visible when looking at the tree from the right side.

2. Step 2: Identify visible nodes

   Only the rightmost node at each level is visible from the right side.

3. Final Answer:

   Nodes visible when the tree is viewed from the right side -> Option C

4. Quick Check:

   Right side view = rightmost nodes [OK]

Hint: Right side view shows rightmost nodes at each level [OK]

Common Mistakes:

• Confusing right side view with left side view
• Thinking it shows all leaf nodes
• Assuming it shows only deepest nodes

2. Which of the following C code snippets correctly declares a binary tree node structure for use in right side view algorithms?

easy

A. typedef struct Node { int val; struct Node* left; struct Node* right; } Node;

B. struct Node { int val; Node* left; Node* right; }; typedef Node;

C. typedef struct { int val; struct Node* left; struct Node* right; } Node;

D. struct Node { int val; struct Node left; struct Node right; }; typedef struct Node Node;

Solution

1. Step 1: Check struct declaration syntax

   typedef struct Node { int val; struct Node* left; struct Node* right; } Node; correctly declares a struct with pointers to left and right child nodes.

2. Step 2: Verify typedef usage

   typedef struct Node { int val; struct Node* left; struct Node* right; } Node; uses typedef properly to alias struct Node as Node.

3. Final Answer:

   typedef struct Node { int val; struct Node* left; struct Node* right; } Node; -> Option A

4. Quick Check:

   Correct struct with pointers and typedef [OK]

Hint: Use struct with pointers and typedef for node [OK]

Common Mistakes:

• Missing struct keyword before pointer types
• Using struct members as values instead of pointers
• Incorrect typedef syntax

3. Given the following binary tree and code snippet, what is the output of the right side view function?

    1
   / \
  2   3
   \   \
    5   4

// Function call: rightSideView(root);

medium

A. [1, 2, 4]

B. [1, 2, 5]

C. [1, 3, 5]

D. [1, 3, 4]

Solution

1. Step 1: Identify rightmost nodes at each level

   Level 0: Node 1; Level 1: Node 3; Level 2: Node 4.

2. Step 2: Collect nodes in order

   The right side view list is [1, 3, 4].

3. Final Answer:

   [1, 3, 4] -> Option D

4. Quick Check:

   Rightmost nodes per level = [1, 3, 4] [OK]

Hint: Pick rightmost node at each tree level [OK]

Common Mistakes:

• Choosing left child nodes instead of rightmost
• Including nodes not visible from right side
• Confusing node values at levels

4. The following C function attempts to print the right side view of a binary tree but has a bug. What is the error?

void rightSideViewHelper(Node* root, int level, int* maxLevel) {
    if (!root) return;
    if (level > *maxLevel) {
        printf("%d ", root->val);
        *maxLevel = level;
    }
    rightSideViewHelper(root->left, level + 1, maxLevel);
    rightSideViewHelper(root->right, level + 1, maxLevel);
}

medium

A. The function visits left child before right, so right side nodes may be missed

B. The maxLevel pointer is not updated correctly

C. The base case does not check for null root

D. The printf statement is missing a newline character

Solution

1. Step 1: Analyze traversal order

   The function visits left child before right child, so rightmost nodes may be overshadowed by left nodes.

2. Step 2: Understand impact on right side view

   Right side view requires visiting right child first to capture rightmost nodes at each level.

3. Final Answer:

   The function visits left child before right, so right side nodes may be missed -> Option A

4. Quick Check:

   Visit right child first for correct right side view [OK]

Hint: Traverse right child before left child [OK]

Common Mistakes:

• Visiting left child before right child
• Not updating maxLevel properly
• Ignoring base case for null nodes

5. You want to modify a function that returns the right side view of a binary tree to also return the left side view in a single traversal. Which approach is best?

hard

A. Perform two separate traversals: one right-first for right view, one left-first for left view

B. Use a single traversal visiting both children and track first node at each level for left and last for right

C. Use a single traversal visiting right child first, store rightmost nodes, then visit left child for leftmost nodes

D. Traverse only left child and assume it covers both views

Solution

1. Step 1: Understand views require different nodes

   Right view needs rightmost nodes; left view needs leftmost nodes at each level.

2. Step 2: Use single traversal with tracking

   Track first node seen at each level for left view and last node for right view during one traversal.

3. Step 3: Avoid separate traversals for efficiency

   This approach reduces time by combining both views in one pass.

4. Final Answer:

   Use a single traversal visiting both children and track first node at each level for left and last for right -> Option B

5. Quick Check:

   Track first and last nodes per level in one traversal [OK]

Hint: Track first and last nodes per level in one traversal [OK]

Common Mistakes:

• Doing two full traversals unnecessarily
• Visiting only one child and missing nodes
• Not tracking nodes per level properly