Binary Tree Right Side View

Medium

The problem

Imagine standing on the right side of the tree and looking at it. Return the values of the nodes you can see, from top to bottom.

Example 1
Input: root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]
The rightmost node of each row is 1, then 3, then 4.
Example 2
Input: root = [1, null, 3]
Output: [1, 3]
Example 3
Input: root = []
Output: []

Limits

0 ≤ number of nodes ≤ 100
-100 ≤ node value ≤ 100
A deeper node on the left can be seen if the right side is shorter

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

What do you see from the right? Exactly one node per level.

The idea

Level-order BFS and keep the last node of each level.

Target: O(n) time

Go function shape

func rightSideView(root *TreeNode) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// RightSideView: from the right you see exactly one node per level, the last one in that level.
func RightSideView(root *TreeNode) []int {
	out := []int{}
	if root == nil {
		return out
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue) // everything currently in the queue is one level
		for i := 0; i < size; i++ {
			n := queue[0]
			queue = queue[1:]
			if i == size-1 {
				out = append(out, n.Val)
			}
			if n.Left != nil {
				queue = append(queue, n.Left)
			}
			if n.Right != nil {
				queue = append(queue, n.Right)
			}
		}
	}
	return out
}

Read the lesson: Trees: BFS / DFS