Binary Tree Right Side View

mediumTrees: Traversal48 stepsJava · Python · C++

Standing on the right, you see the last node of each level. Do a level-order traversal and record the value of the last node popped in every level.

▶ Watch the animated trace

Traced input: root = [1, 2, 3, null, 5, null, 4] → [1, 3, 4]. Original problem: neetcode.io/problems/binary-tree-right-side-view

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(w)

Every node is visited once.

Key idea

The rightmost node of a level is the last one popped in that round.
Left children still matter: a left node is visible if the right side is shorter.
A DFS visiting right first and recording the first node at each depth also works.

Common mistakes

Only following right children misses deeper left nodes.
Recording the first node of each level instead of the last.

Solution

Java

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

Python

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    res = []
    if not root: return res
    queue = deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == size - 1: res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
    return res

C++

vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            if (i == size - 1) res.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Left side visible 4 is a left descendant but the last node on its level.	`root = [1, 2, 3, 4]`	`[1, 3, 4]`
Empty tree Nothing to see.	`root = []`	`[]`
Only left children Each level has a single node.	`root = [1, 2, null, 3]`	`[1, 2, 3]`