Binary Tree Right Side View Using Level‑Order Traversal in Go

Problem Statement

A binary tree is a layered structure; to see the rightmost node at each depth, we need the "right side view" – the list of node values that would be visible when looking at the tree from the right.

Algorithm Idea

Using a level‑order (breadth‑first) traversal, we process nodes layer by layer. For each layer we record the value of the last node visited, because that node is the rightmost one for that depth.

Level‑Order Traversal Skeleton (Go)

// Record nodes
nodes := []*TreeNode{}
nodes = append(nodes, root)
for len(nodes) != 0 {
    // Number of nodes in the current layer
    count := len(nodes)
    for i := 0; i < count; i++ {
        // While traversing the current layer, add its left child
        if nodes[i].Left != nil {
            nodes = append(nodes, nodes[i].Left)
        }
        // ...and its right child
        if nodes[i].Right != nil {
            nodes = append(nodes, nodes[i].Right)
        }
    }
    // After the loop, discard the processed nodes; the slice now holds the next layer
    nodes = nodes[count:]
}

Complete Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    // Level‑order traversal
    result := []int{}
    if root == nil {
        return result
    }
    nodes := []*TreeNode{}
    nodes = append(nodes, root)

    for len(nodes) != 0 {
        count := len(nodes)
        for i := 0; i < count; i++ {
            // The last node of this layer is part of the right‑side view
            if i == count-1 {
                result = append(result, nodes[i].Val)
            }
            if nodes[i].Left != nil {
                nodes = append(nodes, nodes[i].Left)
            }
            if nodes[i].Right != nil {
                nodes = append(nodes, nodes[i].Right)
            }
        }
        // Remove the nodes that have been processed for this layer
        nodes = nodes[count:]
    }
    return result
}

Explanation of the Code

The function first checks for an empty tree and returns an empty slice. It then initializes a slice nodes to hold the current layer's nodes, starting with the root.

Inside the outer for loop, count records how many nodes belong to the current depth. The inner loop iterates over those nodes. When the loop index i reaches count‑1, the node is the rightmost one for that layer, so its value is appended to result.

During the same iteration, the algorithm enqueues the left and right children of each node, building the slice for the next depth. After processing the whole layer, the slice is trimmed with nodes = nodes[count:], discarding the nodes already visited and leaving only the next layer's nodes for the next iteration.

When the queue becomes empty, all layers have been processed and result contains the binary tree's right side view.