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

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

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.

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

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

Same asymptotic; slightly tighter inner loop. The reversal (right before left) ensures the first element of the next level is the rightmost.

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

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.

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.

Test cases

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()

Related data structures

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