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.