199. Binary Tree Right Side View - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Definition: Given the root of a binary tree, imagine yourself standing on the right side of it. The task is to return the values of the nodes you can see, ordered from top to bottom. In other words, for each level of the tree, we want the rightmost node (the node that would be visible when viewing the tree from the right side).

Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation: The tree structure is:

From the right side, the visible nodes are 1 (top level), then 3 (second level, as it is to the right of 2), and then 4 (third level). Nodes 2 and 5 are hidden behind 3 and 4 when viewed from the right side.

Example 2:
Input: root = [1, null, 3]
Output: [1, 3]
Explanation: The tree has a root 1 and a right child 3. From the right side, you see 1 at the top, and 3 as the node on the next level (there is no left child to block it).

Example 3:
Input: root = [] (empty tree)
Output: []
Explanation: No nodes exist, so there is nothing to see from the right side.

Constraints

The number of nodes in the tree is in the range [0, 100]. (This means the tree can be empty or have up to 100 nodes.)
Each node’s value is between -100 and 100.
The tree can be skewed (all nodes in one branch) or balanced; it can have any structure as long as it is a valid binary tree.

Hints

Think Level-by-Level: How can you traverse the tree one level at a time? If you process nodes level-by-level (like in a level order traversal), you can easily identify the last node in each level. That last node is the one visible from the right side.
Use a Queue for BFS: A Breadth-First Search (BFS) using a queue is perfect for level order traversal. Consider using a queue to store nodes of the current level, then move to the next level. The last node you encounter at each level is part of the right side view.
Consider Depth Tracking: Alternatively, you could use Depth-First Search (DFS) and keep track of depth. If you always visit the right child first (before the left child), then the first node you encounter at each depth will be the rightmost node at that depth. You can record it and then continue the traversal.
One Node per Level: No matter the approach, remember that the result will have at most one node from each depth/level of the tree. This can guide your logic – you only pick one node (the correct one) per level.

Try to sketch out or visualize a small tree and simulate your approach (either BFS or DFS) to see how you would collect the visible nodes.

Multiple Approaches

Approach 1: Breadth-First Search (BFS - Level Order Traversal)

Using BFS (level order traversal) is a straightforward way to solve this problem. The idea is to traverse the tree level by level and always take the last node in each level (the rightmost node) for the result. This works because BFS naturally groups nodes by their depth/level.

How it works: You maintain a queue for the current level of nodes. For each level:

Iterate through all nodes in the queue (which represents the current level).
Enqueue their children for the next level (first left child, then right child, so that the queue preserves left-to-right order within the level).
While iterating, keep track of the current node. By the time you finish a level, the current node will be the last node of that level (the rightmost one). Add that node’s value to the right side view list.
Move to the next level (the children you enqueued). Continue until there are no more nodes.

Why it works: In a level order traversal, nodes are visited from left to right at each level. So the last node visited at a given depth is the rightmost node at that depth. By capturing that node, we effectively see what a person on the right side would see for that level.

When to use BFS: BFS is intuitive for this problem because it directly gives you level groupings. It’s often preferable when you want to process or collect results level-by-level. If the tree is very wide (lots of nodes at each level), BFS will use more memory to store the queue, but given the constraints (max 100 nodes) this is not an issue. BFS is a good choice when you want the result in top-to-bottom order (which is exactly what we need here, since we add one node per level in increasing depth order).

Approach 2: Depth-First Search (DFS - Recursive)

DFS can also solve the problem by exploring one branch of the tree deeply before others. To get the right side view using DFS, we should ensure we visit the right side of each level first. There are a couple of ways to do this:

Right-first DFS: Perform a DFS traversal where you visit a node’s right child before its left child. Keep track of the current depth in the recursion. If you reach a node at a depth you haven’t seen before (i.e., the depth is greater than the current size of the result list), that node is the first one encountered at that depth – which, because of the right-first order, is the rightmost node at that level. Add it to the result. Then continue DFS to left child. This way, you add the visible node for each depth as you go.
Left-first DFS with overwrite: Alternatively, you could do a normal pre-order traversal (visit root, then left, then right) but use an array or list indexed by depth. Continuously update the value at each depth so that by the end of traversing a level, the last value set for that depth is from the rightmost node. (This method is a bit trickier to implement correctly, but it’s another way to think about it. Essentially, left nodes get added first, but then right nodes at the same level overwrite them, leaving the rightmost node’s value.)

Why DFS works: DFS will eventually visit all nodes. By controlling the order of traversal (visiting right side first), you ensure that when you first visit a certain depth, you are on the rightmost node of that level. Any other node at the same depth will be to its left and will be visited later (so you’d ignore those for right-side view because you already recorded the rightmost one).

When to use DFS: DFS is useful if you prefer recursion or want to reduce the use of extra data structures like queues. It can be slightly more complex to implement correctly for this specific problem but is quite efficient. DFS might be preferable if the tree is very skewed (like a linked list shape) because the recursion depth would equal the height of the tree, and you won’t ever hold many nodes in memory at once (though in the worst case of a skewed tree, BFS and DFS both handle at most O(n) nodes in memory). Another scenario to prefer DFS might be if you were already using DFS for other related computations and want to integrate this logic in one pass. However, for clarity in this problem, BFS is often the go-to solution.

BFS vs DFS – Which to Choose?

Both approaches have the same time complexity (they visit each node exactly once). The choice often comes down to clarity and the tree’s shape:

BFS is typically easier to understand for level-related problems since it directly deals with levels. If you need the result in level order (top to bottom), BFS naturally provides that ordering.
DFS requires careful handling of depth but can be done in one pass without an explicit queue. It uses the call stack for recursion. If recursion depth is not a concern (tree height <= 100 here, which is fine), DFS is quite elegant too.
In terms of space, BFS may use extra space proportional to the width of the tree (worst-case O(n) in the queue if one level has n/2 nodes). DFS uses space proportional to the height of the tree for the recursion stack (worst-case O(n) in a skewed tree). For balanced trees, height is smaller than total nodes, so DFS might use less space. But with at most 100 nodes, these differences are minor.
Summary: Use BFS for a straightforward level-by-level solution (easy to reason about the rightmost element of each level). Use DFS if you want a recursive solution and are comfortable managing depth logic (often, DFS solutions are concise as well). Both will produce the correct result.

Step-by-Step Walkthrough (Example)

Let’s walk through Example 1 ([1,2,3,null,5,null,4]) using the BFS approach to see how the right side view is determined:

The tree looks like this (right side view nodes marked with <---):

    1            <--- visible
   / \
  2   3         <--- visible
   \   \
    5   4       <--- visible

We expect the output [1, 3, 4] for the right side view. Now, let's simulate the BFS traversal:

Initialize: Start with the root in a queue. queue = [1]. The right side view list result is empty. Depth = 0 (root level).
Level 0: The queue has 1 node (the root).
- Dequeue 1. It’s the only node at this level, so when we finish this level, 1 will be the last node we saw. Add its children to the queue for the next level. Children of 1 are 2 (left) and 3 (right), so enqueue them.
- End of level 0: The last node we saw was 1, so we add 1 to result.
- Now result = [1]. Queue for next level: queue = [2, 3].
Level 1: The queue has 2 nodes: [2, 3].
- Dequeue 2 (first node of this level). Enqueue its children. Node 2 has no left child (null) and a right child 5, so enqueue 5.
- Next, dequeue 3. Enqueue its children. Node 3 has no left child (null) and a right child 4, so enqueue 4.
- End of level 1: The last node processed was 3 (after 2), so 3 is the rightmost node of this level. Add 3 to result.
- Now result = [1, 3]. Queue for next level: queue = [5, 4] (Note: 5 was enqueued before 4, but both are in the queue for the next level).
Level 2: The queue has 2 nodes: [5, 4].
- Dequeue 5. Enqueue its children if any. (Node 5 is a leaf, so no children to add.)
- Next, dequeue 4. Enqueue its children if any. (Node 4 is also a leaf, so no children.)
- End of level 2: The last node processed in this level was 4, so 4 is the visible node on the right side for this level. Add 4 to result.
- Now result = [1, 3, 4]. Queue for next level: queue = [] (no more nodes).
End: The queue is empty, meaning we have processed all levels of the tree. The result now contains the right side view: [1, 3, 4], which matches the expected output.

Visualization of BFS Progress:

After level 0: seen 1 → right side view so far [1]
After level 1: seen 2, 3 → right side view now [1, 3] (3 was last on that level)
After level 2: seen 5, 4 → right side view now [1, 3, 4] (4 was last on that level)

Each level's last node is what we append to the result.

DFS walkthrough (brief): If we did the same example with DFS (right-first), the traversal order would be: visit 1 (depth 0) → visit 3 (depth 1, right child of 1) → visit 4 (depth 2, right child of 3). At this point, we've seen a node at depths 0,1,2 (these are 1, 3, 4 respectively). Then DFS would backtrack and visit 3's left (none), then backtrack to 1 and visit 2 (depth 1, left child of 1), then 2's right child 5 (depth 2). But by depth 2, we already encountered a node (4) so we wouldn't add 5. The result collected would still be [1, 3, 4]. This shows how DFS right-first would pick up the correct nodes as well.

Python Implementation

Python3

. . . .

Java Implementation (BFS)

Java

. . . .

Explanation: The Java solution uses a Queue<TreeNode> for BFS. We use levelSize = queue.size() to determine the number of nodes at the current level. We iterate that many times, polling from the queue and adding children to the queue. The variable currentNode is updated to the node being processed; after the loop, it will represent the last node of that level. We then add currentNode.val to result. This ensures we record the rightmost node of each level. The buildTree helper in main creates a binary tree from an array of Integer, where null indicates no child, to facilitate testing the examples.

Both implementations use the same logic: level-by-level traversal and picking the last node of each level. They handle edge cases like an empty tree (immediately returning an empty list). You can run the provided main tests to verify the output for the example cases.

Complexity Analysis

Time Complexity: Both BFS and DFS approaches visit each node exactly once, so the time complexity is O(n) where n is the number of nodes. In Example 1, for instance, each of the 5 nodes is enqueued/dequeued once in BFS. In general, every node is processed a constant number of times (a few queue operations or recursive calls), so it’s linear in the size of the tree.

Space Complexity:

BFS: Uses a queue to hold at most one level of nodes at a time. In the worst-case (a completely balanced tree), the last level might have about n/2 nodes, so the queue could be O(n) in size. Therefore, BFS has O(n) space complexity in the worst case . However, on average for a balanced tree, the space is proportional to the width of the tree. The output list of size at most O(h) (h = height of tree) is also used, but asymptotically O(n) in worst case where the tree is skewed and height ~ n.
DFS: Uses recursion (or an explicit stack) which takes space proportional to the height of the tree. In the worst case of a skewed tree (like a chain), the height is n, so the recursion stack is O(n). For a balanced tree, the height is about O(log n), so space usage would be O(log n) in that scenario. Thus, DFS space complexity is O(h) where h is height of tree. The result list is the same as BFS, O(h) <= O(n).

Given the problem’s constraints (n up to 100), both time and space usage are very manageable. The algorithms run efficiently for all allowed input sizes.

Common Mistakes

Modifying the queue/list during iteration: When using BFS, a classic mistake is altering the queue in the middle of iterating over it. For example, using a for-each loop on the queue while also adding/removing elements can mess up the iteration order. Always determine the number of nodes at the current level first (e.g., level_size = len(queue)) and then loop that many times to process the current level. This ensures you’re not iterating over a changing collection.
Wrong traversal order in DFS: If you do a DFS but visit the left child before the right child, you’ll end up recording left-side nodes instead. To get the right side view, make sure to traverse the right subtree first. A mistake here would yield a left view or mixed view instead of the right view.
Not handling null properly: Forgetting to check for null (None) nodes can lead to errors. Both BFS and DFS implementations should handle the case when a node doesn’t have a left or right child (e.g., only enqueue children that exist, and in DFS, check if a node is null before recursing). Also, remember to handle the case when the input root itself is null (return an empty list).
Confusing depth indexing: In DFS solutions that use a list indexed by depth, it’s easy to get indices wrong or forget to increase depth. One common bug is not realizing that the list result grows only when you encounter a new depth for the first time. If you accidentally append for every node regardless of depth, or use the wrong condition, the logic breaks. The correct pattern is typically: “if this is the first node at this depth, add it to result”.
Off-by-one errors: When writing the loop for BFS, ensure you add the right node. For instance, adding the first node of each level instead of the last node is a common logic mix-up. Double-check that you update the rightmost node at each level and add it after processing the level.

By being mindful of these pitfalls – especially the iteration over the queue and the traversal order – you can avoid the most common mistakes.

Edge Cases

Consider these edge scenarios to ensure your solution handles them gracefully:

Empty Tree: If root is None/null, the output should be an empty list. Both BFS and DFS should return immediately in this case. (Our implementations do that by checking if not root or if(root==null) at the start.)
Single Node: A tree with only one node (just the root) should return a list with that single value. There are no other levels to consider. e.g., Input [1] should output [1].
All Nodes on Left Side (Left-skewed tree): For example, a tree that is a straight line going left:
```
    1
   / 
  2
 / 
3
```
Even though all nodes are left children, from the right side you would actually see all of them, because each node is the only node on its level (there is nothing to its right at the same depth). So the output would be [1, 2, 3]. Make sure your logic doesn’t mistakenly think that if a right child is missing, it shouldn’t record the left child. In BFS, the left child will end up being the last node of that level if no right sibling exists. In DFS (right-first), you will eventually visit the left child for that level as the only node if the right child is absent, and if it’s the first encountered at that depth it will be added.
All Nodes on Right Side (Right-skewed tree): For a tree that is a straight line to the right, e.g. 1 -> 3 -> 5 -> 7, obviously the right side view is all those nodes [1,3,5,7] because we are basically looking at the tree from the right and all nodes align. Both BFS and DFS trivially handle this (each level has one node which is also the rightmost).
Mixed Skewed Tree: A tree where some nodes only have one child. For example:
```
  1
   \
    2
   /
  3
```
Here, root 1 has a right child 2, and 2 has a left child 3. The levels are: [1], [2], [3]. The right side view would be [1, 2, 3] because at level 2, even though the node is a left child of 2, there is no node to its right at the same level (2 has no right child), so it becomes visible. Ensure your logic doesn’t automatically skip a left child’s value when it’s actually visible due to absence of a right sibling.
Wide Tree: A tree with multiple nodes per level, to ensure the code correctly picks the rightmost one. For instance:
```
     1
   / | \
  2  3  4
      \
       5
```
(Not strictly binary if more than two children, but as a binary tree example: 1 with left=2 and right=3, and 3 with right=5 and assume 2 and 5 might have some left children etc.) The idea is to test that among multiple nodes at a level, you select the correct one. In a proper binary tree example:
```
    10
   /   \
  6     15
 / \   /  \
4   8 12  20
        \
        14
```
The right view would be [10, 15, 20, 14]. Each level’s rightmost node is chosen (10 from level0, 15 from level1, 20 from level2, and 14 from level3).
Our implementations inherently handle these scenarios because they rely on the structure of levels and depths rather than specific configurations. It’s good practice to mentally run through a couple of these edge cases or actually test them to be confident.

This problem is about one particular "view" of a binary tree (the right side). There are similar concepts and variations:

Left Side View of a Binary Tree: This is symmetrical to the right side view. Instead of the rightmost nodes, you'd collect the leftmost node of each level (what you see from the left side of the tree). The approach is almost identical, except you would traverse the left child before the right child in DFS, or in BFS take the first node of each level instead of the last. This is a good variation to try after solving the right side view.
Top View and Bottom View of a Binary Tree: These are more advanced variations. The top view is what you’d see looking down from above the tree (you’d see the highest node at each horizontal distance). The bottom view is looking from below (you see the lowest node at each horizontal distance). Solving these requires tracking horizontal position and using a different traversal strategy (often a BFS with column indices). They’re commonly asked in interviews as well, but require different handling than a simple level order.
Boundary Traversal of a Binary Tree: This involves printing the boundary of the tree (which includes the left boundary, leaves, and right boundary). It’s another way to list "visible" nodes from the outside, but it combines multiple sides.
Populating Next Right Pointers in Each Node: (LeetCode 116 and 117) In these problems, instead of printing the right view, you connect each node to its immediate right neighbor at the same level. This uses a similar BFS level traversal concept. It’s related in the sense of handling nodes level by level and dealing with the notion of "right neighbor". If you found BFS straightforward here, those problems are a good follow-up to practice using BFS in trees.
Zigzag Level Order Traversal: (LeetCode 103) This is another variation of level order traversal where you alternate the direction of traversal at each level (left-to-right, then right-to-left). While not directly a "view" problem, it’s a related traversal problem that can be tackled with BFS (and sometimes with a deque for efficient appends on either end).