Binary Tree Right Side View

Table of Contents +

Imagine you are standing on the right side of a tree and looking at it. You only see the nodes that are closest to you on each row. That is exactly what this question asks. It sounds like a drawing puzzle. But really it is testing if you understand how to walk a tree level by level.

🎯 The Problem

You get the root of a binary tree. Return the values you would see from the right side, top to bottom.

The rules:

  • A binary tree is a structure where each node has at most two children.
  • A level is all the nodes that sit at the same depth.
  • On each level, the node you see from the right is the last one on that level.
  • The answer lists one value per level, from the top level down.
Input:  root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]


      1
    /   \
   2     3
    \      \
     5      4


Explanation: From the right you see 1, then 3, then 4.

So on level 0 you see 1. On level 1 the rightmost node is 3. On level 2 the only node is 4. That gives [1, 3, 4].

Here is the tree drawn out so you can see each level clearly.

1

2

3

null

5

null

4

🐢 Approach 1: Depth-First, Group By Level (Brute Force)

The idea in one line: walk the tree deep first, group every value by its level, then take the last value from each group.

The idea:

  • A depth-first walk goes deep into one branch before trying the next.
  • As you walk, track which level each node is on.
  • Collect all node values grouped by their level.
  • At the end, take the last value from each group.

Why it is weak:

  • You store every node on every level.
  • But you only ever wanted the last one on each row.
  • So you do extra work and use extra memory for values you never return.

Here is the level-grouping DFS code:

right_side_view_level_groups.py
def right_side_view(root):
    levels = {}
    def dfs(node, depth):
        if node:
            levels.setdefault(depth, []).append(node.val)
            dfs(node.left, depth + 1); dfs(node.right, depth + 1)
    dfs(root, 0)
    return [levels[d][-1] for d in sorted(levels)]

⚡ Approach 2: BFS, Keep the Last Node (Best)

The idea in one line: walk level by level and save only the last node of each level as you go.

The idea:

  • BFS stands for breadth-first search.
  • It visits the whole top level, then the next level, then the next.
  • So it lines up nodes row by row on its own.
  • It uses a queue, a line where the first item in is the first item out.

How it works:

  • Push the root into the queue.
  • Before a level starts, read the queue size. That count is the level’s size.
  • Process exactly that many nodes.
  • The last node you process on that level is the one seen from the right. Save its value.
  • While processing each node, push its left child then its right child.
  • So the next level lines up left to right, and again the last one is the rightmost.

Why it is clean:

  • You grab one value per level, never the whole level.
  • Each node enters and leaves the queue once, so the work is O(n).

This diagram shows how the queue holds one level at a time, and we keep the last node of each level.

Level 0 queue: 1 -> pick 1

Level 1 queue: 2, 3 -> pick 3

Level 2 queue: 5, 4 -> pick 4

Answer: 1, 3, 4

Steps to Solve

  1. If the tree is empty, return an empty list.
  2. Put the root node into a queue.
  3. While the queue is not empty, read its current size. That is the count of nodes on this level.
  4. Loop that many times, pulling one node out each time.
  5. When you pull out the last node of the level, save its value into the answer.
  6. For every node you pull out, push its left child then its right child if they exist.
  7. Repeat until the queue is empty, then return the answer.

This Python version uses a deque, which is a fast double-ended queue, for the level walk.

right_side_view.py
from collections import deque




class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None




def right_side_view(root):
    ans = []
    if root is None:
        return ans
    queue = deque([root])              # start with the root
    while queue:
        level_size = len(queue)        # nodes on this level
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:    # last node of the level
                ans.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return ans




root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(5)
root.right.right = Node(4)


print(right_side_view(root))

The output of the above code will be:

[1, 3, 4]

Let us walk through the Python version line by line so the trick is clear.

We start with if root is None: return ans. If there is no tree, the answer is just an empty list. We stop early so the rest of the code never touches a missing node.

Then queue = deque([root]) puts the root into the queue. The queue holds the nodes we still need to process. Right now that is only the root.

The while queue: loop keeps going as long as there are nodes left. Each turn of this loop handles one full level.

The line level_size = len(queue) is the heart of the trick. At this exact moment, the queue holds only the nodes of the current level. So its length tells us how many nodes are on this level. We grab that number before we start adding children.

The inner for i in range(level_size) loop pulls out exactly that many nodes. We use popleft() so we take from the front, which keeps the order correct.

The check if i == level_size - 1 finds the last node of the level. That last node is the rightmost one. So we add its value to the answer.

The last two if blocks push the children. Left first, then right. This keeps the next level in left-to-right order, so its last node will again be the rightmost. When the loop ends, ans holds the right-side view from top to bottom.

⏱️ Time and Space Complexity

The brute force and the BFS both visit every node once, so both are O(n) in time where n is the number of nodes. The difference is memory. The BFS only ever holds one level of nodes in the queue, which is much tidier. In the worst case a level can hold about half the nodes, so the space is O(n). But you never store every level’s values like the clumsy version does. The clean win here is simplicity, not raw speed.

Approach Time Complexity Space Complexity
Brute force (collect all levels) O(n) O(n)
BFS with last node per level O(n) O(n)

Tip

The level-size trick is worth remembering. Read the queue length before the loop. That single number tells you how many nodes are on the current level, with no extra markers needed.

🧩 Key Takeaways

  • ✅ The right side view is just the last node on each level, from top to bottom.
  • ✅ BFS with a queue lines nodes up level by level for free.
  • ✅ Read the queue size before the level loop to know how many nodes are on that level.
  • ✅ Push the left child then the right child so the last node stays the rightmost.
  • ✅ You only keep one value per level, so the answer stays small.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does the Binary Tree Right Side View problem ask you to return?

    Why: From the right you see the rightmost node on each level, which is the last node of that level.

  2. 2

    Why does BFS line up nodes nicely for this problem?

    Why: BFS processes an entire level before moving to the next, so nodes naturally group by level.

  3. 3

    How do we know how many nodes are on the current level?

    Why: At the start of a level the queue holds only that level's nodes, so its length is the level size.

  4. 4

    What is the time complexity of the BFS solution?

    Why: Each node enters and leaves the queue exactly once, so the work is linear in the node count.

Score: 0 / 4

🚀 What’s Next?

Previous Balanced Binary Tree Next Count Good Nodes in Binary Tree