Binary Tree Right Side View solution and explanation
Google
9 more videos on this problem
Binary Tree Right Side View - Breadth First Search - Leetcode 199NeetCode · 10:16 · 153K views
Binary Tree Right Side View - LeetCode 199 PythonDeepti Talesra · 8:22 · 7K views
Binary Tree Right Side View (LeetCode 199) | Both Views with the thought processNikhil Lohia · 11:07 · 4K views
BINARY TREE RIGHT SIDE VIEW | PYTHON SOLUTION | LEETCODE # 199Cracking FAANG · 5:37 · 3K views
Solving LeetCode 199 in JavaScript (Binary Tree Right Side View)KA Education · 5:41 · 1K views
Binary Tree Right Side View - LeetCode 199 - JavaScriptAlgoJS · 4:54 · 835 views
Binary Tree Right Side View - 199. LeetCode - JavaTeddy Smith · 10:25 · 418 views
LeetCode #199 (Binary Tree Right Side View) using Python | NeetCode 150CodeMeetsWorld · 9:43 · 155 views
Binary Tree Right Side View - LeetCode 199 - Breadth First Search (BFS)Jamie Dawson · 11:50 · 130 views
Binary Tree Right Side View | BFS 🔥| LeetCode Solution 199Gantavya Malviya · 10:29 · 81 views
The problem
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.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:
Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:
Example 3:
Input: root = [1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach overview
Problem Overview: Given the root of a binary tree, return the list of node values visible when the tree is viewed from the right side. At each depth level, only the rightmost node should appear in the result.
Approach 1: Breadth-First Search (BFS) using Queue (O(n) time, O(n) space)
This approach performs a level-order traversal using a queue. Process the tree level by level and track how many nodes exist at the current depth. As you iterate through nodes in the same level, the last node processed represents the rightmost node visible from that level. Add this node's value to the result list. Each node is enqueued once and dequeued once, which gives O(n) time complexity, while the queue can hold up to one full level of nodes, leading to O(n) space in the worst case.
BFS works well because the problem is naturally defined by levels of a tree. You simply detect the final node encountered in each level iteration. This method is straightforward and easy to implement during interviews, especially when you are already using a queue for level traversal of a binary tree. The algorithm scales cleanly for skewed and balanced trees alike.
Approach 2: Depth-First Search (DFS) Right-First Traversal (O(n) time, O(h) space)
The DFS approach explores the tree recursively while prioritizing the right subtree before the left subtree. Maintain the current depth during recursion and track the maximum depth already recorded in the result list. Whenever you visit a node at a depth equal to the current result size, it means this is the first node encountered at that level from the right side, so you append its value.
This works because visiting the right child first guarantees the first node seen at each depth is the visible one. The recursion stack stores at most the height of the tree, resulting in O(h) space where h is the tree height. In the worst case of a skewed tree, that becomes O(n). DFS is common when working with recursive traversal patterns in depth-first search problems.
Compared to BFS, this method avoids explicitly storing full levels in a queue and instead relies on recursion depth tracking. It integrates naturally with many tree-recursion templates used in tree problems.
Recommended for interviews: Both BFS and DFS run in O(n) time and are accepted solutions. Interviewers often expect the BFS level-order solution first because it directly models "one node per level" visibility. Demonstrating the DFS right-first approach afterward shows deeper understanding of traversal order and recursion patterns.
Approach 1: Breadth-First Search (BFS) using Queue
The Breadth-First Search (BFS) approach involves traversing the tree level by level using a queue. For each level, we capture the last node's value visible when viewed from the right side. This can be done by iterating through each level and storing the value of the last node encountered. This approach ensures that the elements are captured in top-to-bottom order as required.
from collections import deque
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: TreeNode):
if not root:
return []
queue = deque([root])
view = []
while queue:
level_length = len(queue)
last_node = None
for _ in range(level_length):
node = queue.popleft()
last_node = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
view.append(last_node)
return viewimport java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
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;
}
}
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> view = new ArrayList<>();
if (root == null) return view;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
Integer lastNode = null;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
lastNode = node.val;
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
view.add(lastNode);
}
return view;
}
}The solution uses a queue to perform BFS. We initialize the queue with the root node, and for each level, we iterate over each node, updating the last node value for that level. At the end of each level iteration, the last node value is added to the result. This gives us the right view of the tree. The space complexity is determined by the maximum width of the tree, and the time complexity is O(n) where n is the number of nodes.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree (at the level with the most nodes).
Approach 2: Depth-First Search (DFS)
In this approach, a recursive Depth-First Search (DFS) is utilized. It traverses the tree from the root and prioritizes the right child before the left child at each node. By keeping track of the current level, we ensure to capture only the first node visited at that level, which represents the right view at that height.
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> view;
dfs(root, 0, view);
return view;
}
void dfs(TreeNode* node, int level, vector<int>& view) {
if (!node) return;
if (level == view.size()) view.push_back(node->val);
dfs(node->right, level + 1, view);
dfs(node->left, level + 1, view);
}
};using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public IList<int> RightSideView(TreeNode root) {
var view = new List<int>();
DFS(root, 0, view);
return view;
}
private void DFS(TreeNode node, int level, List<int> view) {
if (node == null) return;
if (level == view.Count) {
view.Add(node.val);
}
DFS(node.right, level + 1, view);
DFS(node.left, level + 1, view);
}
}This solution uses DFS, visiting each node starting from the rightmost node. For each node, if it's the first node visited at that level, it gets added to the result, giving the rightmost view.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(h), where h is the height of the tree, considering the space used for recursion stack.
Approach 3: BFS
We can use breadth-first search (BFS) and define a queue q to store the nodes. We start by putting the root node into the queue. Each time, we take out all the nodes of the current level from the queue. For the current node, we first check if the right subtree exists; if it does, we put the right subtree into the queue. Then, we check if the left subtree exists; if it does, we put the left subtree into the queue. This way, the first node taken out from the queue each time is the rightmost node of that level.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* 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) {
const ans = [];
if (!root) {
return ans;
}
const q = [root];
while (q.length > 0) {
ans.push(q[0].val);
const nq = [];
for (const { left, right } of q) {
if (right) {
nq.push(right);
}
if (left) {
nq.push(left);
}
}
q.length = 0;
q.push(...nq);
}
return ans;
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function rightSideView(root: TreeNode | null): number[] {
const ans: number[] = [];
if (!root) {
return ans;
}
const q: TreeNode[] = [root];
while (q.length > 0) {
ans.push(q[0].val);
const nq: TreeNode[] = [];
for (const { left, right } of q) {
if (right) {
nq.push(right);
}
if (left) {
nq.push(left);
}
}
q.length = 0;
q.push(...nq);
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) (ans []int) {
if root == nil {
return
}
q := []*TreeNode{root}
for len(q) > 0 {
ans = append(ans, q[0].Val)
for k := len(q); k > 0; k-- {
node := q[0]
q = q[1:]
if node.Right != nil {
q = append(q, node.Right)
}
if node.Left != nil {
q = append(q, node.Left)
}
}
}
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut ans = vec![];
if root.is_none() {
return ans;
}
let mut q = VecDeque::new();
q.push_back(root);
while !q.is_empty() {
let k = q.len();
ans.push(q[0].as_ref().unwrap().borrow().val);
for _ in 0..k {
if let Some(node) = q.pop_front().unwrap() {
let mut node = node.borrow_mut();
if node.right.is_some() {
q.push_back(node.right.take());
}
if node.left.is_some() {
q.push_back(node.left.take());
}
}
}
}
ans
}
}Approach 4: DFS
Use DFS (depth-first search) to traverse the binary tree. Each time, traverse the right subtree first, then the left subtree. This way, the first node visited at each level is the rightmost node of that level.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* 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) {
const ans = [];
const dfs = (root, depth) => {
if (!root) {
return;
}
if (ans.length == depth) {
ans.push(root.val);
}
dfs(root.right, depth + 1);
dfs(root.left, depth + 1);
};
dfs(root, 0);
return ans;
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function rightSideView(root: TreeNode | null): number[] {
const ans = [];
const dfs = (root: TreeNode | null, depth: number) => {
if (!root) {
return;
}
if (ans.length == depth) {
ans.push(root.val);
}
dfs(root.right, depth + 1);
dfs(root.left, depth + 1);
};
dfs(root, 0);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) (ans []int) {
var dfs func(*TreeNode, int)
dfs = func(root *TreeNode, depth int) {
if root == nil {
return
}
if len(ans) == depth {
ans = append(ans, root.Val)
}
dfs(root.Right, depth+1)
dfs(root.Left, depth+1)
}
dfs(root, 0)
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut ans = Vec::new();
fn dfs(node: Option<Rc<RefCell<TreeNode>>>, depth: usize, ans: &mut Vec<i32>) {
if let Some(node_ref) = node {
let node = node_ref.borrow();
if ans.len() == depth {
ans.push(node.val);
}
dfs(node.right.clone(), depth + 1, ans);
dfs(node.left.clone(), depth + 1, ans);
}
}
dfs(root, 0, &mut ans);
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) using Queue | Time Complexity: O(n), where n is the number of nodes in the tree. |
| Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes in the tree. |
| BFS | – |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (Queue Level Order) | O(n) | O(n) | Best when reasoning level-by-level in a binary tree and identifying the last node in each level |
| Depth-First Search (Right-First Traversal) | O(n) | O(h) | Useful when using recursive tree traversal templates and tracking depth |
Frequently asked questions
Is Binary Tree Right Side View easy or hard?
Binary Tree Right Side View is considered a Medium difficulty problem. The logic is straightforward once you recognize the level-order or right-first traversal pattern, but it requires understanding of tree traversal and careful handling of levels or recursion depth.
How to solve Binary Tree Right Side View in O(n)?
Traverse the tree once using either BFS or DFS. In BFS, iterate through each level using a queue and record the last node encountered in that level. In DFS, traverse the right subtree before the left and record the first node seen at each depth. Both approaches ensure each node is processed once, giving O(n) time complexity.
Binary Tree Right Side View Python or Java solution
Python and Java solutions typically use a queue for BFS or recursion for DFS. The BFS implementation iterates through each level and stores the last node value in the result list. The DFS implementation traverses right before left and records the first node encountered at each depth.
What is the best approach for Binary Tree Right Side View?
Both BFS level-order traversal and DFS right-first traversal solve the problem efficiently in O(n) time. BFS is often considered the most intuitive because you process nodes level by level and record the last node in each level. DFS is equally optimal and records the first node encountered at each depth when traversing right before left.
What data structure is used in Binary Tree Right Side View?
The main data structures used are queues and recursion stacks. BFS uses a queue to process nodes level by level, while DFS relies on the recursion call stack to track traversal depth. Both approaches operate on a binary tree structure.
What is the time complexity of Binary Tree Right Side View?
The optimal time complexity is O(n) because every node in the binary tree is visited exactly once. BFS processes nodes level by level using a queue, while DFS visits each node recursively. Space complexity is O(n) for BFS and O(h) for DFS where h is the tree height.
Is Binary Tree Right Side View asked at Google, Amazon, or Meta?
Binary Tree Right Side View is a common tree traversal interview problem and has appeared in interview prep lists associated with companies like Amazon, Google, and Meta. It tests understanding of BFS level traversal, DFS recursion, and tree visibility logic.