199. Binary Tree Right Side View 🚀
Tags: javascript, programming, tutorial, leetcode
Published: 2022-05-24 16:11:17


***
### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article we will be covering Leetcode's '[199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)' question. 

Question:

> 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:

>![Example](https://assets.leetcode.com/uploads/2021/02/14/tree.jpg)

```
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
```

## Explaining The Question
This Question is rated **Medium**. Which is for the most part accurate. But this is **ONLY** Medium if you have already have solved the [**Medium**](https://leetcode.com/problems/binary-tree-level-order-traversal/) Question. Without knowing this key [Level Order Traversal Pattern](https://leetcode.com/problems/binary-tree-level-order-traversal/) you will struggle to understand this question. It's vital that you know the [Level Order Traversal Pattern](https://leetcode.com/problems/binary-tree-level-order-traversal/). If you do not know this pattern, please solve [**Level Order Traversal Question First**](https://leetcode.com/problems/binary-tree-level-order-traversal/).

I strongly suggest reading [this](https://dev.to/samuelhinchliffe/102-binary-tree-level-order-traversal-2oh5) if you don't understand [level order traversal](https://dev.to/samuelhinchliffe/102-binary-tree-level-order-traversal-2oh5) pattern.

What we're being asked is to imagine we're standing at the right side of the binary tree, what nodes would we see? In other words, if we could only traverse the right visible nodes, meaning node that was hidden behind another node. Now this does sound confusing, but it's actually very simple.

***

##  Recommended Knowledge
1. [Binary Trees](https://en.wikipedia.org/wiki/Binary_tree)
2. [Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

## What do we know?
1. We have a binary tree.
2. This binary tree could have no nodes
3. We need to find all the right-view nodes

## How we're going to do it:

We're going to perform a level order traversal of the binary tree, each time we reach the end of a `row` we're going to push the value of the node into an array. This array will be all the right most nodes. The reason we're doing this is because at the end of each row in the level order traversal will always be visible from a right view. Meaning that all the last nodes on a row are the visible nodes.

1. We're going to declare a variable `right_view` and set it to an empty array. This will house all the right most nodes values.
2. We're going to perform a level order traversal of the binary tree. In the exact same fashion to [Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) question. Where we make note of the length of the queue at each row and only iterate the length of the queue.
3. Once we have reached the last node of a row, we will add it to the `right_view` array.
4. We repeat this until we have iterated through all the rows of the binary tree.

## Big O Notation:
* Time Complexity:   *O(**n**)* | Where ***n*** is the number of nodes in the binary tree. As we will traverse every node.
* Space Complexity: *O(**q**)* | Where ***q*** is the number of the longest row in the binary tree. As we will have to store the length of the queue at each row. Meaning that in the worst case, we will have a queue of length **n**.

## Leetcode Results:

See Submission Link: 

* Runtime: 72 ms, faster than ***77.60%*** of JavaScript online submissions for Binary Tree Right Side View
* Memory Usage: 43.8 MB, less than ***64.69%*** of JavaScript online submissions for Binary Tree Right Side View.

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/problems/binary-tree-right-side-view/submissions/)


***

# The Solution
```

var rightSideView = function (root) {

    // Base case, no nodes given. 
    if (!root) {
        return [];
    }

    // An array to store all the right most nodes
    const right_view = [];

    // A queue for the level order traversal
    const queue = [root];

    // While the queue is not empty, keep going
    while (queue.length) {

        // Make note of the queue length.
        // We do this to perform row by row traversal.
        const q_len = queue.length;

        // Iterate through the queue, end at the row
        for (let i = 0; i < q_len; i++) {

            // Current node
            const node = queue.pop();

            // If the current index is the end of the row,
            // meaning, it's the right most node in the level.
            // Push it to the right_view array.
            if (i === q_len - 1) {
                right_view.push(node.val);
            }

            // Add them. 
            node.left ? queue.unshift(node.left) : null;
            node.right ? queue.unshift(node.right) : null;
        }
    }

    // Return Home!!
    return right_view;
};


```