Skip to content

084 — Binary Tree Right Side View

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

84 — Binary Tree Right Side View

LeetCode 199 · Medium. 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.

🍽️ Intuition

Standing to the right of the tree, for every level you can only see whichever node is furthest to the right on that level — everything to its left is hidden behind it. That's it: the "right side view" is just "the last node in each level of a level-order traversal." Once you already know how to walk a tree level by level, this problem is really just "keep the last one, throw away the rest."

🚩 Pattern-Recognition Cue

"What's visible from the side" / "rightmost node per level" is a level-order (BFS) problem wearing a costume — same queue-driven, level-by-level walk as Binary Tree Level Order Traversal, just keeping only the final node visited in each round instead of the whole level.

🐢 Brute Force

Run a full level-order traversal, building every level's complete array of values (just like Chapter 83), and then map over the finished list of levels to keep only the last value of each one.

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val }
}

func collectLevels(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }
    var result: [[Int]] = []
    var queue: [TreeNode] = [root]

    while !queue.isEmpty {
        let levelSize = queue.count
        var level: [Int] = []
        for _ in 0..<levelSize {
            let node = queue.removeFirst()
            level.append(node.val)
            if let left = node.left { queue.append(left) }
            if let right = node.right { queue.append(right) }
        }
        result.append(level)
    }
    return result
}

func rightSideViewBruteForce(_ root: TreeNode?) -> [Int] {
    let levels = collectLevels(root)
    return levels.compactMap { $0.last }
}

// smoke test:      1
//                /   \
//               2     3
//                \      \
//                 5      4
let bfRoot = TreeNode(1)
bfRoot.left = TreeNode(2); bfRoot.right = TreeNode(3)
bfRoot.left?.right = TreeNode(5)
bfRoot.right?.right = TreeNode(4)
print(rightSideViewBruteForce(bfRoot))   // [1, 3, 4]

Big-O: O(n) time — one full BFS pass. O(n) extra space — every value at every level is stored in full, even though only one value per level (O(h) total) actually ends up in the answer.

🚀 Optimal

Do a DFS that visits the right child before the left child at every node, tracking depth as it descends. The very first time a given depth is reached, record that node's value — since right is explored first, the first node seen at each new depth is guaranteed to be the rightmost one.

func rightSideView(_ root: TreeNode?) -> [Int] {
    var result: [Int] = []

    func dfs(_ node: TreeNode?, _ depth: Int) {
        guard let node = node else { return }

        if depth == result.count {
            // first time we've reached this depth — since right is visited first,
            // this must be the rightmost node at this level
            result.append(node.val)
        }

        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)
    }

    dfs(root, 0)
    return result
}

// smoke test: same tree as above
let root = TreeNode(1)
root.left = TreeNode(2); root.right = TreeNode(3)
root.left?.right = TreeNode(5)
root.right?.right = TreeNode(4)
print(rightSideView(root))   // [1, 3, 4]

print(rightSideView(nil))   // [] — empty tree, nothing visible

// left-only skewed tree: 1 -> 2 -> 3 (no right children at all)
let skewed = TreeNode(1)
skewed.left = TreeNode(2)
skewed.left?.left = TreeNode(3)
print(rightSideView(skewed))   // [1, 2, 3] — with no right children, the left spine IS what's visible

Big-O: O(n) time — every node is still visited exactly once. O(h) extra space for both the recursion stack and the result array — the result has exactly one entry per level (h levels total), never storing a full level's worth of values along the way.

🔑 The Key Insight

The brute force builds every level completely just to immediately discard all but the last value — an O(n)-sized intermediate structure in service of an answer that's only ever O(h) values long. Visiting right before left flips which node "claims" a depth first: since the rightmost branch at any depth is always explored before anything to its left, the very first arrival at a new depth is guaranteed to be the correct answer for that level, and every subsequent arrival at that same depth can be safely ignored. That turns "collect everything, then filter" into "record only what you need, exactly once."

🔗 Related Chapters

  • Binary Trees — the structure being viewed.
  • Queues & Deques — the queue driving the brute force's full level-order walk.
  • BFS — the brute force's level-by-level traversal is the same queue walk as Binary Tree Level Order Traversal, just keeping the last node per level instead of the whole level.

🧸 Memory Sentence

Right Side View is standing to the right of the tree and only ever seeing whoever got there first — visit right before left, and the first node to claim each new depth is the one you can see.

✅ Check Your Understanding

Trace the optimal dfs on the tree 1 -> (2 -> right(5), 3 -> right(4)), writing down the order in which nodes are visited and the value of result after each visit. Then explain why visiting node.right before node.left is essential — what would rightSideView return on this same tree if the recursive calls were swapped to visit node.left first?

⬅️ Previous: Binary Tree Level Order Traversal · Next: Count Good Nodes in Binary Tree ➡️

Clone this wiki locally