Right Side View of Binary Tree in DSA Python

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 and windows. You only see the windows on the right edge of each floor, not the ones behind or to the left.

      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 at root node 1, level 0

Level 0: [1]
Rightmost node: 1

Why: Root is always visible from the right side

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

Level 1: [2, 3]
Rightmost node: 3

Why: At level 1, node 3 is to the right of node 2, so 3 is visible

Step 3: Move to level 2, nodes 5 and 4

Level 2: [5, 4]
Rightmost node: 4

Why: At level 2, node 4 is to the right of node 5, so 4 is visible

Result:

Right side view list: [1, 3, 4]

Annotated Code

DSA Python

from collections import deque

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

def right_side_view(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.popleft()  # dequeue node for current level
            if node.left:
                queue.append(node.left)  # enqueue left child
            if node.right:
                queue.append(node.right)  # enqueue right child
            if i == level_length - 1:
                result.append(node.val)  # last node in level is rightmost
    return result

# Driver code to test the function
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)

print(right_side_view(root))

if not root: return []

handle empty tree edge case

queue = deque([root])

start BFS with root node

for i in range(level_length): node = queue.popleft()

process all nodes at current level

if node.left: queue.append(node.left)

add left child to queue for next level

if node.right: queue.append(node.right)

add right child to queue for next level

if i == level_length - 1: result.append(node.val)

append rightmost node value of current level to result

Output

[1, 3, 4]

Complexity Analysis

Time: O(n) because we visit each node exactly once during BFS

Space: O(n) because in worst case the queue holds all nodes at the last level

vs Alternative: Compared to DFS, BFS naturally processes nodes level by level, making it easier to identify rightmost nodes without extra bookkeeping

Edge Cases

Empty tree

Returns empty list since there are no nodes

DSA Python

if not root:
    return []

Tree with only root node

Returns list with only root value

DSA Python

queue = deque([root])

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 Python

if node.left:
    queue.append(node.left)

When to Use This Pattern

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

Common Mistakes

Mistake: Appending the first node at each level instead of the last node
Fix: Append the node value only when processing the last node in the current level (i == level_length - 1)

Mistake: Using DFS without tracking levels properly, leading to incorrect rightmost nodes
Fix: Use BFS to process nodes level by level or carefully track levels in DFS

Summary

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

Use when you want to see which nodes are visible when looking at the tree from the right side.

The key insight is that the last node processed at each level in a level order traversal is the rightmost visible node.

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