Problem #199: Binary Tree Right Side View

Intuition & Strategy Breakdown

Use BFS level order traversal. The last node visited at each depth level corresponds to the visible node from the right side.

Python Solution

from collections import deque

def rightSideView(root):
    if not root:
        return []
    
    res = []
    q = deque([root])
    
    while q:
        level_size = len(q)
        for i in range(level_size):
            node = q.popleft()
            
            # If it's the last node of the level
            if i == level_size - 1:
                res.append(node.val)
            
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            
    return res

Java Solution

class Solution {
    public List rightSideView(TreeNode root) {
        List res = new ArrayList<>();
        if (root == null) return res;
        
        Queue q = new LinkedList<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = q.poll();
                
                if (i == levelSize - 1) {
                    res.add(node.val);
                }
                
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
        }
        return res;
    }
}