Binary tree right side view explained: BFS and DFS

In this article

1. Before you start
2. Why interviewers ask this
3. Right side view from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the coding interview patterns and practice guide.

Why interviewers ask this

Right side view looks like a picture question, but it tests whether a candidate can turn a picture into a rule. The LeetCode problem asks you to imagine standing on the right side of a tree and return the values you can see from top to bottom, and the page labels it Medium. The rule hides in the wording: what you see from the right is the last node of each level.

A weak answer follows only right children and fails when a level has no right-subtree node. A strong answer states the rule, picks breadth-first search (BFS) or depth-first search (DFS), and explains the one detail that makes it correct. A Staff-level answer also gives the memory cost of each and says which tree shape hurts which approach.

Right side view from first principles

Right side view

The right side view of a binary tree is the list of the values of the nodes you can see when standing on its right side, which is the rightmost node of every level, ordered from the top level to the bottom one.

Level-size snapshot

A level-size snapshot is the number of nodes in the queue, read once before a breadth-first loop starts a level, so the loop knows exactly how many nodes belong to that level.

In plain words

Picture a building seen from the street on its right. On each floor, the person standing furthest right hides anyone behind them. If a floor has people only on the left, the furthest right of them is still the one you see. The analogy breaks in one place: a tree level is not a physical row, because nodes on it can come from far-apart branches.

In one precise sentence, the right side view is the last node of each level when the nodes of a level are read from left to right. The problem statement's own examples show why following right children is not enough: for the tree [1,2,3,4,null,null,null,5] the output is [1,3,4,5], and the nodes 4 and 5 sit on the left branch. They are visible because the right subtree has no nodes at those depths.

Step 1: Group the nodes by level

Input: the root of the tree. Output: one list of nodes per level. Take the first example from the problem page, [1,2,3,null,5,null,4]. LeetCode writes a tree level by level, left to right, with null for a missing child: 1 is the root, 2 and 3 are its children, 2 has no left child and right child 5, and 3 has no left child and right child 4. Level zero is [1], level one is [2,3] and level two is [5,4]. The rightmost node of each level is 1, 3 and 4, so the answer is [1,3,4].

The node 5 is on level two, but 4 stands to its right, so 4 covers it. The solution write-up by doocs states the rule as the rightmost node of each level, which also means the answer has exactly one value per level. You now know what to produce; the next two steps are two ways to find it. An empty tree has no levels, so its answer is the empty list, as the problem page's fourth example shows.

Step 2: Breadth-first search snapshots the level size

Breadth-first search (BFS) is a traversal that visits all nodes of one level before any node of the next, using a queue. Start with the root in the queue. While the queue is not empty, read its length, call it size, and then pop exactly size nodes. Push each popped node's left child, then its right child. The last node popped in that loop is the rightmost of the level, so record it.

The snapshot is not style. Children pushed during the loop wait for the next pass, and the AlgoMonster write-up says the range(len(q)) loop processes only the nodes that were in the queue when the level began. If you wrote while len(q) inside the level loop, new children would join the current level and the last node popped would be a node from a deeper level. That is the bug the lead warned about.

from collections import deque

def right_side_view(root):
    view = []
    if root is None:
        return view
    q = deque([root])
    while q:
        size = len(q)              # the level-size snapshot
        for i in range(size):
            node = q.popleft()
            if i == size - 1:      # last node of this level
                view.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return view

Input: the root. Output: one value per level. The code takes the last node of each level, as the NeetCode breadth-first solution does.

Step 3: Right-first depth-first search records the first node at each depth

Depth-first search (DFS) is a traversal that follows one branch to its end before trying the next, using recursion or an explicit stack. For this problem visit the right child before the left child, and pass the current depth down. A node is visible when it is the first node seen at its depth. Because the right side is explored first, the first node at any depth is the rightmost one there.

The test is one line: record the node when its depth equals the length of the result list. The NeetCode depth-first code uses if depth == len(res): res.append(node.val) and then calls the right child before the left. The list has one entry per depth already seen, so a new depth is exactly a length match.

def right_side_view_dfs(root):
    res = []
    def dfs(node, depth):
        if node is None:
            return
        if depth == len(res):      # first node seen at this depth
            res.append(node.val)
        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return res

A common slip is to record the last node visited per depth with a left-first search; that works only if you overwrite entries, which is a different and clumsier rule.

Step 4: Each node is visited once, so time is linear

Input: a tree of n nodes. Output: the same view, in time proportional to n. In BFS every node enters the queue once and leaves once; in DFS every node is entered once. Both searches run in O(n) time, and the doocs write-up gives O(n) time and space for its solution.

Space differs by shape, and you can derive it without a source. The BFS queue holds the rest of one level plus the next level's nodes pushed so far, so its size is on the order of the widest level (at most two adjacent levels). The DFS stack holds one frame per level on the current path, so it is the height of the tree: about log n for a balanced tree and n for a chain.

1 · Levels2 · BFS3 · DFS4 · CostReplay

Step-by-step description

1. Group nodes by depth.
2. Snapshot the size, keep the last.
3. Go right first, keep the first.
4. Each node is visited once.

• Levels are groups of nodes at the same depth, and the right side view takes the last node of each.
• Breadth-first search reads the queue length before it pops a level.
• Right-first depth-first search records a node when its depth equals the length of the result list.
• Both searches run in O(n) time.

The four ideas in the figure are: levels are groups of nodes at the same depth, and the right side view takes the last node of each. Breadth-first search reads the queue length before it pops a level. Right-first depth-first search records a node when its depth equals the length of the result list. Both searches run in O(n) time.

Worked example

The script in assets/data/right-side-view-trace.py builds the two example trees from the problem page and runs both searches.¹ For [1,2,3,null,5,null,4] the queue holds 1, then 2, then 2 nodes at the start of the three levels. Level zero pops 1 and records 1. Level one pops 2 and 3 and records 3. Level two pops 5 and 4 and records 4, giving [1,3,4].¹

The right-first depth-first run reaches the same answer in another order. It records 1 at depth zero, goes right to 3 and records it at depth one, goes right to 4 and records it at depth two, then comes back. The node 2 at depth one and the node 5 at depth two are skipped, because the list already has an entry for those depths.¹

The tree sizes beyond the examples are illustrative: the numbers 15, 127, 1,023 and 100 were chosen to show the shape effect, and the peaks were computed.¹ A perfect tree of 1,023 nodes peaks at 512 queued nodes, so the peak queue is about half the nodes of a perfect tree. That is the BFS memory worst case, and it is still O(n).

Text description of the diagram

• A perfect tree of 1,023 nodes peaks at 512 queued nodes.
• The peak queue is about half the nodes of a perfect tree.

Trade-offs and edge cases

Neither search is better everywhere. BFS uses memory for the widest level and DFS uses memory for the height, so a bushy tree favors DFS and a stringy one favors BFS. BFS uses a queue and needs memory for the widest level. DFS uses the call stack and needs memory for the height of the tree.

Text description of the diagram

• Breadth-first search uses a queue and needs memory for the widest level.
• Depth-first search uses the call stack and needs memory for the height of the tree.

Edge cases to name aloud: the empty tree returns []; a single node returns its own value; a tree with only left children returns every node, because each level has one node. The LeetCode constraints are 0 to 100 nodes and values from -100 to 100, so recursion depth never matters there. Outside that site, Python bounds recursion by an interpreter limit that the sys documentation calls the maximum depth of the interpreter stack, and a very deep chain can exceed it; check the value with sys.getrecursionlimit().

Also avoid a plain list as the queue. Removing from the front of a list shifts every other element, which costs O(n) per pop; the collections documentation says lists "incur O(n) memory movement costs for pop(0) and insert(0, v)", while a deque gives appends and pops at either end approximately O(1) performance. The same level-by-level queue idea drives Kahn's algorithm in topological sort, and the lowest common ancestor problem is the next tree question worth practicing.

How to answer it in an interview

The spoken structure: state the rule, pick a search, name the level-size snapshot, give time, then give the space trade-off between the two searches.

Common mistakes

• "I just follow the right child." (wrong) This misses levels where only the left subtree has nodes. (right) "I take the last node of each level, which may be on the left branch."
• "I read the queue length inside the loop." (wrong) Newly pushed children are counted into the current level. (right) "I take the snapshot before the loop, so the level ends where it should."
• "Right-first DFS records the last node per depth." (wrong) It records the first node seen at each new depth. (right) "I record when depth equals the length of the result."
• "DFS always uses logarithmic space." (wrong) The stack follows the height, which is n for a chain. (right) "DFS space is the height; BFS space is on the order of the widest level."
• "A list works as the queue." (wrong) Popping from the front of a list is O(n). (right) "I use collections.deque and popleft."

Follow-up questions

How do you solve binary tree right side view?

Take the rightmost node of every level. Use a queue and a level-size snapshot, recording the last node popped, or a right-first recursive search that records the first node seen at each depth. Either way each node is visited once.

What is the time and space complexity of the right side view?

Time is O(n) because every node is visited once. Space is on the order of the widest level for BFS and the tree height for DFS; both are O(n) in the worst case, and DFS is about log n on a balanced tree.

How do you get the left side view instead?

Swap the child order. In BFS record the first node popped of each level instead of the last. In DFS visit the left child before the right, still recording the first node seen at each depth.

Is BFS or DFS better for right side view?

BFS is easier to explain because levels map straight onto loop passes. DFS is shorter and uses less memory on a balanced tree. For a very deep chain BFS avoids recursion limits, so say which tree shape you expect.

Why use a deque instead of a list as the queue?

A deque pops from the left in constant time, while a list must shift all remaining items. The Python guide to interview questions covers more of these standard library choices, and detecting a cycle in a directed graph is another graph traversal where the traversal order matters. For the next practice problem after trees, try K closest points to origin.

Sources

1. Binary Tree Right Side View (problem 199) — LeetCode, 26 Oct 2026
2. collections: deque objects, Python 3 documentation — Python Software Foundation, 26 Oct 2026
3. sys: getrecursionlimit and setrecursionlimit, Python 3 documentation — Python Software Foundation, 26 Oct 2026
4. 199. Binary Tree Right Side View (solution write-up) — doocs/leetcode, 26 Oct 2026
5. Binary Tree Right Side View: solution and explanation — NeetCode, 26 Oct 2026
6. 102. Binary Tree Level Order Traversal (complexity write-up) — AlgoMonster, 26 Oct 2026