Trees

• 1: 199. Binary Tree Right Side View

1 - 199. Binary Tree Right Side View

Problem Description

LeetCode Problem Link

Given the root of a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom.

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 ≤ Node.val ≤ 100

Example:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: The nodes visible from the right side are 1, 3, and 4.

Intuition and Approach

Intuition

When viewing a binary tree from the right side, we want to see the rightmost node at each level. Using a queue for level-order traversal (BFS), we can capture the last node at each level to build our right-side view.

Approach

1. Use a queue to perform level-order traversal
2. For each level:
   • Get the current level size
   • Process all nodes at this level
   • Add the last node’s value to our result
3. Return the collected right-side values

/**
 * Definition for a binary tree node.
 * 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 {
        levelSize := len(queue)
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            // If it's the last node in current level, add to result
            if i == levelSize-1 {
                result = append(result, node.Val)
            }
            
            // Add children to queue
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    
    return result
}

Time and Space Complexity

Time Complexity: O(n)

• Visit each node exactly once
• Queue operations are O(1)

Space Complexity: O(w)

• w is the maximum width of the tree
• In worst case (perfect binary tree), the last level has n/2 nodes
• Queue stores at most one level at a time