Algorithm-Day46-Binary-Tree-Right-Side-View-lc-199

Posted on In , Views:

🧩 Problem Description

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

💬 Example

1
2
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
1
2
Input: root = [1,null,3]
Output: [1,3]
1
2
Input: root = []
Output: []

💡 Approach 1: BFS (Level Order Traversal)

We can perform a level-order traversal and take the last node at each level as the visible node from the right side.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

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

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) { // last node in this level
                    result.add(node.val);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

💡 Approach 2: DFS (Right-First Preorder)

We can also use DFS, always visiting right child first so the first node we encounter at each depth is the visible one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 depth, List<Integer> result) {
        if (node == null) return;
        if (depth == result.size()) {
            result.add(node.val);
        }
        dfs(node.right, depth + 1, result);
        dfs(node.left, depth + 1, result);
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — Each node is visited once.
  • Space Complexity: O(h) — h is the height of the tree (O(n) worst case).

✍️ Summary

  • BFS is intuitive and level-based.
  • DFS (right-first) is memory-friendly and elegant.
  • This problem pairs well with:
    • lc-102 — Binary Tree Level Order Traversal
    • lc-103 — Zigzag Level Order Traversal