Binary Tree Right Side View

▶

Steps

setup

Initialize rightside list and start DFS at root

The algorithm initializes an empty list 'rightside' to store the rightmost node values at each depth. It then calls the dfs function starting at the root node (value 1) with depth 0.

💡 Initializing the list and starting DFS sets up the structure to record visible nodes and begins the traversal from the top of the tree.

Line:

rightside = []
dfs(root, 0)

💡 The traversal will explore nodes depth-first, starting at the root, and record nodes as it goes deeper.

fill_cells

Visit root node at depth 0 and record value

At node 1 (depth 0), since depth equals the length of 'rightside' (0), the node's value 1 is appended to 'rightside'.

💡 Recording the first node at depth 0 ensures the root is visible from the right side.

Line:

if depth == len(rightside):
    rightside.append(node.val)

💡 The first node visited at each depth is the rightmost visible node for that level.

traverse

Traverse right child of root (node 3) at depth 1

The algorithm recursively calls dfs on the right child of node 1, which is node 3, increasing depth to 1.

💡 Visiting the right child first ensures the rightmost nodes are considered before left nodes at the same depth.

Line:

dfs(node.right, depth + 1)

💡 Right-first traversal prioritizes nodes visible from the right side.

fill_cells

Visit node 3 at depth 1 and record value

At node 3 (depth 1), since depth equals the length of 'rightside' (1), node 3's value is appended to 'rightside'.

💡 Recording the first node at depth 1 captures the rightmost visible node at this level.

Line:

if depth == len(rightside):
    rightside.append(node.val)

💡 The first node visited at each depth is the rightmost visible node for that level.

traverse

Traverse right child of node 3 (node 4) at depth 2

The algorithm recursively calls dfs on the right child of node 3, which is node 4, increasing depth to 2.

💡 Continuing right-first traversal ensures the rightmost nodes at deeper levels are visited first.

Line:

dfs(node.right, depth + 1)

💡 This traversal order helps capture the right side view efficiently.

fill_cells

Visit node 4 at depth 2 and record value

At node 4 (depth 2), since depth equals the length of 'rightside' (2), node 4's value is appended to 'rightside'.

💡 Recording node 4 captures the rightmost visible node at depth 2.

Line:

if depth == len(rightside):
    rightside.append(node.val)

💡 The first node visited at each depth is the rightmost visible node for that level.

traverse

Traverse left child of node 4 (null) at depth 3

The algorithm attempts to traverse the left child of node 4, which is null, so it returns immediately.

💡 Null children are base cases that stop recursion and backtrack.

Line:

dfs(node.left, depth + 1)

💡 Leaves and null children terminate recursion branches.

traverse

Traverse left child of node 3 (null) at depth 2

After finishing node 4, the algorithm traverses the left child of node 3, which is null, so it returns immediately.

💡 Null children end recursion branches and allow backtracking.

Line:

dfs(node.left, depth + 1)

💡 No nodes to visit here, so recursion backtracks.

traverse

Traverse left child of root (node 2) at depth 1

The algorithm now explores the left child of root node 1, which is node 2, at depth 1.

💡 After finishing the right subtree, the algorithm explores the left subtree to find any visible nodes not yet recorded.

Line:

dfs(node.left, depth + 1)

💡 Left children are visited after right children at the same depth.

compare

Visit node 2 at depth 1 but do not record value

At node 2 (depth 1), since depth (1) is less than the length of 'rightside' (3), node 2's value is not appended.

💡 Only the first node visited at each depth is recorded; node 3 was visited first at depth 1.

Line:

if depth == len(rightside):
    rightside.append(node.val)

💡 Nodes visited later at the same depth are hidden behind earlier rightmost nodes.

traverse

Traverse right child of node 2 (node 5) at depth 2

The algorithm recursively calls dfs on the right child of node 2, which is node 5, increasing depth to 2.

💡 Exploring right children first continues to prioritize rightmost nodes at each level.

Line:

dfs(node.right, depth + 1)

💡 Node 5 is visited after node 4 at the same depth.

compare

Visit node 5 at depth 2 but do not record value

At node 5 (depth 2), since depth (2) is less than the length of 'rightside' (3), node 5's value is not appended.

💡 Node 4 was visited first at depth 2, so node 5 is hidden from the right side view.

Line:

if depth == len(rightside):
    rightside.append(node.val)

💡 Only the first node visited at each depth is visible from the right side.

traverse

Traverse left child of node 5 (null) at depth 3

The algorithm attempts to traverse the left child of node 5, which is null, so it returns immediately.

💡 Null children end recursion branches and allow backtracking.

Line:

dfs(node.left, depth + 1)

💡 Leaves and null children terminate recursion branches.

traverse

Traverse right child of node 5 (null) at depth 3

The algorithm attempts to traverse the right child of node 5, which is null, so it returns immediately.

💡 Null children end recursion branches and allow backtracking.

Line:

dfs(node.right, depth + 1)

💡 Leaves and null children terminate recursion branches.

reconstruct

Return final rightside list

After completing DFS traversal, the algorithm returns the 'rightside' list containing the right side view: [1, 3, 4].

💡 Returning the accumulated list provides the final visible nodes from the right side.

Line:

return rightside

💡 The traversal order and recording logic produce the correct right side view.

from typing import Optional, List
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []  # STEP 1
    def dfs(node, depth):
        if not node:  # STEP 7,8,13,14 base case
            return
        if depth == len(rightside):  # STEP 2,4,6,10,12 check if first node at depth
            rightside.append(node.val)
        dfs(node.right, depth + 1)  # STEP 3,5,9,11 traverse right child first
        dfs(node.left, depth + 1)   # STEP 7,8,13,14 traverse left child next
    dfs(root, 0)  # STEP 1 start DFS
    return rightside  # STEP 15

# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
print(rightSideView(root))  # Output: [1,3,4]

📊

Binary Tree Right Side View - Watch the Algorithm Execute, Step by Step

Watching the traversal order and how the rightmost nodes are recorded at each level helps you understand why this approach efficiently captures the right side view without extra data structures.

Current node: 1

12345

DFS Stack

1 (entered)depth=0

Current node: 1

12345

DFS Stack

1 (entered)depth=0

Result: [1]

Current node: 3

12345

DFS Stack

3 (entered)depth=11 (right_done)depth=0

Result: [1]

Current node: 3

12345

DFS Stack

3 (entered)depth=11 (right_done)depth=0

Result: [1, 3]

Current node: 4

12345

DFS Stack

4 (entered)depth=23 (right_done)depth=11 (right_done)depth=0

Result: [1, 3]

Current node: 4

12345

DFS Stack

4 (entered)depth=23 (right_done)depth=11 (right_done)depth=0

Result: [1, 3, 4]

12345

DFS Stack

4 (right_done)depth=23 (right_done)depth=11 (right_done)depth=0

Result: [1, 3, 4]

12345

DFS Stack

3 (left_done)depth=11 (right_done)depth=0

Result: [1, 3, 4]

Current node: 2

12345

DFS Stack

2 (entered)depth=11 (left_done)depth=0

Result: [1, 3, 4]

Current node: 2

12345

DFS Stack

2 (entered)depth=11 (left_done)depth=0

Result: [1, 3, 4]

Current node: 5

12345

DFS Stack

5 (entered)depth=22 (right_done)depth=11 (left_done)depth=0

Result: [1, 3, 4]

Current node: 5

12345

DFS Stack

5 (entered)depth=22 (right_done)depth=11 (left_done)depth=0

Result: [1, 3, 4]

12345

DFS Stack

5 (right_done)depth=22 (left_done)depth=11 (left_done)depth=0

Result: [1, 3, 4]

12345

DFS Stack

2 (returning)depth=11 (left_done)depth=0

Result: [1, 3, 4]

12345

Result: [1, 3, 4]

Return: [1,3,4]

Key Takeaways

✓ The first node visited at each depth during a right-first DFS is the rightmost visible node at that level.

This insight is hard to see from code alone because it depends on traversal order and depth checks, which are clearer when visualized step-by-step.

✓ Right children are always visited before left children, ensuring the right side view captures the correct nodes without extra data structures.

Plain English explanation: visiting right nodes first means the algorithm sees the rightmost nodes before any others at the same depth.

✓ Nodes visited later at the same depth (like node 2 and node 5) are not added to the result because the depth has already been recorded.

This concrete example from the trace shows why some nodes are hidden behind others from the right side perspective.

Practice

1. Consider the following BFS-based code snippet for checking if two nodes are cousins in a binary tree. Given the tree below and inputs x=4, y=5, what is the final return value of the function? Tree structure: 1 / \ 2 3 / \ 4 5

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 isCousins(root, x, y):
    if not root:
        return False
    queue = deque([root])
    while queue:
        size = len(queue)
        x_parent = y_parent = None
        for _ in range(size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
                if node.left.val == x:
                    x_parent = node
                if node.left.val == y:
                    y_parent = node
            if node.right:
                queue.append(node.right)
                if node.right.val == x:
                    x_parent = node
                if node.right.val == y:
                    y_parent = node
        if x_parent and y_parent:
            return x_parent != y_parent
        if x_parent or y_parent:
            return False
    return False

easy

A. Raises an exception

B. false

C. null

D. true

Solution

1. Step 1: Trace first level

   Queue starts with root (1). After processing, queue contains nodes 2 and 3. Neither 4 nor 5 found yet.

2. Step 2: Trace second level

   Process nodes 2 and 3. Node 2's left child is 4 (x), so x_parent = 2. Node 3's right child is 5 (y), so y_parent = 3. Both parents found and are different.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nodes 4 and 5 are cousins with different parents at same depth [OK]

Hint: Check parents at same BFS level to confirm cousin status [OK]

Common Mistakes:

• Confusing siblings as cousins
• Returning true if only one parent found
• Not resetting parents each level

2. You are given a binary tree and need to find the shortest distance from the root node down to the nearest leaf node. Which algorithmic approach guarantees the optimal solution with minimal time complexity?

easy

A. Breadth-First Search (BFS) stopping at the first encountered leaf node

B. Dynamic Programming storing minimum depths for subtrees and combining results

C. Depth-First Search (DFS) exploring all paths to leaves and returning the minimum depth

D. Greedy approach choosing the child with the smaller value at each step

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the minimum depth to a leaf node, which means the shortest path from root to any leaf.

2. Step 2: Identify the algorithm that finds shortest path in unweighted trees

   BFS explores nodes level by level and stops immediately when it finds the first leaf, ensuring the shortest path is found efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS stops at first leaf -> minimal depth found [OK]

Hint: Shortest path in trees -> BFS with early stop [OK]

Common Mistakes:

• Assuming DFS always finds minimum depth efficiently
• Confusing greedy value-based choice with shortest path
• Thinking DP is needed for simple tree traversal

3. Consider the following Python code for N-ary tree level order traversal. Given the tree root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)]), what is the value of res after the first iteration of the outer while loop completes?

easy

A. [[1]]

B. [[1, 3, 2, 4]]

C. [[3, 2, 4]]

D. [[5, 6]]

Solution

1. Step 1: Trace the first outer loop iteration

   Initially, current_level contains only the root node with value 1.

2. Step 2: Collect values and enqueue children

   We pop node 1, append its value to level_nodes -> [1], and enqueue its children (3, 2, 4) into next_level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After first iteration, res = [[1]] as only root level processed [OK]

Hint: First level contains only root node value [OK]

Common Mistakes:

• Confusing first level with all children nodes

4. What is the space complexity of the optimal BFS approach for computing the average of levels in a binary tree, where n is the number of nodes and w is the maximum width of the tree?

medium

A. O(log n) because the tree height bounds the queue size

B. O(n) because all nodes are stored in the queue at once

C. O(w) because the queue holds at most all nodes at the widest level

D. O(n) due to storing all node values in the result list

Solution

1. Step 1: Identify maximum queue size during BFS

   The queue holds nodes level-by-level; max size is the maximum number of nodes at any level, i.e., width w.

2. Step 2: Consider auxiliary space for result list

   Result list stores one average per level, at most height h, which is ≤ n but smaller than w in wide trees.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Queue size dominates space, bounded by maximum width w [OK]

Hint: Queue size = max nodes at any level = width w [OK]

Common Mistakes:

• Assuming queue holds all nodes simultaneously (O(n))
• Confusing height with width for queue size
• Ignoring space for result list

5. The following code attempts to count good nodes in a binary tree using iterative DFS. Identify the line containing the subtle bug that causes incorrect counting.

medium

A. Line checking if node.val > max_val instead of >= max_val

B. Line updating max_val with max(max_val, node.val)

C. Line pushing node.right onto the stack

D. Line returning count at the end

Solution

1. Step 1: Examine condition for counting good nodes

   The condition uses strictly greater (node.val > max_val), but problem definition includes equality (>=).

2. Step 2: Understand impact of strict inequality

   This causes undercounting when node.val equals max_val, missing some good nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing > to >= fixes counting [OK]

Hint: Check if condition uses >= not > for counting [OK]

Common Mistakes:

• Using > instead of >=
• Not updating max_val before pushing children
• Ignoring null root case