Binary Tree Right Side View

Medium Problem 71 of 151 Java and Python

Problem

Given the root of a binary tree, imagine standing on its right side. Return the values of the nodes you can see, ordered from top to bottom.

Example 1

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

Example 2

Input: root = [1, 2, 3, 4]
Output: [1, 3, 4]
Why: 4 is on the left, but nothing on level 3 is to its right, so it is visible.

Constraints

0 ≤ number of nodes ≤ 100

Explanation

From the right you see exactly one node per level: the rightmost one, which is not always a right child.

Either do a level-order traversal and keep each level's last node, or DFS visiting right before left and record the first node you reach at each new depth.

Approach 1 · Better

BFS, keep the last of each level

Time O(n)
Space O(w)

Process the tree level by level; the last node popped in each level is visible.

Run level-order BFS.
For each level, append the value of its last node.

Java

import java.util.*;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    result.add(node.val);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return result;
    }
}

Python

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        queue = deque([root] if root else [])
        while queue:
            for i in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(node.val)
        return result

Approach 2 · Optimal

DFS, right child first

Time O(n)
Space O(h)

Visit right before left. The first node you reach at each depth is the rightmost one on that level.

dfs(node, depth): if depth == result.size(), append node.val.
Recurse into right, then left, with depth + 1.

Java

import java.util.*;

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 (depth == result.size()) {
            result.add(node.val);
        }
        dfs(node.right, depth + 1, result);
        dfs(node.left, depth + 1, result);
    }
}

Python

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

        def dfs(node, depth):
            if not node:
                return
            if depth == len(result):
                result.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result

Complexity compared

Approach	Time	Space
Better BFS, keep the last of each level	O(n)	O(w)
Optimal DFS, right child first	O(n)	O(h)

Key takeaways

Swap the order (left first) and the same DFS gives the left side view.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem