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.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
Hint 1
You see exactly one node per level.
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.
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
- If the tree is empty, return an empty list.
- Put the root in a queue.
- While the queue is not empty, take the
sizenodes of the current level, enqueuing each one's left then right child; append the value of the last of them. - 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 outJava
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)