Skip to content

🌲 Tree: Binary Tree Right Side View

📝 Description

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

Real-World Application

This mimics Occlusion Culling in Computer Graphics (rendering a scene from a specific camera angle) or finding the "boundary" of a hierarchical structure.

🛠️ Constraints & Edge Cases

  • Number of nodes is between 0 and \(10^4\).
  • Edge Cases to Watch:
    • Left branch is deeper/longer than right branch (must see left nodes).
    • Empty tree.

🧠 Approach & Intuition

The Aha! Moment

The "right side view" is simply the last node visited in each level during a Level Order Traversal (BFS). Alternatively, in DFS (Root -> Right -> Left), it's the first node visited at each depth.

🐢 Brute Force (Naive)

BFS and store all levels, then pick the last element. Space inefficient (\(O(N)\) storage for result of all levels).

🐇 Optimal Approach (BFS)

  1. Standard BFS with Queue.
  2. At each level iteration, identify the last node (i == len(q) - 1).
  3. Add it to result.

🧩 Visual Tracing

graph TD
    A[1] --> B[2]
    A --> C[3]
    B --> D[5]
    C --> E[4]
    Res[View: 1, 3, 4]

💻 Solution Implementation

(Implementation details need to be added...)

⏱️ Complexity Analysis

  • Time Complexity: \(\mathcal{O}(N)\) — BFS visits all nodes.
  • Space Complexity: \(\mathcal{O}(D)\) — Diameter of tree (max width).

🎤 Interview Toolkit

  • Alternative: DFS (Pre-order Root->Right->Left). Pass level. If level == len(res), add node.