# Binary Tree Right Side View
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-tree-right-side-view)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-right-side-view
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Accolite](https://scaleengineer.com/companies/accolite), [Flipkart](https://scaleengineer.com/companies/flipkart), [Google](https://scaleengineer.com/companies/google), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
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_.

**Example 1:**

**Input:** root = \[1,2,3,null,5,null,4\]

**Output:** \[1,3,4\]

**Explanation:**

![](https://assets.glich.co/dsa/binary-tree-right-side-view/image0.png)

**Example 2:**

**Input:** root = \[1,2,3,4,null,null,null,5\]

**Output:** \[1,3,4,5\]

**Explanation:**

![](https://assets.glich.co/dsa/binary-tree-right-side-view/image1.png)

**Example 3:**

**Input:** root = \[1,null,3\]

**Output:** \[1,3\]

**Example 4:**

**Input:** root = \[\]

**Output:** \[\]

**Constraints:**

* The number of nodes in the tree is in the range `[0, 100]`.
* `-100 <= Node.val <= 100`

# Approaches
## Breadth-First Search (Level Order Traversal)
This approach uses Breadth-First Search (BFS) to traverse the tree level by level. For each level, the very last node that gets processed is the rightmost node. We can identify this node and add its value to our result list. This method is highly intuitive because the problem is defined in terms of levels, and BFS is the natural algorithm for level-by-level processing.
**Time:** O(N) · **Space:** O(W)
**Pros:** It's a very direct and intuitive approach that maps well to the problem statement.; It works for any binary tree and correctly identifies the rightmost node at each level.; It can be more space-efficient than DFS for very deep and narrow (skewed) trees.
**Cons:** The space complexity can be significant for wide trees. In the worst case of a complete binary tree, the queue might need to store up to N/2 nodes, where N is the total number of nodes.
### Explanation
We can solve this problem using a standard level order traversal, which is implemented with a queue. The idea is to traverse the tree one level at a time. For each level, we want to find the rightmost node. When we process a level, we know exactly how many nodes are on that level (it's the size of the queue at the beginning of the level's processing). We can iterate through all nodes of the current level, and the last node we pull from the queue in that iteration will be the rightmost one. We add this node's value to our result list. We repeat this for all levels until the entire tree is traversed.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                // If it's the last node of the current level
                if (i == levelSize - 1) {
                    result.add(currentNode.val);
                }
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Create an empty list `result` to store the right side view.
- If the `root` is null, return the empty list.
- Create a `Queue` and add the `root` node to it.
- Loop while the queue is not empty:
  - Get the number of nodes at the current level, `levelSize = queue.size()`.
  - This `levelSize` is crucial as it defines the boundary for the current level.
  - Loop `levelSize` times:
    - Dequeue a node, let's call it `currentNode`.
    - Check if this is the last node of the level. This can be determined if the loop index `i` is equal to `levelSize - 1`.
    - If it is the last node, add its value to the `result` list.
    - Enqueue the left child of `currentNode` if it exists.
    - Enqueue the right child of `currentNode` if it exists.
- After the main loop finishes, return the `result` list.

## Depth-First Search (Reverse Pre-order)
A more elegant and often more space-efficient approach uses Depth-First Search (DFS). The trick is to modify the standard pre-order traversal (Root-Left-Right) to a reverse pre-order traversal (Root-Right-Left). By visiting the right subtree first, we ensure that the first node we encounter at any given depth is the rightmost node at that level. We use the size of our result list to track the maximum depth visited so far.
**Time:** O(N) · **Space:** O(H)
**Pros:** Very concise and elegant code.; Generally more space-efficient than BFS for balanced or complete binary trees, as its space complexity depends on the tree's height (O(log N)) rather than its width (O(N)).
**Cons:** The recursion depth can be large for skewed trees, potentially leading to a `StackOverflowError` for extremely deep trees. The worst-case space complexity is O(N) for a skewed tree.
### Explanation
This approach leverages recursion and a specific traversal order to solve the problem efficiently. We define a recursive function that takes the current node, its level (or depth), and the result list. The key idea is to traverse the right subtree of any node before its left subtree. 

When our recursive function visits a node at a certain `level`, we check if we've seen this level before. We can do this by comparing the `level` with the current size of our `result` list. If `level == result.size()`, it means we're encountering a node at this depth for the first time. Because our traversal prioritizes the right side, this first-encountered node is guaranteed to be the rightmost node at that level. We add its value to the `result` list. For any subsequent nodes visited at the same level (which would be to the left of the one we just added), the condition `level == result.size()` will be false, so we won't add them. This elegantly builds the right-side view.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<Integer> result) {
        if (node == null) {
            return;
        }
        // If this is the first time we visit this level, it must be the rightmost node.
        if (level == result.size()) {
            result.add(node.val);
        }
        // Traverse right subtree first
        dfs(node.right, level + 1, result);
        // Then traverse left subtree
        dfs(node.left, level + 1, result);
    }
}
```
### Algorithm
- Create an empty list `result`.
- Call a recursive helper function, for example, `dfs(node, level, result)`.
- The initial call would be `dfs(root, 0, result)`.
- Inside the `dfs` function:
  - If the current `node` is null, simply return.
  - Check if the current `level` is equal to the size of the `result` list. If it is, this means we are visiting this level for the first time. Since we traverse the right side first, this node must be the rightmost one. Add `node.val` to `result`.
  - Make a recursive call for the right child, incrementing the level: `dfs(node.right, level + 1, result)`.
  - Make a recursive call for the left child, incrementing the level: `dfs(node.left, level + 1, result)`.
- After the initial call returns, the `result` list will contain the right side view.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > rightSideView ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { ans . add ( q . peekLast (). val ); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } } return ans ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var rightSideView =
  function (root) {
    const ans = [];
    if (!root) {
      return ans;
    }
    const q = [root];
    while (q.length > 0) {
      ans.push(q[0].val);
      const nq = [];
      for (const { left, right } of q) {
        if (right) {
          nq.push(right);
        }
        if (left) {
          nq.push(left);
        }
      }
      q.length = 0;
      q.push(...nq);
    }
    return ans;
  };

```

### CPP

```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 < int > rightSideView ( TreeNode * root ) { vector < int > ans ; if ( ! root ) { return ans ; } queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { ans . emplace_back ( q . back () -> val ); for ( int n = q . size (); n ; -- n ) { TreeNode * node = q . front (); q . pop (); if ( node -> left ) { q . push ( node -> left ); } if ( node -> right ) { q . push ( node -> right ); } } } return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def rightSideView ( self , root : Optional [ TreeNode ]) -> List [ int ]: ans = [] if root is None : return ans q = deque ([ root ]) while q : ans . append ( q [ - 1 ]. val ) # add last node of previous level traversal results for _ in range ( len ( q )): node = q . popleft () if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) return ans ############# # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class Solution ( object ): def rightSideView ( self , root ): """ :type root: TreeNode :rtype: List[int] """ def dfs ( root , h ): if root : if h == len ( ans ): ans . append ( root . val ) # pre-order, all the way to the right dfs ( root . right , h + 1 ) dfs ( root . left , h + 1 ) ans = [] dfs ( root , 0 ) return ans
```