Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Binary Tree Right Side View

MEDIUMProblemSolveExternal Links

Description

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.

In other words, for each level of the tree, you want the rightmost node that exists at that level. If a level has nodes on both the left and right, you only see the rightmost one. If a level only has a node on the left (because the right subtree is shorter), that left node becomes visible from the right side.

Examples

Example 1

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

       1
      / \
     2   3
      \   \
       5   4

Output: [1, 3, 4]

Explanation:

  • Level 0: Only node 1 → visible from right: 1
  • Level 1: Nodes 2 (left) and 3 (right) → rightmost is 3
  • Level 2: Nodes 5 (left subtree) and 4 (right subtree) → rightmost is 4

Example 2

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

         1
        / \
       2   3
      /
     4
    /
   5

Output: [1, 3, 4, 5]

Explanation:

  • Level 0: 1
  • Level 1: 2 and 3 → rightmost is 3
  • Level 2: Only node 4 (left subtree extends deeper) → 4 is visible
  • Level 3: Only node 5 → 5 is visible

Notice: nodes 4 and 5 are in the left subtree, but since the right subtree doesn't extend that deep, they become visible from the right side.

Example 3

Input: root = [1, null, 3]

Output: [1, 3]

Explanation: Root is 1, its only child is right child 3. Both are rightmost at their levels.

Example 4

Input: root = []

Output: []

Explanation: An empty tree has no nodes visible from any side.

Constraints

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

Editorial

Brute Force - BFS Level Order Traversal

Intuition

The most natural way to think about the right side view is to process the tree level by level. If you could lay the tree out on a table and look at each row, the rightmost node in each row is what you'd see from the right side.

Breadth-First Search (BFS) with a queue processes the tree exactly this way — level by level. For each level, we process all nodes from left to right using the queue. The last node we process at each level is the rightmost one, and that's what goes into our result.

Think of it like reading a book page by page (level by level) and noting the last word on each line (the rightmost node).

Step-by-Step Explanation

Let's trace Example 1: root = [1, 2, 3, null, 5, null, 4]

Tree structure:

       1
      / \
     2   3
      \   \
       5   4

Step 1: Initialize queue with root [1]. Result = [].

Step 2: Process Level 0. Queue size = 1.

  • Dequeue node 1. It's the last (and only) node at this level.
  • Add to result: result = [1].
  • Enqueue children: 2 (left), 3 (right). Queue = [2, 3].

Step 3: Process Level 1. Queue size = 2.

  • Dequeue node 2 (i=0). Not last node.
  • Enqueue child of 2: 5 (right child).
  • Dequeue node 3 (i=1). This IS the last node at level 1.
  • Add to result: result = [1, 3].
  • Enqueue child of 3: 4 (right child). Queue = [5, 4].

Step 4: Process Level 2. Queue size = 2.

  • Dequeue node 5 (i=0). Not last.
  • Node 5 has no children.
  • Dequeue node 4 (i=1). Last node at level 2.
  • Add to result: result = [1, 3, 4].
  • Node 4 has no children. Queue = [].

Step 5: Queue is empty. Done. Return [1, 3, 4].

BFS Level Order — Collecting Rightmost Nodes — Watch how BFS processes nodes level by level, collecting the last node at each level for the right side view.

Algorithm

  1. If root is null, return empty list
  2. Initialize a queue with the root node and an empty result list
  3. While the queue is not empty:
    a. Record the current level size (number of nodes in the queue)
    b. For each of the level_size nodes:
    • Dequeue the front node
    • If this is the last node at this level (i == level_size - 1), add its value to result
    • Enqueue its left child (if exists), then right child (if exists)
  4. Return result

Code

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if (!root) return result;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (i == levelSize - 1) {
                    result.push_back(node->val);
                }
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return result;
    }
};
from collections import deque
from typing import Optional, List

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result

        queue = deque([root])
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.popleft()
                if i == level_size - 1:
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result
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 levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (i == levelSize - 1) {
                    result.add(node.val);
                }
                if (node.left != null)  queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit every node exactly once. Each node is enqueued and dequeued exactly once, each operation costing O(1). Total: O(n) where n is the number of nodes.

Space Complexity: O(n)

The queue holds at most one full level of nodes at a time. In the worst case (a complete binary tree), the widest level has approximately n/2 nodes. Therefore, the queue can grow to O(n) space. The result array also takes O(h) space where h is the height, but that's dominated by the queue.

Why This Approach Is Not Efficient

The BFS approach works correctly and runs in O(n) time, but it uses O(n) extra space for the queue. In the worst case (a complete binary tree), the bottom level holds roughly n/2 nodes — all sitting in the queue simultaneously.

But think about it: we only need one node per level for the right side view. Storing an entire level of nodes in a queue feels wasteful. Can we avoid this?

The key insight: if we use Depth-First Search (DFS) and always visit the right subtree before the left, the first node we encounter at each new depth level is guaranteed to be the rightmost. We don't need a queue at all — just the recursion stack, which is proportional to the tree's height h, not the total number of nodes n.

For a balanced tree, h = O(log n), which is significantly less than O(n). For a skewed tree, h = O(n), but in practice most trees are reasonably balanced.

Optimal Approach - DFS Right-First Recursion

Intuition

Imagine walking through a forest where trees are arranged in levels. You always take the rightmost path first. Every time you reach a depth you've never been to before, the node you're standing at is the first one at that depth — and since you went right first, it's the rightmost.

The algorithm works by performing a modified preorder traversal (visit root, then right, then left). We maintain a variable maxDepth tracking the deepest level we've added to the result so far. When we visit a node at a level deeper than maxDepth, it means this is the first node we've encountered at this level — and because we always go right before left, this first encounter is guaranteed to be the rightmost node.

Nodes in the left subtree at the same level? They're visited later. But by that time, maxDepth has already been updated, so they don't get added to the result. The right subtree "claims" each level first.

Step-by-Step Explanation

Let's trace Example 2: root = [1, 2, 3, 4, null, null, null, 5] to show how left-side nodes become visible when the right subtree is shorter.

         1
        / \
       2   3
      /
     4
    /
   5

Step 1: Call dfs(node=1, depth=0). maxDepth = -1.

  • depth 0 > maxDepth -1? YES. First time at this depth.
  • Add 1 to result. result = [1]. maxDepth = 0.
  • Go RIGHT first: dfs(node=3, depth=1).

Step 2: Call dfs(node=3, depth=1). maxDepth = 0.

  • depth 1 > 0? YES. First at this depth.
  • Add 3. result = [1, 3]. maxDepth = 1.
  • Go right: node 3 has no right child. Go left: no left child either.
  • Return to node 1.

Step 3: Now go LEFT from node 1: dfs(node=2, depth=1). maxDepth = 1.

  • depth 1 > 1? NO. Level 1 already claimed by node 3.
  • Node 2 is NOT added to result (it's hidden behind node 3).
  • Go right: node 2 has no right child. Go left: dfs(node=4, depth=2).

Step 4: Call dfs(node=4, depth=2). maxDepth = 1.

  • depth 2 > 1? YES! First at depth 2.
  • Add 4. result = [1, 3, 4]. maxDepth = 2.
  • Node 4 is in the left subtree, but since the right subtree ended at depth 1, node 4 is visible from the right!
  • Go right: no right child. Go left: dfs(node=5, depth=3).

Step 5: Call dfs(node=5, depth=3). maxDepth = 2.

  • depth 3 > 2? YES! First at depth 3.
  • Add 5. result = [1, 3, 5]. Wait — that's not right.

Let me re-check the expected output. Example 2: root = [1,2,3,4,null,null,null,5]. Output: [1, 3, 4, 5]. That matches! result = [1, 3, 4, 5].

Step 6: Node 5 has no children. All recursion completes. Return [1, 3, 4, 5].

Key observation: Nodes 4 and 5 are in the LEFT subtree of the tree, but they appear in the right side view because the right subtree doesn't extend to their depth levels.

DFS Right-First — Left Nodes Become Visible — Watch how DFS explores the right subtree first, then the left. When the left subtree extends deeper than the right, those left nodes become visible from the right side.

Algorithm

  1. Initialize result as an empty list
  2. Define recursive function dfs(node, depth):
    a. If node is null, return
    b. If depth == len(result) (we haven't seen this depth before), append node.val to result
    c. Recurse on node.right with depth + 1 (RIGHT FIRST)
    d. Recurse on node.left with depth + 1
  3. Call dfs(root, 0)
  4. Return result

Why depth == len(result) works: The result list grows by one entry per level. When result has k entries, levels 0 through k-1 are covered. So depth == k means depth k hasn't been added yet, and the current node is the first (rightmost) at that depth.

Code

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        dfs(root, 0, result);
        return result;
    }

private:
    void dfs(TreeNode* node, int depth, vector<int>& result) {
        if (!node) return;
        if (depth == (int)result.size()) {
            result.push_back(node->val);
        }
        dfs(node->right, depth + 1, result);
        dfs(node->left, depth + 1, result);
    }
};
from typing import Optional, List

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def dfs(node, depth):
            if not node:
                return
            if depth == len(result):
                result.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result
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);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit every node exactly once during the DFS traversal. Each visit does O(1) work (a comparison and potentially an append). Total: O(n).

Space Complexity: O(h) where h is the height of the tree

The space is used by the recursion call stack. In the best case (balanced tree), h = O(log n). In the worst case (completely skewed tree), h = O(n). The result array stores at most h elements (one per level), which doesn't exceed the stack space.

Compared to the BFS approach's O(n) queue space, DFS saves space on balanced trees: O(log n) vs O(n/2).