Binary Tree Right Side View

Problem Link

Binary Tree Right Side View – LeetCode

Problem: Binary Tree Right Side View

Problem Statement

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.

Examples

Example 1

Input:
       1
     /   \
    2     3
     \     \
      5     4

Output: [1, 3, 4]

Example 2

Input: root = []
Output: []

Constraints

• 0 <= number of nodes <= 100

• -100 <= Node.val <= 100

Intuition

The goal is to collect the last (rightmost) node from each level of the tree.
There are two common approaches:

1. BFS (Level Order Traversal) – process nodes level by level.

2. DFS (Right-First Recursive Traversal) – visit right children before left and take the first node encountered at each level.

Approach 1: BFS (Level Order Traversal)

Algorithm

• Use a queue for level order traversal.

• At each level, the last node encountered is the one visible from the right.

Code (Java)

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                if (i == size - 1) {
                    result.add(curr.val);
                }
                if (curr.left != null) q.offer(curr.left);
                if (curr.right != null) q.offer(curr.right);
            }
        }

        return result;
    }
}

Approach 2: DFS (Right-First Recursive Traversal)

Algorithm

• Traverse the tree recursively: right child first, then left.

• Maintain a variable level and a List to hold the result.

• If the current level == result.size(), this is the first node visited at this level → add it to result.

Code (Java)

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<Integer> result) {
        if (node == null) return;

        if (level == result.size()) {
            result.add(node.val);
        }

        dfs(node.right, level + 1, result);
        dfs(node.left, level + 1, result);
    }
}

Time and Space Complexity

For both approaches:

• Time Complexity: O(N) — each node is visited once

• Space Complexity:

  • BFS: O(W) where W is the max width of the tree (for queue)

  • DFS: O(H) where H is the height of the tree (for recursion stack)

Dry Run (for DFS)

Input:

       1
     /   \
    2     3
     \     \
      5     4

Traversal order (DFS, right-first):
1 → 3 → 4 → 2 → 5

• Level 0 → result = [1]

• Level 1 → result = [1, 3]

• Level 2 → result = [1, 3, 4]

Conclusion

• BFS is straightforward and level-based.

• DFS with right-first logic gives an elegant and recursive solution.

Choose based on context:

• BFS is more intuitive for beginners.

• DFS is more space-efficient for narrow trees.