199. Binary Tree Right Side View (Medium)

Problem

Given the root of a binary tree, imagine standing on the right side of it. Return the values of the nodes you can see, ordered from top to bottom, one value per depth, the rightmost at that depth.

Example

root = [1,2,3,null,5,null,4] → [1, 3, 4]
root = [1,null,3] → [1, 3]
root = [] → []

LeetCode 199 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: BFS, take the last node of each level

Standard level-order traversal; append the last value processed per level.

from collections import deque

def right_side_view(root):
    if not root:
        return []
    result = []
    q = deque([root])              # L1: O(1) init
    while q:
        level_size = len(q)        # L2: snapshot current level size
        for i in range(level_size):
            node = q.popleft()     # L3: O(1) dequeue
            if i == level_size - 1:
                result.append(node.val)  # L4: O(1) record last in level
            if node.left:
                q.append(node.left)      # L5: O(1) enqueue
            if node.right:
                q.append(node.right)     # L6: O(1) enqueue
    return result

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function rightSideView(root: TreeNode | null): number[] {
    if (!root) return [];
    const result: number[] = [];
    const q: TreeNode[] = [root];              // L1: O(1) init
    while (q.length) {
        const levelSize = q.length;            // L2: snapshot current level size
        for (let i = 0; i < levelSize; i++) {
            const node = q.shift()!;           // L3: O(1) dequeue
            if (i === levelSize - 1) result.push(node.val);  // L4: O(1) record last in level
            if (node.left) q.push(node.left);  // L5: O(1) enqueue
            if (node.right) q.push(node.right);// L6: O(1) enqueue
        }
    }
    return result;
}

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

func rightSideView(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    result := []int{}
    q := []*TreeNode{root}              // L1: O(1) init
    for len(q) > 0 {
        levelSize := len(q)             // L2: snapshot current level size
        for i := 0; i < levelSize; i++ {
            node := q[0]
            q = q[1:]                   // L3: O(1) dequeue
            if i == levelSize-1 {
                result = append(result, node.Val)  // L4: O(1) record last in level
            }
            if node.Left != nil {
                q = append(q, node.Left)   // L5: O(1) enqueue
            }
            if node.Right != nil {
                q = append(q, node.Right)  // L6: O(1) enqueue
            }
        }
    }
    return result
}

final class Solution { func rightSideView(_ root: TreeNode?) -> [Int] { guard let root else { return [] }; var result: [Int] = [], queue = [root], read = 0; while read < queue.count { let end = queue.count; while read < end { let node = queue[read]; read += 1; if read == end { result.append(node.val) }; if let left = node.left { queue.append(left) }; if let right = node.right { queue.append(right) } } }; return result } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L3 (dequeue)	$O(1)$	n	$O(n)$
L4 (append last)	$O(1)$	h	$O(h)$
L5/L6 (enqueue children)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Every node is enqueued and dequeued exactly once. Only h nodes (one per level) actually contribute to the result.

Complexity

Time: $O(n)$ , driven by L3/L5/L6 processing each node once.
Space: $O(w)$ .

Approach 2: BFS, always take the first right-first

Enqueue right child first, then left; then the first node popped at each level is the rightmost.

Python
Swift

from collections import deque

def right_side_view(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        result.append(q[0].val)         # L1: O(1) peek first (= rightmost)
        for _ in range(len(q)):
            node = q.popleft()          # L2: O(1) dequeue
            if node.right:
                q.append(node.right)    # L3: enqueue right first
            if node.left:
                q.append(node.left)     # L4: enqueue left second
    return result

final class Solution { func rightSideView(_ root: TreeNode?) -> [Int] { guard let root else { return [] }; var result: [Int] = [], queue = [root], read = 0; while read < queue.count { let end = queue.count; result.append(queue[read].val); while read < end { let node = queue[read]; read += 1; if let right = node.right { queue.append(right) }; if let left = node.left { queue.append(left) } } }; return result } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L1 (peek)	$O(1)$	h	$O(h)$
L2 (dequeue)	$O(1)$	n	$O(n)$
L3/L4 (enqueue)	$O(1)$	n	$O(n)$ ← dominates

Complexity

Time: $O(n)$ .
Space: $O(w)$ .

Approach 3: DFS right-first with depth tracking (optimal space)

Preorder-ish DFS that visits the right subtree first. The first node seen at each depth is the rightmost.

def right_side_view(root):
    result = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(result):
            result.append(node.val)      # L1: O(1) first visit at this depth
        dfs(node.right, depth + 1)       # L2: recurse right first
        dfs(node.left, depth + 1)        # L3: recurse left second
    dfs(root, 0)
    return result

function rightSideView(root: TreeNode | null): number[] {
    const result: number[] = [];
    function dfs(node: TreeNode | null, depth: number): void {
        if (!node) return;
        if (depth === result.length) result.push(node.val);  // L1: O(1) first visit at this depth
        dfs(node.right, depth + 1);                          // L2: recurse right first
        dfs(node.left, depth + 1);                           // L3: recurse left second
    }
    dfs(root, 0);
    return result;
}

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, depth int) {
        if node == nil {
            return
        }
        if depth == len(result) {
            result = append(result, node.Val)  // L1: O(1) first visit at this depth
        }
        dfs(node.Right, depth+1)               // L2: recurse right first
        dfs(node.Left, depth+1)                // L3: recurse left second
    }
    dfs(root, 0)
    return result
}

final class Solution { func rightSideView(_ root: TreeNode?) -> [Int] { var result: [Int] = []; func visit(_ node: TreeNode?, _ depth: Int) { guard let node else { return }; if depth == result.count { result.append(node.val) }; visit(node.right, depth + 1); visit(node.left, depth + 1) }; visit(root, 0); return result } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L1 (append)	$O(1)$	h	$O(h)$
L2/L3 (recurse)	$O(1)$ dispatch	n	$O(n)$ ← dominates

Complexity

Time: $O(n)$ .
Space: $O(h)$ recursion (less than or equal to $O(n)$ , often $O(log n)$ ).

For balanced trees, h = log n, which is smaller than the BFS w = n/2 at the last level.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
BFS + last per level	$O(n)$	$O(w)$
BFS right-first	$O(n)$	$O(w)$
DFS right-first	$O(n)$	$O(h)$

All three are linear time. The DFS variant has smaller space for balanced trees; the BFS variant is arguably cleaner.

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 build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def right_side_view(root):
    result = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(result):
            result.append(node.val)
        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return result

def _run_tests():
    assert right_side_view(build_tree([1, 2, 3, None, 5, None, 4])) == [1, 3, 4]
    assert right_side_view(build_tree([1, None, 3])) == [1, 3]
    assert right_side_view(None) == []
    assert right_side_view(build_tree([1])) == [1]
    # left-only tree: left side is visible from right at each level
    t = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert right_side_view(t) == [1, 2, 3]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function rightSideView(root: TreeNode | null): number[] {
    const result: number[] = [];
    function dfs(node: TreeNode | null, depth: number): void {
        if (!node) return;
        if (depth === result.length) result.push(node.val);
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
    dfs(root, 0);
    return result;
}

console.assert(JSON.stringify(rightSideView(buildTree([1, 2, 3, null, 5, null, 4]))) === JSON.stringify([1, 3, 4]));
console.assert(JSON.stringify(rightSideView(buildTree([1, null, 3]))) === JSON.stringify([1, 3]));
console.assert(JSON.stringify(rightSideView(null)) === JSON.stringify([]));
console.assert(JSON.stringify(rightSideView(buildTree([1]))) === JSON.stringify([1]));
const t = new TreeNode(1, new TreeNode(2, new TreeNode(3)));
console.assert(JSON.stringify(rightSideView(t)) === JSON.stringify([1, 2, 3]));
console.log("all tests pass");

Binary Trees & BSTs, depth-indexed value selection
Queues, BFS variants

Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
BFS, the level order frontier pattern for shortest unweighted distance and wave expansion.

199. Binary Tree Right Side View (Medium)

Problem

Try it yourself

Approach 1: BFS, take the last node of each level

Approach 2: BFS, always take the first right-first

Approach 3: DFS right-first with depth tracking (optimal space)

Summary

Test cases

Related data structures

Related concepts