Binary Tree Right Side View

Problem Statement

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.

What to notice first

• You see only the rightmost node at each level.
• If a right child exists, you see it; otherwise you see the leftmost node that extends to that level.
• Both BFS and DFS work, but they visit levels differently.

Examples

Input	Output	Explanation
[1,2,3,null,5,null,4]	[1,3,4]	Right view: root 1, right child 3, right-most at level 3 is 4
[1,null,3]	[1,3]	Only right children visible
[]	[]	Empty tree

Visualized Examples

Example 1:       1              Output: [1, 3, 4]
                / \
               2   3            Right side view
                \   \
                 5   4

Example 2:       1
                  \
                   3            Output: [1, 3]

Example 3:    (empty)           Output: []

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Real-World Applications

Where this pattern appears

• 3D rendering — determine visible surfaces from a viewing angle.
• Organizational charts — view reporting lines from the side.
• Route planning — see landmarks from a specific viewpoint.
• Game graphics — render visible objects in a scene.
• Photography — identify prominent features in composition.

Complexity Comparison

Approach	Time	Space	Best When
BFS Level-Order	O(n)	O(w)	Want to process level-by-level clearly
DFS Right-First	O(n)	O(h)	Prefer simpler recursion; smaller trees

Where h = height, w = max width

Which approach should you learn first?

• Pick BFS Level-Order if you want a clear, intuitive level-by-level approach.
• Pick DFS Right-First if you prefer elegant recursion that processes the right side first.

Level-by-Level

BFS Level-Order

O(n) time · O(w) space

Right-First

DFS Right-First

O(n) time · O(h) space

Approach 1: BFS Level-Order (Recommended)

★ Recommended

Process the tree level by level. For each level, take the rightmost node (the last one dequeued in that level).

⏱ Time O(n) Visit all nodes once 💾 Space O(w) Queue width at widest level

Step-by-step Example

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

Level 1: [1]         → right-most = 1
Level 2: [2, 3]      → right-most = 3
Level 3: [5, 4]      → right-most = 4
Result: [1, 3, 4]

Pseudocode

function rightSideViewBFS(root):
    if root is null:
        return []

    result = []
    queue = [root]

    while queue is not empty:
        levelSize = length of queue

        // Process all nodes at this level
        for i = 0 to levelSize - 1:
            node = queue.dequeue()

            // Store the rightmost (last) node at this level
            if i == levelSize - 1:
                result.append(node.val)

            if node.left exists:
                queue.enqueue(node.left)
            if node.right exists:
                queue.enqueue(node.right)

    return result

Solution Code

Python

binary_tree_right_side_view_bfs.py

from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def rightSideView(root: Optional[TreeNode]) -> List[int]:
    """
    Return the right side view of a binary tree using BFS.

    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(w) where w is the maximum width
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.popleft()

            # Record the rightmost (last) node at this level
            if i == level_size - 1:
                result.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result


# Test cases
if __name__ == "__main__":
    # Example 1: [1,2,3,null,5,null,4]
    #       1
    #      / \
    #     2   3
    #      \   \
    #       5   4
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(3)
    root1.left.right = TreeNode(5)
    root1.right.right = TreeNode(4)

    result1 = rightSideView(root1)
    print(f"Right side view of tree 1: {result1}")  # Expected: [1, 3, 4]

    # Example 2: [1,null,3]
    #     1
    #      \
    #       3
    root2 = TreeNode(1)
    root2.right = TreeNode(3)

    result2 = rightSideView(root2)
    print(f"Right side view of tree 2: {result2}")  # Expected: [1, 3]

    # Example 3: Empty tree
    root3 = None
    result3 = rightSideView(root3)
    print(f"Right side view of tree 3: {result3}")  # Expected: []

C++

binary_tree_right_side_view_bfs.cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if (!root) return result;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();

                if (i == levelSize - 1) {
                    result.push_back(node->val);
                }

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }

        return result;
    }
};

int main() {
    Solution sol;

    TreeNode* root1 = new TreeNode(1);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(3);
    root1->left->right = new TreeNode(5);
    root1->right->right = new TreeNode(4);

    vector<int> result1 = sol.rightSideView(root1);
    cout << "Right side view: ";
    for (int val : result1) cout << val << " ";
    cout << endl;  // Expected: 1 3 4

    return 0;
}

Java

binary_tree_right_side_view_bfs.java

import java.util.*;

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                if (i == levelSize - 1) {
                    result.add(node.val);
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return result;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.right = new TreeNode(5);
        root1.right.right = new TreeNode(4);

        List<Integer> result1 = sol.rightSideView(root1);
        System.out.println("Right side view: " + result1);
    }
}

JavaScript

binary_tree_right_side_view_bfs.js

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rightSideView(root) {
    const result = [];
    if (!root) return result;

    const queue = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();

            if (i === levelSize - 1) {
                result.push(node.val);
            }

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    return result;
}

if (require.main === module) {
    const root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(3);
    root1.left.right = new TreeNode(5);
    root1.right.right = new TreeNode(4);

    const result1 = rightSideView(root1);
    console.log("Right side view:", result1);  // Expected: [1, 3, 4]
}

module.exports = rightSideView;

Rust

binary_tree_right_side_view_bfs.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

#[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,
        }
    }
}

pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    if root.is_none() {
        return result;
    }

    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());

    while !queue.is_empty() {
        let level_size = queue.len();

        for i in 0..level_size {
            let node = queue.pop_front().unwrap();
            let node_ref = node.borrow_mut();

            if i == level_size - 1 {
                result.push(node_ref.val);
            }

            if let Some(left) = node_ref.left.clone() {
                queue.push_back(left);
            }
            if let Some(right) = node_ref.right.clone() {
                queue.push_back(right);
            }
        }
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_example_1() {
        let root = Rc::new(RefCell::new(TreeNode::new(1)));
        let left = Rc::new(RefCell::new(TreeNode::new(2)));
        let right = Rc::new(RefCell::new(TreeNode::new(3)));
        let left_right = Rc::new(RefCell::new(TreeNode::new(5)));
        let right_right = Rc::new(RefCell::new(TreeNode::new(4)));

        left.borrow_mut().right = Some(left_right);
        right.borrow_mut().right = Some(right_right);
        root.borrow_mut().left = Some(left);
        root.borrow_mut().right = Some(right);

        let result = right_side_view(Some(root));
        assert_eq!(result, vec![1, 3, 4]);
    }
}

Go

binary_tree_right_side_view_bfs.go

package main

import "fmt"

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func RightSideView(root *TreeNode) []int {
  result := []int{}
  if root == nil {
    return result
  }

  queue := []*TreeNode{root}

  for len(queue) > 0 {
    levelSize := len(queue)

    for i := 0; i < levelSize; i++ {
      node := queue[0]
      queue = queue[1:]

      if i == levelSize-1 {
        result = append(result, node.Val)
      }

      if node.Left != nil {
        queue = append(queue, node.Left)
      }
      if node.Right != nil {
        queue = append(queue, node.Right)
      }
    }
  }

  return result
}

func main() {
  root1 := &TreeNode{Val: 1}
  root1.Left = &TreeNode{Val: 2}
  root1.Right = &TreeNode{Val: 3}
  root1.Left.Right = &TreeNode{Val: 5}
  root1.Right.Right = &TreeNode{Val: 4}

  result1 := RightSideView(root1)
  fmt.Println("Right side view:", result1)
}

Approach 2: DFS Right-First Traversal

🎯 Interview Favourite

Use DFS and visit the right child before the left child. Track the current level. Record a node only the first time we visit its level (which is the rightmost at that level).

⏱ Time O(n) Visit all nodes 💾 Space O(h) Recursion call stack

Step-by-step Example

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

DFS order (right-first): 1 (level 0) → 3 (level 1) → 4 (level 2) → 2 (level 1, skip) → 5 (level 2, skip)

Result: [1, 3, 4]

Pseudocode

function rightSideViewDFS(root):
    result = []

    function dfs(node, level):
        if node is null:
            return

        // First time reaching this level, it's the rightmost
        if level == length of result:
            result.append(node.val)

        // Right child first, then left
        dfs(node.right, level + 1)
        dfs(node.left, level + 1)

    dfs(root, 0)
    return result

Solution Code

Python

binary_tree_right_side_view_dfs.py

from typing import Optional, List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def rightSideView(root: Optional[TreeNode]) -> List[int]:
    """
    Return the right side view of a binary tree using DFS (right-first).

    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(h) where h is the height (call stack depth)
    """
    result = []

    def dfs(node: Optional[TreeNode], level: int) -> None:
        if not node:
            return

        # First time visiting this level, it's the rightmost
        if level == len(result):
            result.append(node.val)

        # Visit right subtree first, then left
        dfs(node.right, level + 1)
        dfs(node.left, level + 1)

    dfs(root, 0)
    return result


# Test cases
if __name__ == "__main__":
    # Example 1: [1,2,3,null,5,null,4]
    #       1
    #      / \
    #     2   3
    #      \   \
    #       5   4
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(3)
    root1.left.right = TreeNode(5)
    root1.right.right = TreeNode(4)

    result1 = rightSideView(root1)
    print(f"Right side view of tree 1: {result1}")  # Expected: [1, 3, 4]

    # Example 2: [1,null,3]
    #     1
    #      \
    #       3
    root2 = TreeNode(1)
    root2.right = TreeNode(3)

    result2 = rightSideView(root2)
    print(f"Right side view of tree 2: {result2}")  # Expected: [1, 3]

    # Example 3: Empty tree
    root3 = None
    result3 = rightSideView(root3)
    print(f"Right side view of tree 3: {result3}")  # Expected: []

C++

binary_tree_right_side_view_dfs.cpp

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    void dfs(TreeNode* node, int level, vector<int>& result) {
        if (!node) return;

        if (level == result.size()) {
            result.push_back(node->val);
        }

        dfs(node->right, level + 1, result);
        dfs(node->left, level + 1, result);
    }

public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        dfs(root, 0, result);
        return result;
    }
};

int main() {
    Solution sol;

    TreeNode* root1 = new TreeNode(1);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(3);
    root1->left->right = new TreeNode(5);
    root1->right->right = new TreeNode(4);

    vector<int> result1 = sol.rightSideView(root1);
    cout << "Right side view: ";
    for (int val : result1) cout << val << " ";
    cout << endl;  // Expected: 1 3 4

    return 0;
}

Java

binary_tree_right_side_view_dfs.java

import java.util.*;

public class Solution {
    private void dfs(TreeNode node, int level, List<Integer> result) {
        if (node == null) return;

        if (level == result.size()) {
            result.add(node.val);
        }

        dfs(node.right, level + 1, result);
        dfs(node.left, level + 1, result);
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.right = new TreeNode(5);
        root1.right.right = new TreeNode(4);

        List<Integer> result1 = sol.rightSideView(root1);
        System.out.println("Right side view: " + result1);
    }
}

JavaScript

binary_tree_right_side_view_dfs.js

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rightSideView(root) {
    const result = [];

    function dfs(node, level) {
        if (!node) return;

        if (level === result.length) {
            result.push(node.val);
        }

        dfs(node.right, level + 1);
        dfs(node.left, level + 1);
    }

    dfs(root, 0);
    return result;
}

if (require.main === module) {
    const root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(3);
    root1.left.right = new TreeNode(5);
    root1.right.right = new TreeNode(4);

    const result1 = rightSideView(root1);
    console.log("Right side view:", result1);  // Expected: [1, 3, 4]
}

module.exports = rightSideView;

Rust

binary_tree_right_side_view_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[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,
        }
    }
}

pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut result = Vec::new();

    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, level: usize, result: &mut Vec<i32>) {
        if let Some(n) = node {
            let n_ref = n.borrow();

            if level == result.len() {
                result.push(n_ref.val);
            }

            dfs(&n_ref.right, level + 1, result);
            dfs(&n_ref.left, level + 1, result);
        }
    }

    dfs(&root, 0, &mut result);
    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_example_1() {
        let root = Rc::new(RefCell::new(TreeNode::new(1)));
        let left = Rc::new(RefCell::new(TreeNode::new(2)));
        let right = Rc::new(RefCell::new(TreeNode::new(3)));
        let left_right = Rc::new(RefCell::new(TreeNode::new(5)));
        let right_right = Rc::new(RefCell::new(TreeNode::new(4)));

        left.borrow_mut().right = Some(left_right);
        right.borrow_mut().right = Some(right_right);
        root.borrow_mut().left = Some(left);
        root.borrow_mut().right = Some(right);

        let result = right_side_view(Some(root));
        assert_eq!(result, vec![1, 3, 4]);
    }
}

Go

binary_tree_right_side_view_dfs.go

package main

import "fmt"

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func RightSideView(root *TreeNode) []int {
  result := []int{}

  var dfs func(*TreeNode, int)
  dfs = func(node *TreeNode, level int) {
    if node == nil {
      return
    }

    if level == len(result) {
      result = append(result, node.Val)
    }

    dfs(node.Right, level+1)
    dfs(node.Left, level+1)
  }

  dfs(root, 0)
  return result
}

func main() {
  root1 := &TreeNode{Val: 1}
  root1.Left = &TreeNode{Val: 2}
  root1.Right = &TreeNode{Val: 3}
  root1.Left.Right = &TreeNode{Val: 5}
  root1.Right.Right = &TreeNode{Val: 4}

  result1 := RightSideView(root1)
  fmt.Println("Right side view:", result1)
}

Related Problems

• Binary Tree Level Order Traversal ↗ Medium #102
• Binary Tree Zigzag Level Order Traversal ↗ Medium #103
• Maximum Depth of Binary Tree ↗ Easy #104
• Average of Levels in Binary Tree ↗ Easy #637

Interview Tips

Key trade-offs to discuss

• BFS vs DFS: BFS is more intuitive for level processing; DFS is elegant but requires careful right-first ordering.
• Space usage: BFS uses queue space (width-dependent); DFS uses call stack (height-dependent).
• Follow-ups to expect: left side view, top view, bottom view, or per-level aggregations.

← Previous
#198 House Robber Next
#200 Number of Islands →