Binary Tree Right Side View

Medium · Trees · Explanation and code example

Breadth First Search

How it works

In BFS we explore the tree level by level.
If we look at each level from left to right, the last node we encounter at that level is the one visible from the right side.

So for every level:

  • Traverse all nodes.
  • Remember the rightmost node.
  • Add it to the answer.

Steps

  1. If the tree is empty → return an empty list.
  2. Initialize a queue with the root.
  3. While the queue is not empty:
    • Determine how many nodes are in the current level (level_size).
    • For each node in the level:
      • Pop it from the queue.
      • Update rightmost_node to this node.
      • Push its left child, then right child (if they exist).
    • After finishing the level, append rightmost_node's value to the result.
  4. Return the result list.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Only Traversing Right Children

The rightmost visible node at each level is not always in the right subtree. When the right subtree is shorter than the left, deeper left nodes become visible from the right.

Using DFS With Left-First Traversal Without Adjustment

In DFS, if you visit left children before right children, you must update (not just set) the result for each depth. Otherwise, only left-side nodes are captured.

Forgetting to Track Level Size in BFS

In BFS, you must process all nodes at the current level before moving to the next. Without tracking the level size, you cannot determine which node is rightmost at each level.

Python code example

from typing import List, Optional
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

        while q:
            rightSide = None
            qLen = len(q)

            for i in range(qLen):
                node = q.popleft()
                if node:
                    rightSide = node
                    q.append(node.left)
                    q.append(node.right)
            if rightSide:
                res.append(rightSide.val)
        return res

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* rightSide = nullptr;
            int qLen = q.size();

            for (int i = 0; i < qLen; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node) {
                    rightSide = node;
                    q.push(node->left);
                    q.push(node->right);
                }
            }
            if (rightSide) {
                res.push_back(rightSide->val);
            }
        }
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations