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 thevalues
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
What do we know?
- We have a binary tree.
- This binary tree could have no nodes
- 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.
- 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. - 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.
- Once we have reached the last node of a row, we will add it to the
right_view
array. - 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;
};
Top comments (0)