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

Concept Flow - Right Side View of Binary Tree

Start at root node

↓

Level order traversal

↓

For each level:

↓

Visit nodes left to right

↓

Record last node at level

↓

Add node value to result

↓

Move to next level

↓

Repeat until no more nodes

↓

Return collected right side view

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

Execution Sample

DSA Python

def rightSideView(root):
    if not root:
        return []
    queue = [root]
    result = []
    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.pop(0)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            if i == level_length - 1:
                result.append(node.val)
    return result

This code collects the rightmost node value at each level of the binary tree using a queue for level order traversal.

Execution Table

Step	Operation	Node Visited	Queue State	Right Side View Collected	Visual Tree State
1	Start with root	1	[1]	[]	1 / \ 2 3
2	Visit level 1 node	1	[2, 3]	[1]	1 / \ 2 3
3	Visit level 2 node	2	[3, 4, 5]	[1]	1 / \ 2 3 / \ 4 5
4	Visit level 2 node	3	[4, 5, 6]	[1, 3]	1 / \ 2 3 / \ \ 4 5 6
5	Visit level 3 node	4	[5, 6]	[1, 3]	1 / \ 2 3 / \ \ 4 5 6
6	Visit level 3 node	5	[6]	[1, 3]	1 / \ 2 3 / \ \ 4 5 6
7	Visit level 3 node	6	[]	[1, 3, 6]	1 / \ 2 3 / \ \ 4 5 6
8	No more nodes	None	[]	[1, 3, 6]	Traversal complete

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	Final
queue	[1]	[2, 3]	[4, 5, 6]	[]	[]
result	[]	[1]	[1, 3]	[1, 3, 6]	[1, 3, 6]
node	None	1	3	6	None

Key Moments - 3 Insights

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

Because i == level_length - 1 means we are at the last node of the current level, which is the rightmost node visible from the right side. See execution_table rows 2, 4, and 7 where result is updated.

Why do we add left child before right child to the queue if we want the right side view?

We add left child first to keep the natural left-to-right order in the queue. This way, the last node we visit at each level is the rightmost node. This is shown in execution_table rows 3 and 4 where left nodes are added before right nodes.

What happens if the tree is empty?

If the tree is empty (root is None), the function returns an empty list immediately, as shown in the code's first if check and no steps in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the queue state?

A [3, 4, 5]

B [4, 5, 6]

C [2, 3]

D [5, 6]

💡 Hint

Check the 'Queue State' column in execution_table row 4.

At which step is the first right side view value added to the result?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Right Side View Collected' column to see when the first value appears.

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

A It would remain the same

B It would show the leftmost nodes instead

C It would show the rightmost nodes but in reverse order

D It would show the leftmost nodes at each level

💡 Hint

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

Concept Snapshot

Right Side View of Binary Tree:
- Use level order traversal (BFS) with a queue
- Visit nodes level by level, left to right
- Record the last node's value at each level
- Return collected values as right side view
- Handles empty tree by returning []

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 at each level. We use a queue to hold nodes of the current level. For each level, we visit all nodes, add their children to the queue, and when we reach the last node of that level, we add its value to the result list. This process repeats until no nodes remain. If the tree is empty, we return an empty list immediately. This approach ensures we see the nodes visible from the right side of the tree.

Practice

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

easy

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

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

C. All leaf nodes of the binary tree

D. All nodes at the deepest level of the 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: Differentiate from other views

   Unlike left side or leaf views, this specifically shows the rightmost nodes at each level.

3. Final Answer:

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

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 of the following Python code snippets correctly initializes an empty list to store the right side view nodes?

easy

A. right_view = set()

B. right_view = []

C. right_view = ()

D. right_view = {}

Solution

1. Step 1: Identify the correct data structure for ordered collection

   We need a list to store nodes in order, so an empty list is initialized with [].

2. Step 2: Check other options

   {} is a dictionary, () is a tuple, set() is unordered; none fit the requirement.

3. Final Answer:

   right_view = [] -> Option B

4. Quick Check:

   Empty list uses [] [OK]

Hint: Use [] for empty list to store nodes [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Using () which creates an empty tuple
• Using set() which is unordered

3. What is the output of the following code that prints the right side view of the binary tree?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root):
    if not root:
        return []
    from collections import deque
    queue = deque([root])
    right_view = []
    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            if i == level_length - 1:
                right_view.append(node.val)
    return right_view

# Tree:
#     1
#    / \
#   2   3
#    \   \
#     5   4
root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3, None, TreeNode(4)))
print(rightSideView(root))

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 and identify rightmost nodes

   Level 1: Node 1 (only node), Level 2: Nodes 2 and 3, rightmost is 3, Level 3: Nodes 5 and 4, rightmost is 4.

2. Step 2: Collect rightmost nodes in order

   Right side view list is [1, 3, 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:

• Picking leftmost node instead of rightmost
• Appending nodes before checking level end
• Confusing node values at each level

4. Find the error in the following code snippet for right side view and select the fix:

def rightSideView(root):
    if not root:
        return []
    queue = [root]
    right_view = []
    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.pop()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            if i == level_length - 1:
                right_view.append(node.val)
    return right_view

medium

A. Remove the if condition checking i == level_length - 1

B. Replace queue.append(node.left) with queue.insert(0, node.left)

C. Initialize queue as a deque instead of list

D. Replace queue.pop() with queue.pop(0) to pop from front

Solution

1. Step 1: Identify queue operation error

   Using pop() removes last element, but BFS requires removing from front (FIFO).

2. Step 2: Fix by popping from front

   Use pop(0) to remove first element, maintaining correct BFS order.

3. Final Answer:

   Replace queue.pop() with queue.pop(0) to pop from front -> Option D

4. Quick Check:

   Queue pop front for BFS [OK]

Hint: Use pop(0) to dequeue from front in list-based BFS [OK]

Common Mistakes:

• Using pop() removes from end, breaking BFS order
• Appending children incorrectly
• Ignoring level length causing wrong node selection

5. Given a binary tree, how would you modify the right side view algorithm to return the left side view instead? Choose the best approach.

hard

A. Reverse the final right side view list before returning

B. Change the order of adding children to queue: add right child before left child

C. Change the order of adding children to queue: add left child before right child

D. Use a stack instead of a queue for traversal

Solution

1. Step 1: Understand right side view child addition order

   Right side view adds right child before left child to queue, so rightmost nodes appear last at each level.

2. Step 2: Modify to get left side view

   Change to add left child before right child so leftmost nodes appear last at each level and get recorded.

3. Final Answer:

   Change the order of adding children to queue: add left child before right child -> Option C

4. Quick Check:

   Left side view = add left child first [OK]

Hint: Add left child before right child for left side view [OK]

Common Mistakes:

• Reversing the right side view list incorrectly
• Adding right child before left child for left view
• Using stack breaks level order traversal