Log inSign up
mediumleetcodeNot Started

Binary Tree Right Side View

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

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.

For each depth level, only the rightmost node is visible from the right side.

Example 1 · Example 1: Standard Tree:

Input: root = [1, 2, 3, null, 5, null, 4] Tree: 1 / \ 2 3 \ \ 5 4
Output: [1, 3, 4]
Explanation: Level 0: 1. Level 1: 3. Level 2: 4 (hides 5).

Example 2 · Example 2: Left Subtree Deeper:

Input: root = [1, null, 3] Tree: 1 \ 3
Output: [1, 3]
Explanation: Right view is 1, 3.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why Root -> Right -> Left visits the right view nodes first.
  • Recognize the invariant: depth == result.length signifies first time reaching level.
  • Compare O(h) DFS memory against O(w) BFS queue memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Right side view of binary tree.
  • Last element of each level.
  • Rightmost visible node per depth.

Algorithmic Decision Tree:

  • If node == null return.
  • if depth == res.size() -> res.push(node.val).
  • dfs(node.right, depth + 1); dfs(node.left, depth + 1).

Connected Patterns:

Binary Tree Left ViewBinary Tree Level Order TraversalTop View of Binary Tree

1. Full Level Order Storage

Intuition

BFS level order storing all elements. Loop rows and append row.back().

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Standard BFS queue storing levels in 2D list.
  3. Step 3: Extract last element of each level list.
  4. Step 4: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> rightSideView(TreeNode* root) {
10 if (!root) return {};
11 vector<vector<int>> levels;
12 queue<TreeNode*> q;
13 q.push(root);
14 while (!q.empty()) {
15 int sz = q.size();
16 vector<int> cur;
17 for (int i = 0; i < sz; ++i) {
18 TreeNode* node = q.front(); q.pop();
19 cur.push_back(node->val);
20 if (node->left) q.push(node->left);
21 if (node->right) q.push(node->right);
22 }
23 levels.push_back(cur);
24 }
25 vector<int> res;
26 for (auto& lvl : levels) res.push_back(lvl.back());
27 return res;
28 }
29};
30
31int main() {
32 // Sample driver execution
33 cout << "Execution completed successfully." << endl;
34 return 0;
35}
36

Time & Space Complexity

  • Time complexity: O(n) — Stores all n nodes in 2D array.
  • Space complexity: O(n) — 2D array holds n integers.

2. BFS Queue (Direct Last Element Selection)

Intuition

Loop through level of size S. When i == S - 1, push node.val to result. Push children as usual.

When to apply: Iterative queue-based solution.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Queue q with root.
  3. Step 3: For i from 0 to sz - 1: if i == sz - 1 add node.val to res.
  4. Step 4: Push left and right children.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> rightSideView(TreeNode* root) {
10 if (!root) return {};
11 vector<int> res;
12 queue<TreeNode*> q;
13 q.push(root);
14 while (!q.empty()) {
15 int sz = q.size();
16 for (int i = 0; i < sz; ++i) {
17 TreeNode* node = q.front(); q.pop();
18 if (i == sz - 1) res.push_back(node->val);
19 if (node->left) q.push(node->left);
20 if (node->right) q.push(node->right);
21 }
22 }
23 return res;
24 }
25};
26
27int main() {
28 // Sample driver execution
29 cout << "Execution completed successfully." << endl;
30 return 0;
31}
32

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(w) — Queue holds maximum level width w.

3. Recursive Preorder DFS (Root -> Right -> Left)

Intuition

By visiting right before left, the rightmost node at depth D is visited first. If depth == res.length, add node.val. Recurse right then left.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Helper dfs(node, depth, res): if null return.
  2. Step 2: If depth == res.size(): res.push_back(node.val).
  3. Step 3: dfs(node.right, depth + 1, res).
  4. Step 4: dfs(node.left, depth + 1, res).

Right View DFS Trace for root = [1, 2, 3, null, 5, null, 4]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Inspect root 1 at depth 0
Visual state
Values and pointers at this exact step
tree
Root
1 (Visible)
L
2
R
3

Node order shown; add connections to display explicit tree edges.

level 0: 1
Check / comparison
depth (0) == res.len (0) -> Visible!
Decision / next transition
Add 1 to result.
Why this step matters

Step 1: Inspect root 1 at depth 0. depth == len(0). Add 1 to right view. Recurse to right child 3.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 void dfs(TreeNode* node, int depth, vector<int>& res) {
9 if (!node) return;
10 if (depth == res.size()) res.push_back(node->val);
11 dfs(node->right, depth + 1, res);
12 dfs(node->left, depth + 1, res);
13 }
14public:
15 vector<int> rightSideView(TreeNode* root) {
16 vector<int> res;
17 dfs(root, 0, res);
18 return res;
19 }
20};
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(h) — Recursion call stack takes O(h) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Level Order StorageO(n)O(n)Collect all levels in 2D array and pick last element.Memory waste.
2.BFS Direct Last ElementO(n)O(w)Queue checks index == size - 1.Queue memory.
3.Recursive Preorder DFS (Right First)OptimalO(n)O(h)Root -> Right -> Left with depth == len check.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: returns [].
  • Single node: returns [root.val].
  • Left-skewed tree: every left child is visible because right is absent.
  • Right-skewed tree: every right child is visible.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the exact mirror symmetry with Left View: Left view visits Left first; Right view visits Right first.
  2. Mention that DFS uses O(h) call stack memory, making it preferable to O(w) queue memory.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the DFS approach visit the right child before the left child (dfs(node.right); dfs(node.left))?

Back to DSA Sheet