Right Side View of Binary Tree in DSA Go

Mental Model

We want to see the nodes that are 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 (level 0), add node 1 to right side view

Level 0: [1]
Right side view so far: [1]

Why: Root is always visible from the right side

Step 2: Move to level 1, nodes are 2 and 3; pick rightmost node 3

Level 1: [2, 3]
Right side view so far: [1, 3]

Why: At level 1, node 3 is on the right edge

Step 3: Move to level 2, nodes are 5 (from 2) and 4 (from 3); pick rightmost node 4

Level 2: [5, 4]
Right side view so far: [1, 3, 4]

Why: At level 2, node 4 is on the right edge

Result:

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

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func rightSideView(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	result := []int{}
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		size := len(queue)
		var rightmost int
		for i := 0; i < size; i++ {
			curr := queue[0]
			queue = queue[1:]

			// update rightmost at this level
			rightmost = curr.Val

			if curr.Left != nil {
				queue = append(queue, curr.Left)
			}
			if curr.Right != nil {
				queue = append(queue, curr.Right)
			}
		}
		result = append(result, rightmost)
	}
	return result
}

func main() {
	// Construct the tree:
	//       1
	//      / \
	//     2   3
	//      \    \
	//       5    4

	n1 := &TreeNode{Val: 1}
	n2 := &TreeNode{Val: 2}
	n3 := &TreeNode{Val: 3}
	n5 := &TreeNode{Val: 5}
	n4 := &TreeNode{Val: 4}

	n1.Left = n2
	n1.Right = n3
	n2.Right = n5
	n3.Right = n4

	view := rightSideView(n1)
	for i, v := range view {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}

for len(queue) > 0 {

process nodes level by level until no nodes left

size := len(queue)

determine number of nodes at current level

for i := 0; i < size; i++ {

iterate over all nodes at this level

curr := queue[0] queue = queue[1:]

dequeue current node to process

rightmost = curr.Val

update rightmost node value at this level

if curr.Left != nil { queue = append(queue, curr.Left) }

enqueue left child if exists

if curr.Right != nil { queue = append(queue, curr.Right) }

enqueue right child if exists

result = append(result, rightmost)

add rightmost node of this level to result

Output

1 -> 3 -> 4

Complexity Analysis

Time: O(n) because we visit each node exactly once during level order traversal

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

vs Alternative: Compared to a recursive depth-first approach, this level order method is straightforward and uses a queue to track nodes per level, making it easier to identify rightmost nodes.

Edge Cases

Empty tree (root is nil)

Returns empty list since there are no nodes to view

DSA Go

if root == nil { return []int{} }

Tree with only one node

Returns list with that single node value

DSA Go

for len(queue) > 0 { ... } handles single node level

Tree where all nodes only have left children

Returns list of all nodes since each is the rightmost at its level

DSA Go

rightmost = curr.Val updates at each level even if no right child

When to Use This Pattern

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

Common Mistakes

Mistake: Adding the first node at each level instead of the last node
Fix: Update the rightmost node value at each iteration and add it after processing the entire level

Mistake: Using preorder traversal which does not guarantee level order
Fix: Use a queue for level order traversal to process nodes level by level

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 to traverse the tree level by level and record the last node seen at each level.

Practice

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

easy

A. The nodes visible when the tree is viewed from the right side

B. The nodes visible when the tree is viewed from the left side

C. The nodes at the bottom level of the tree

D. The nodes at the top 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: Compare with other views

   Left side view shows nodes from left, bottom view shows lowest nodes, top view shows highest nodes.

3. Final Answer:

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

4. Quick Check:

   Right side view = nodes visible from right [OK]

Hint: Right side view shows last node at each level [OK]

Common Mistakes:

• Confusing right side view with left side view
• Thinking it shows bottom or top nodes only
• Assuming it shows all nodes at each level

2. Which Go code snippet correctly declares a binary tree node struct for the right side view problem?

easy

A. type TreeNode struct { Val int; Left, Right int }

B. type TreeNode struct { Value int; Left, Right TreeNode }

C. type TreeNode struct { Val int; Left, Right *TreeNode }

D. type TreeNode struct { Val int; Left *int; Right *int }

Solution

1. Step 1: Check struct field types

   Tree nodes must have pointers to left and right child nodes, so *TreeNode is correct.

2. Step 2: Validate field names and types

   Val is int, Left and Right are pointers to TreeNode, matching type TreeNode struct { Val int; Left, Right *TreeNode }.

3. Final Answer:

   type TreeNode struct { Val int; Left, Right *TreeNode } -> Option C

4. Quick Check:

   Pointers to child nodes = *TreeNode [OK]

Hint: Use pointers for child nodes in struct [OK]

Common Mistakes:

• Using non-pointer types for children
• Incorrect field names or types
• Using int instead of *TreeNode for children

3. What is the output of the right side view function for this tree?

    1
   / \
  2   3
   \   \
    5   4

Assuming the function returns a slice of node values visible from the right side.

medium

A. [1, 2, 4]

B. [1, 2, 5]

C. [1, 3, 5]

D. [1, 3, 4]

Solution

1. Step 1: Identify nodes visible from right at each level

   Level 1: 1; Level 2: 3 (right child of 1); Level 3: 4 (right child of 3)

2. Step 2: Collect these nodes in order

   The right side view is [1, 3, 4].

3. Final Answer:

   [1, 3, 4] -> Option D

4. Quick Check:

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

Hint: Pick last node at each level from right [OK]

Common Mistakes:

• Choosing left child nodes instead of right
• Including nodes not visible from right
• Mixing node order in output

4. Given this Go function snippet for right side view, what is the bug?

func rightSideView(root *TreeNode) []int {
    var result []int
    var queue []*TreeNode
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == size-1 {
                result = append(result, node.Val)
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return result
}

medium

A. The queue is not initialized properly

B. The function does not check if root is nil before appending

C. The loop condition should be i <= size

D. The function appends left child before right child, so right side view is incorrect

Solution

1. Step 1: Check root nil condition

   The function appends root to queue without checking if root is nil, which can cause runtime error.

2. Step 2: Verify other parts

   Queue initialization and loop conditions are correct; appending left before right is valid for BFS.

3. Final Answer:

   The function does not check if root is nil before appending -> Option B

4. Quick Check:

   Check root nil before use [OK]

Hint: Always check root != nil before BFS queue append [OK]

Common Mistakes:

• Ignoring nil root check causing panic
• Misunderstanding BFS queue order
• Incorrect loop boundary conditions

5. How would you modify the right side view algorithm to return the left side view instead?

hard

A. Change the condition to append node.Val when i == 0 instead of i == size-1

B. Change the order of child node appending to queue: append left child before right child

C. Change the condition to append node.Val when i == size-1 and reverse the queue

D. Change the order of child node appending to queue: append right child before left child

Solution

1. Step 1: Understand right side view logic

   Right side view appends node.Val when i == size-1 (last node at level).

2. Step 2: Modify for left side view

   Left side view requires first node at each level, so append when i == 0.

3. Final Answer:

   Change the condition to append node.Val when i == 0 instead of i == size-1 -> Option A

4. Quick Check:

   Left side view = first node per level [OK]

Hint: Append first node at each level for left side view [OK]

Common Mistakes:

• Only changing child append order without condition change
• Appending last node instead of first for left view
• Reversing queue unnecessarily