# Binary Tree Right Side View: One Node Per Level Picture yourself standing to the right of a binary tree, looking at it edge-on. Some nodes stand in plain sight. Others are hiding behind their neighbours. **Binary Tree Right Side View** (LeetCode 199) asks one question: > Which nodes can you see from the right? It sounds like a geometry puzzle. It's actually a lesson in *choosing the right mental model*, and once you have it, the code writes itself. Let's build it from the ground up. * * * ## The Tree We'll Use Throughout ```text 1 / \ 2 3 / \ \ 4 5 7 / 6 ``` Take a moment and answer this yourself before reading on: **what do you see from the right?** If you said `[1, 3, 7]`, you just walked into the trap this problem was designed around. The correct answer is: ```text [1, 3, 7, 6] ``` Node `6` sits in the *left* subtree, and it is still visible. Nothing is to its right at that depth, so nothing blocks it. * * * ## The Trap: "Just Follow the Right Children" The first instinct is almost always this: start at the root and keep walking `node->right` until you fall off the tree. That gives you `1 → 3 → 7`, and it quietly drops `6`. Visibility isn't about *which child pointer you followed*. It's about **what else exists at the same depth**. A node is hidden only if another node at its level sits further to the right. * * * ## The Reframe: One Node Per Level Slice the tree into horizontal levels: ```text Level 0 → 1 Level 1 → 2 3 Level 2 → 4 5 7 Level 3 → 6 ``` From the right, you see exactly one node per level: the **rightmost** one. ```text Level 0 → 1 Level 1 → 3 Level 2 → 7 Level 3 → 6 ``` > **Right Side View = the rightmost node of every level.** That one sentence is the entire problem. Everything else is just two different ways of finding that node. ![Right Side View intuition: the full tree, the viewpoint from the right, and the visible nodes 1 → 3 → 7 → 6](https://res.cloudinary.com/dp7fychwy/image/upload/v1791310600/first_image_iaybnj.jpg align="center") * * * ## Two Ways to Find the Rightmost Node of Each Level | Approach | How it sees the tree | What it picks | | --- | --- | --- | | **DFS (right-first)** | Dives deep, right side first | The **first** node it reaches at each level | | **BFS (level-order)** | Sweeps one level at a time | The **last** node of each level | Same destination, two different routes. Let's walk both. * * * ## Approach 1: DFS, Right First ![Right-first DFS: traverse Root → Right → Left, and the first node reached at each level is the visible one](https://res.cloudinary.com/dp7fychwy/image/upload/v1791310600/second_unkrqx.jpg align="center") A standard DFS visits `Root → Left → Right`. We flip it: ```text Root → Right → Left ``` **Why?** If we always explore the right subtree before the left, then the first time we reach any given depth, we've arrived via the rightmost available path. That first arrival *is* the visible node, so we record it and ignore everything else that shows up at that depth later. ### The One Line That Does the Work ```cpp if (res.size() == level) res.push_back(root->val); ``` This looks cryptic until you see the invariant behind it: > `res.size()` is always the number of levels we've already captured. So when we arrive at a node on `level`: * `res.size() == level`: we've captured levels `0 … level-1` but nothing for this level yet. We're the first to get here, so we're visible. Record it. * `res.size() > level`: this level already has a representative from further right. We're hidden. Skip. No hash map, no per-level bookkeeping. The size of the result vector *is* the state. ### The Solution ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) * : val(x), left(left), right(right) {} * }; */ class Solution { public: vector rightSideView(TreeNode* root) { vector res; dfs(root, 0, res); return res; } private: void dfs(TreeNode* node, int level, vector& res) { if (node == nullptr) return; // First node reached at this depth => the rightmost one if (static_cast(res.size()) == level) { res.push_back(node->val); } // Right before left is what makes "first" mean "rightmost" dfs(node->right, level + 1, res); dfs(node->left, level + 1, res); } }; ``` The same idea in TypeScript: ```ts function rightSideView(root: TreeNode | null): number[] { const res: number[] = []; const dfs = (node: TreeNode | null, level: number): void => { if (!node) return; if (res.length === level) res.push(node.val); dfs(node.right, level + 1); dfs(node.left, level + 1); }; dfs(root, 0); return res; } ``` ### Dry Run On our tree, right-first DFS visits nodes in this order: ```text 1 → 3 → 7 → 2 → 5 → 6 → 4 ``` | Visit | Node | `level` | `res.size()` | Action | `res` | | --- | --- | --- | --- | --- | --- | | 1 | 1 | 0 | 0 | record | `[1]` | | 2 | 3 | 1 | 1 | record | `[1, 3]` | | 3 | 7 | 2 | 2 | record | `[1, 3, 7]` | | 4 | 2 | 1 | 3 | skip, level 1 already has `3` | `[1, 3, 7]` | | 5 | 5 | 2 | 3 | skip, level 2 already has `7` | `[1, 3, 7]` | | 6 | 6 | 3 | 3 | **record**, first node at level 3 | `[1, 3, 7, 6]` | | 7 | 4 | 2 | 4 | skip | `[1, 3, 7, 6]` | Look at step 6. The traversal is deep in the *left* subtree, and node `6` still gets recorded because it's the first node at a depth nobody has reached yet. That's the exact case the "follow right children" shortcut misses. * * * ## Approach 2: BFS, Level by Level ![Level-order BFS: the tree split into levels, with the last node of every level highlighted](https://res.cloudinary.com/dp7fychwy/image/upload/v1791310600/third_hphjtt.jpg align="center") If DFS thinks in *paths*, BFS thinks in *layers*, which matches how we framed the problem in the first place. The plan: 1. Put the root in a queue. 2. Snapshot the queue size. That's exactly the number of nodes in the current level. 3. Process that many nodes, pushing their children as you go. 4. The **last** node processed in the batch is the rightmost. Record it. ```text Level 0 → [1] → last: 1 Level 1 → [2, 3] → last: 3 Level 2 → [4, 5, 7] → last: 7 Level 3 → [6] → last: 6 ``` ### The Solution ```cpp class Solution { public: vector rightSideView(TreeNode* root) { vector res; if (root == nullptr) return res; queue q; q.push(root); while (!q.empty()) { int levelSize = q.size(); // freeze the level boundary for (int i = 0; i < levelSize; i++) { TreeNode* node = q.front(); q.pop(); // Last node of this level => visible from the right if (i == levelSize - 1) { res.push_back(node->val); } if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return res; } }; ``` The line that matters is `int levelSize = q.size();`. The queue keeps growing as we push children, so we must capture the size *before* the inner loop. That snapshot is what turns a flat queue into clean level boundaries. * * * ## DFS vs BFS: Which One Should You Reach For? Both are `O(n)` in time. The difference is in what they cost and how they fail. ![Both approaches converge on the same answer: 1 → 3 → 7 → 6](https://res.cloudinary.com/dp7fychwy/image/upload/v1791310600/fourth_tdgt20.jpg align="center") | | **DFS (Right → Left)** | **BFS (Level-order)** | | --- | --- | --- | | **Mental model** | First arrival at each depth wins | Last node in each layer wins | | **Takes** | First node per level | Last node per level | | **Time** | `O(n)` | `O(n)` | | **Extra space** | `O(h)`, the recursion stack | `O(w)`, the queue | | **Worst case for space** | Skewed tree, `h = n` | Wide, complete tree, `w ≈ n/2` | | **Failure mode** | Stack overflow on very deep trees | Memory pressure on very wide trees | Here `h` is the height of the tree and `w` is its maximum width. **Rule of thumb:** * Reach for **DFS** when the tree is reasonably balanced and you want the shortest code. * Reach for **BFS** when the input could be deeply skewed. A linked-list-shaped tree with 100,000 nodes will blow a default recursion stack, while a queue won't care. * In an interview, state the trade-off out loud. Naming the failure mode of each approach is what separates "I memorised a solution" from "I understand the structure." * * * ## Edge Cases Worth Checking | Input | Expected | Why it's interesting | | --- | --- | --- | | `nullptr` | `[]` | BFS needs the explicit guard. DFS handles it through its base case. | | Single node | `[1]` | Trivial, but confirms the base path. | | Left-skewed (`1 → 2 → 3` via `left`) | `[1, 2, 3]` | Every node is visible. This breaks the "follow right pointers" shortcut immediately. | | Right-skewed | Same as input | Right-first DFS never needs to visit the left side. | A small C++ note: `res.size()` returns `size_t` (unsigned), while `level` is an `int`. Comparing them directly compiles but triggers sign-comparison warnings, which many teams treat as errors. The `static_cast` in the DFS solution above keeps it clean. * * * ## The Pattern Behind the Pattern This problem is really a template for a whole family: * **Left Side View**: mirror it. Visit left first in DFS, or take `i == 0` in BFS. * **Binary Tree Level Order Traversal**: the same BFS skeleton, collecting every node instead of one. * **Zigzag Level Order**: the same skeleton with alternating direction. * **Average of Levels / Largest Value in Each Row**: aggregate per level instead of picking one node. * **Top View / Bottom View**: the same "one representative per slot" idea, but slots are horizontal columns instead of depths. The skill being tested is **how you partition a tree**: by level, by column, or by path. Once you can name the partition, the traversal is mechanical. * * * ## Final Takeaway Don't ask *"which child do I follow?"* Ask *"what does each level contribute?"* ```text DFS → visit Right first → keep the FIRST node seen at each level BFS → sweep level by level → keep the LAST node seen at each level ``` Two traversals, one idea: > **Right Side View = the rightmost node of every level.** If this helped, try the mirror image (Left Side View) without looking at the code. If you can write it in under two minutes, the pattern has stuck. Happy coding. 🌳