Skip to content

Volume ITechnology

4.14.9 — Binary Tree Right Side View ​

LeetCode 199 · Medium · ★ Blind 75

The problem ​

Standing to the right of the tree, list the nodes you can see, top to bottom.

   1            visible: 1, 3, 4
 /   \
2     3
 \
  4

Note that 4 is visible even though it is on the left branch — nothing on the right side of the tree reaches that depth, so 4 is the rightmost node at its level.

Constraints to Keep in Mind: ​

  • 0 <= Number of nodes in the tree <= 100
  • -100 <= Node.val <= 100
  • The tree can be empty or severely unbalanced.

The brute force, and where it wastes work ​

The simplest idea might be to just extract the rightmost branch of the tree: root, root.right, root.right.right, etc.

  • Why it's wrong: As shown in the example, a node on the left branch (like 4) can still be visible if there is no node on the right branch at that depth. We must explore the whole tree to guarantee we find the rightmost node at every single level.
  • The real solution: We must use a full traversal, either Breadth-First Search (BFS) to process it level by level, or Depth-First Search (DFS) with careful ordering. Both will take O(n) time since we might have to check every node.

The pattern ​

"The rightmost node at each level" is the definition, so this is 4.14.8 with one line changed: instead of collecting every value in a level, keep only the last one.

The solution ​

python
from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:                           # (1)
            return []

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

        while queue:
            size = len(queue)                  # (2)
            for i in range(size):
                node = queue.popleft()
                if i == size - 1:              # (3) the last node of this level
                    result.append(node.val)
                if node.left:                  # (4)
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result
ts
function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];                         // (1)

  const result: number[] = [];
  let queue: TreeNode[] = [root];

  while (queue.length) {                        // (2) queue holds exactly one level
    result.push(queue[queue.length - 1].val);   // (3) last of this level
    const next: TreeNode[] = [];
    for (const node of queue) {
      if (node.left) next.push(node.left);      // (4)
      if (node.right) next.push(node.right);
    }
    queue = next;
  }

  return result;
}

Line by line ​

(1) An empty tree shows nothing.

(2) Freeze the size of the current level. Exactly as in 4.14.8, the size is measured before the inner loop, so the loop handles exactly one level.

(3) Keep only the last node of the level. When i reaches size - 1, this is the final node of the level. Children were queued left before right, so the final node is the rightmost one. That is the node you would see standing to the right of the tree. TypeScript reads it directly, as the last item of the array that holds the level.

(4) Queue the children, left before right. You might think only the right children matter. They do not. The left child must still be queued, because it may be the rightmost node of its level if nothing on the right reaches that deep. That is exactly why node 4 is visible in the example.

Hand Trace (BFS) ​

Trace on the example tree [1, 2, 3, None, 4, None, None]

  • Initial: queue = [1], result = []

Round 1:

  • size = 1. i = 0. Pop 1.
  • i == 1 - 1 (0 == 0), so append 1 to result.
  • Queue children: queue = [2, 3]. result = [1].

Round 2:

  • size = 2. queue = [2, 3].
  • i = 0. Pop 2. 0 != 1, do not append. Queue children: 4. queue = [3, 4].
  • i = 1. Pop 3. 1 == 1, append 3 to result. Queue children: none. queue = [4].
  • result = [1, 3].

Round 3:

  • size = 1. queue = [4].
  • i = 0. Pop 4. 0 == 0, append 4 to result. Queue children: none.
  • result = [1, 3, 4]. ✓

size must be captured before the inner loop, exactly as in 4.14.8 — children added during the round would otherwise change len(queue) mid-loop and the comparison i == size - 1 would fire at the wrong moment.

Children are still enqueued left before right, even though you only want the rightmost. The order matters because it determines which node ends up last.

The DFS version ​

Walk depth-first, visiting the right child first, and record a value the first time you reach each new depth.

python
def rightSideView(self, root):
    result = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(result):        # first node seen at this depth
            result.append(node.val)     # and we came from the right, so it is rightmost
        dfs(node.right, depth + 1)      # right FIRST
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return result

depth == len(result) means no node at this depth has been recorded yet. Since the right subtree is explored first, the first arrival at any depth is the rightmost node there.

It uses O(h) space instead of O(w), so on a balanced tree it is the cheaper version. Swap the two recursive calls and you get the left side view, which is a good check that you understood why the order matters.

Complexity ​

  • Time Complexity: O(n) time either way. We visit every single node exactly once to ensure we don't miss a deep node on the left side that has no right-side counterpart.
  • Space Complexity: O(w) space for BFS (where w \approx n/2 in a balanced tree for the queue), O(h) for DFS (where h is the height of the tree for the recursion stack).

Edge cases ​

  • Empty tree. Returns [].
  • Only left children, a line going down-left. Every node is the only node on its level, so every node is visible.
  • A deep left branch and a short right branch, like the example. The deeper left nodes become visible below the point where the right branch ends.

Where this goes next ​

Same BFS skeleton, different line inside the level loop:

  • Average of Levels — sum the level and divide.
  • Largest Value in Each Row — take the maximum.
  • Zigzag Level Order — reverse alternate levels.
  • Find Bottom Left Tree Value — the first node of the last level. Easiest as BFS pushing right before left, then taking the final node processed.

The rule: BFS with a frozen level length gives you every "per level" question. Only the line inside the loop changes.

What the interviewer will push on ​

"Why is 4 visible in the example?" It is the rightmost node at its depth. The view is per level, not per branch.

"Do it depth-first." Right child first, record on first arrival at a depth.

"How would you get the left side view?" Swap the two recursive calls, or take the first node of each level in BFS.

One thing to volunteer: say that this is the level-order template with one line changed. Recognising a problem as a variant, out loud, is worth as much as solving it.

Next: 4.14.10 Count Good Nodes in Binary Tree — information flowing down the tree instead of up.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet