199. Binary Tree Right Side View

LeetCode #199 - View a binary tree from the right side

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