Tech Blogs LLD SDE Playbook DSA

Binary Tree Right Side View

Medium Top 250
Associated Patterns
Trees
Interviewed At (Company Tags)
GoogleAmazonMicrosoftMeta
External Reference View on LeetCode

Problem 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.

Examples

Example 1:

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

Example 2:

Input: root = [1,null,3] Output: [1,3]

Example 3:

Input: root = [] Output: []

Constraints

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

Layer-by-Layer Rightmost Elements

We can find the right side view:

  1. Level-Order Traversal (BFS): Traverse the tree level by level using a queue. For each level, the last node we process in the level is the rightmost node visible from that level. We append its value to our result list.
  2. Reverse Preorder DFS (Root-Right-Left): Walk the tree depth-first, visiting the right child before the left child. We pass the current depth along. If depth == result.size(), it means this is the first node we have visited at this depth level, which is guaranteed to be the rightmost element. We record it and recurse.

Solution 1: Level-Order BFS Traversal

Traverse tree levels using a queue, recording the final element of each level.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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 curr = queue.poll();
                
                // If it is the last element of the current level, record it
                if (i == levelSize - 1) {
                    result.add(curr.val);
                }

                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
        }
        return result;
    }
}
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]:
        result = []
        if not root:
            return result
            
        queue = deque([root])
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                curr = queue.popleft()
                
                # Last element of this level is the rightmost element
                if i == level_size - 1:
                    result.append(curr.val)
                    
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
                    
        return result
#include <vector>
#include <queue>

/**
 * 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:
    std::vector<int> rightSideView(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;

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

        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode* curr = q.front();
                q.pop();

                if (i == levelSize - 1) {
                    result.push_back(curr->val);
                }

                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
        }
        return result;
    }
};

Complexity Analysis

  • Time Complexity: O(n) since we visit every node in the binary tree exactly once.
  • Space Complexity: O(w) auxiliary space to store elements in the queue, where w is the maximum width of the tree.

Solution 2: Reverse Preorder DFS

Perform Depth-First Search prioritising the right child to collect the rightmost node at each depth level.

import java.util.ArrayList;
import java.util.List;

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 this is the first time we visit this depth level, record the node value
        if (depth == result.size()) {
            result.add(node.val);
        }

        // Visit right child first
        dfs(node.right, depth + 1, result);
        dfs(node.left, depth + 1, result);
    }
}
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> list[int]:
        result = []
        
        def dfs(node: Optional[TreeNode], depth: int):
            if not node:
                return
            
            if depth == len(result):
                result.append(node.val)
                
            # Visit right child first
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result
#include <vector>

class Solution {
private:
    void dfs(TreeNode* node, int depth, std::vector<int>& result) {
        if (!node) return;

        if (depth == result.size()) {
            result.push_back(node->val);
        }

        dfs(node->right, depth + 1, result);
        dfs(node->left, depth + 1, result);
    }

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

Complexity Analysis

  • Time Complexity: O(n) since we visit every node once.
  • Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.

← All Problems