Right Side View of Binary Tree in DSA Python - Time & Space Complexity

Time Complexity: Right Side View of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the right side view of a binary tree changes as the tree grows.

Specifically, how does the number of steps grow when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import deque

def rightSideView(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    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:
                result.append(node.val)
    return result
    

This code finds the right side view of a binary tree by visiting nodes level by level and recording the last node at each level.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once in a breadth-first manner.
• How many times: Each node is processed exactly one time.

How Execution Grows With Input

As the number of nodes in the tree increases, the code visits each node once, so the total steps grow directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The steps grow linearly as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the right side view grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Since we only take one node per level, the time is O(height) or O(log n)."

[OK] Correct: Even though we record one node per level, we must visit all nodes to know which is last at each level, so the time depends on total nodes, not just height.

Interview Connect

Understanding this time complexity helps you explain how tree traversals work and why visiting all nodes is necessary, a key skill in many coding challenges.

Self-Check

"What if we used a depth-first search instead of breadth-first search? How would the time complexity change?"

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