Binary Tree Right Side View

Medium
1913.

Binary Tree Right Side View

Binary Tree Right Side View is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Meta and Bloomberg interviews.

Imagine standing to the right of a binary tree and looking at it. On every level you see only the node furthest to the right.

Given the root of the tree, return the values you can see, from the top level down. Return an empty list for an empty tree.

Example 1

Input
root = [1,2,3,null,5,null,4]
Output
[1,3,4]
Explanation
Standing on the right you see 1, then 3, then 4 — the last node of each level.

Example 2

Input
root = [1,2,3,4]
Output
[1,3,4]
Explanation
The deepest level holds only 4, a left descendant, yet nothing to its right hides it.

Example 3

Input
root = []
Output
[]
Explanation
An empty tree shows nothing.

Constraints

  • 0 <= number of nodes <= 100
  • -100 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Right Side View — Solution in Python, Java & C++

Binary Tree Right Side View solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Binary Tree Right Side View is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Meta and Bloomberg interviews.

Problem statement

Imagine standing to the right of a binary tree and looking at it. On every level you see only the node furthest to the right.

Given the root of the tree, return the values you can see, from the top level down. Return an empty list for an empty tree.

Example 1

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: Standing on the right you see 1, then 3, then 4 — the last node of each level.

Example 2

Input: root = [1,2,3,4]
Output: [1,3,4]
Explanation: The deepest level holds only 4, a left descendant, yet nothing to its right hides it.

Example 3

Input: root = []
Output: []
Explanation: An empty tree shows nothing.

Constraints

  • 0 <= number of nodes <= 100
  • -100 <= Node.val <= 100

Hints for Binary Tree Right Side View

  1. Hint 1

    You see exactly one node per level.

  2. Hint 2

    The visible node is the last one of its level when the level is read from left to right — it need not be a right child.

  3. Hint 3

    Do a level-order traversal and record the last node taken from each level.

How to solve Binary Tree Right Side View

Traverse level by level; the last node of each level is the one visible from the right.

Approach

  1. If the tree is empty, return an empty list.
  2. Put the root in a queue.
  3. While the queue is not empty, take the size nodes of the current level, enqueuing each one's left then right child; append the value of the last of them.
  4. Return the collected values.

Why it works

With children enqueued left before right, each round of the queue holds one complete level in left-to-right order, so its last node is the rightmost node of that level — the only one not hidden by a node further right.

Complexity

  • Time — O(n)
  • Space — O(w), w the largest number of nodes on one level

Pitfalls

  • Following only right children misses levels where the rightmost node hangs off a left branch, as in [1,2,3,4].

Reference solution

Python

from typing import List, Optional

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    out = []
    level = [root] if root else []
    while level:
        out.append(level[-1].val)
        nxt = []
        for node in level:
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
    return out

Java

public static int[] rightSideView(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    while (!queue.isEmpty()) {
        out.add(queue.peekLast().val);
        for (int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

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

JavaScript

var rightSideView = function(root) {
    var out = [];
    if (root === null) return out;
    var queue = [root], head = 0;
    while (head < queue.length) {
        var end = queue.length;
        out.push(queue[end - 1].val);
        while (head < end) {
            var node = queue[head++];
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)