Solution Developed In:

The Question

For this article we will be covering Leetcode's '199. 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:

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 Question. Without knowing this key Level Order Traversal Pattern you will struggle to understand this question. It's vital that you know the Level Order Traversal Pattern. If you do not know this pattern, please solve Level Order Traversal Question First.

I strongly suggest reading this if you don't understand level order traversal 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
2. 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 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.

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;
};