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

Concept Flow - Right Side View of Binary Tree

Start at root node

↓

Initialize queue with root

↓

While queue not empty

↓

Get number of nodes at current level

↓

For each node at this level

↓

Dequeue node

↓

If last node at level, record value

↓

Enqueue left child if exists

↓

Enqueue right child if exists

↓

Repeat for next level

↓

Return collected right side view values

We use a queue to do level order traversal. At each level, we record the last node's value to get the right side view.

Execution Sample

DSA Typescript

function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const queue = [root];
  const result = [];
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!;
      if (i === size - 1) result.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

This code traverses the tree level by level and collects the rightmost node's value at each level.

Execution Table

Step	Operation	Node Visited	Queue Before	Queue After	Right Side View Collected	Visual Tree State
1	Initialize queue with root	1	[]	[1]	[]	1 / \ 2 3 / \ 4 5
2	Start level 1 traversal	1	[1]	[]	[]	1 / \ 2 3 / \ 4 5
3	Enqueue left child 2	1	[]	[2]	[]	1 / \ 2 3 / \ 4 5
4	Enqueue right child 3	1	[2]	[2,3]	[]	1 / \ 2 3 / \ 4 5
5	Record rightmost node at level 1	1	[2,3]	[2,3]	[1]	1 / \ 2 3 / \ 4 5
6	Start level 2 traversal	2	[2,3]	[3]	[1]	1 / \ 2 3 / \ 4 5
7	Enqueue left child 4	2	[3]	[3,4]	[1]	1 / \ 2 3 / \ 4 5
8	No right child for node 2	2	[3,4]	[3,4]	[1]	1 / \ 2 3 / \ 4 5
9	Start level 2 traversal	3	[3,4]	[4]	[1]	1 / \ 2 3 / \ 4 5
10	No left child for node 3	3	[4]	[4]	[1]	1 / \ 2 3 / \ 4 5
11	Enqueue right child 5	3	[4]	[4,5]	[1]	1 / \ 2 3 / \ 4 5
12	Record rightmost node at level 2	3	[4,5]	[4,5]	[1,3]	1 / \ 2 3 / \ 4 5
13	Start level 3 traversal	4	[4,5]	[5]	[1,3]	1 / \ 2 3 / \ 4 5
14	No children for node 4	4	[5]	[5]	[1,3]	1 / \ 2 3 / \ 4 5
15	Start level 3 traversal	5	[5]	[]	[1,3]	1 / \ 2 3 / \ 4 5
16	No children for node 5	5	[]	[]	[1,3]	1 / \ 2 3 / \ 4 5
17	Record rightmost node at level 3	5	[]	[]	[1,3,5]	1 / \ 2 3 / \ 4 5
18	Queue empty, end traversal	-	[]	[]	[1,3,5]	1 / \ 2 3 / \ 4 5

💡 Queue is empty, all levels processed, right side view collected

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 12	After Step 17	Final
queue	[]	[]	[2,3]	[4,5]	[]	[]
rightSideView	[]	[]	[1]	[1,3]	[1,3,5]	[1,3,5]
currentNode	null	1	1	3	5	null

Key Moments - 3 Insights

Why do we record the node value only when it is the last node at the current level?

Because the last node at each level is the one visible from the right side. See execution_table rows 5, 12, and 17 where the rightmost nodes 1, 3, and 5 are recorded.

Why do we enqueue left child before right child if we want the right side view?

We enqueue left child before the right child to process nodes from left to right at each level, ensuring the rightmost node is processed last and recorded. If we enqueued right child first, nodes would be processed right to left, recording leftmost nodes instead. See execution_table steps 3-4 and 7-11.

What happens when the queue becomes empty?

When the queue is empty, it means all nodes have been processed and the traversal ends. This is shown in execution_table step 18 where the queue is empty and the final right side view is returned.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what value is added to the right side view?

A 2

B 1

C 3

D 4

💡 Hint

Check the 'Right Side View Collected' column at step 5 in execution_table

At which step does the queue become empty, ending the traversal?

A Step 16

B Step 17

C Step 18

D Step 15

💡 Hint

Look at the 'Queue After' column in execution_table to find when it becomes []

If we changed the enqueue order to right child before left child, how would the right side view change?

A It would show leftmost nodes instead

B It would remain the same

C It would show nodes in reverse order

D It would be empty

💡 Hint

Refer to key_moments explanation about enqueue order and rightmost node recording

Concept Snapshot

Right Side View of Binary Tree:
- Use level order traversal with a queue
- At each level, record the last node's value
- Enqueue left then right children
- Continue until queue is empty
- Result is list of rightmost nodes per level

Full Transcript

This visualization shows how to find the right side view of a binary tree by traversing level by level. We start with the root in a queue. For each level, we process all nodes, enqueue their children, and record the last node's value. This last node is what we see from the right side. The process repeats until no nodes remain. The final collected values form the right side view.

Practice

1. What does the "Right Side View of Binary Tree" represent?

easy

A. All nodes at the deepest level 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. All leaf nodes of the binary tree

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 deepest level nodes only

2. Which TypeScript syntax correctly defines a binary tree node class for this problem?

easy

A. type TreeNode = { val: number; left?: TreeNode; right?: TreeNode }

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

C. interface TreeNode { val: number; left: TreeNode; right: TreeNode; }

D. class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } }

Solution

1. Step 1: Check class definition syntax

   class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } } uses TypeScript class with proper types and constructor.

2. Step 2: Compare other options

   function TreeNode(val) { this.val = val; this.left = null; this.right = null; } is JavaScript function, not TypeScript class. interface TreeNode { val: number; left: TreeNode; right: TreeNode; } misses nullability. type TreeNode = { val: number; left?: TreeNode; right?: TreeNode } uses type but lacks constructor.

3. Final Answer:

   class TreeNode with constructor and nullable children -> Option D

4. Quick Check:

   TypeScript class with constructor = class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } } [OK]

Hint: Use class with constructor and nullable children for nodes [OK]

Common Mistakes:

• Using JavaScript function instead of TypeScript class
• Not allowing null for left/right children
• Using interface without constructor

3. Given the binary tree below, what is the right side view output?

    1
   / \
  2   3
   \   \
    5   4

function rightSideView(root: TreeNode | null): number[] { const result: number[] = []; if (!root) return result; const queue: (TreeNode | null)[] = [root]; while (queue.length) { const size = queue.length; for (let i = 0; i < size; i++) { const node = queue.shift()!; if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); if (i === size - 1) result.push(node.val); } } return result; }

medium

A. [1, 3, 4]

B. [1, 2, 5]

C. [1, 3, 5]

D. [1, 2, 4]

Solution

1. Step 1: Traverse level by level

   Level 1: node 1; Level 2: nodes 2, 3; Level 3: nodes 5, 4.

2. Step 2: Pick rightmost node at each level

   Level 1 rightmost: 1; Level 2 rightmost: 3; Level 3 rightmost: 4.

3. Final Answer:

   [1, 3, 4] -> Option A

4. Quick Check:

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

Hint: Pick last node at each level during BFS [OK]

Common Mistakes:

• Choosing leftmost nodes instead of rightmost
• Mixing node values from different levels
• Ignoring null children in traversal

4. Identify the bug in this TypeScript code for right side view and select the fix.

function rightSideView(root: TreeNode | null): number[] {
  const result: number[] = [];
  if (!root) return result;
  const queue: TreeNode[] = [root];
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
      if (i === size - 1) result.push(node.val);
    }
  }
  return result;
}

medium

A. Initialize queue as empty array instead of [root]

B. Change queue type to (TreeNode | undefined)[] and check node is not undefined after shift

C. Remove the if condition checking i === size - 1

D. Push left child after right child in the queue

Solution

1. Step 1: Analyze queue.shift() return type

   queue.shift() can return undefined if queue is empty, but here size ensures it's not empty. Still, TypeScript requires checking.

2. Step 2: Fix type safety

   Change queue type to allow undefined and check node is not undefined before accessing properties.

3. Final Answer:

   Change queue type and check node after shift -> Option B

4. Quick Check:

   Type safety requires checking shift result [OK]

Hint: Check shift() result for undefined before use [OK]

Common Mistakes:

• Ignoring possible undefined from shift()
• Removing correct condition for rightmost node
• Changing queue initialization incorrectly

5. You want to find the right side view of a binary tree but only have access to a preorder traversal array with nulls for missing nodes, e.g., [1, 2, null, 5, null, null, 3, null, 4]. How can you adapt your approach to get the right side view?

hard

A. Rebuild the tree from preorder with nulls, then perform BFS right side view

B. Directly pick every second element from the preorder array

C. Use preorder array as is and treat it as right side view

D. Reverse the preorder array and pick first elements

Solution

1. Step 1: Understand preorder with nulls

   The array represents tree nodes with nulls marking missing children, so tree structure is implicit.

2. Step 2: Rebuild tree then apply right side view

   Reconstruct the binary tree from this array, then run BFS to get right side view nodes.

3. Final Answer:

   Rebuild tree from preorder with nulls, then BFS -> Option A

4. Quick Check:

   Need tree structure to find right side view [OK]

Hint: Rebuild tree from traversal before right side view [OK]

Common Mistakes:

• Assuming preorder array directly gives right side view
• Ignoring nulls and tree structure
• Trying to pick nodes without tree reconstruction