| Question | 199. Binary Tree Right Side View – Leetcode Javascript Solution |
| Difficulty | Medium |
| Question Type | Tree, Binary Tree |
| Question Link | https://leetcode.com/problems/binary-tree-right-side-view/ |
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: From right side of tree, we can able to see these items only.Example 2:
Input: root = [1, null, 3]
Output: [1, 3]Example 3:
Input: root = []
Output: []Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100What is Right Side View in Binary Tree?
Right view of a Binary Tree is set of nodes visible when tree is visited from Right side. As illustrated in below image, The nodes which are visible to the observer will be the rightmost nodes at each level. All the other nodes will be hidden since they will hide behind the rightmost nodes in their respective levels.
Solution 1 : ( Using Breadth First Search [ BFS ] )
BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level. BFS builds the tree level by level.
We will see that our main task is to print the right most node of every level. So, we will do a Breadth First Search approach of level order traversal on the tree and print the last node at every level. Below is the implementation of above BFS Traversal approach:
// ------ Breadth First Search Leetcode solution start - jsdiet ------
var rightSideView = function (root) {
if (!root) {
return [];
}
let queue = [root], result = [];
while (queue.length) {
let length = queue.length, count = 0, currentNode;
while (count < length) {
currentNode = queue.shift();
if (currentNode && currentNode.left) {
queue.push(currentNode.left);
}
if (currentNode && currentNode.right) {
queue.push(currentNode.right);
}
count++;
}
result.push(currentNode.val);
}
return result;
};
// ------ Breadth First Search Leetcode solution end - jsdiet ------
// Leetcode environment provides already generated binary tree.
// So below part of code no need, if you are trying in Leetcode website environment.
// ------- Code to generate our binary tree -------
// This is purely for testing in local machine
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
insert(values) {
const queue = [this];
let i = 0;
while (queue.length > 0) {
let current = queue.shift();
for (let side of ["left", "right"]) {
if (!current[side]) {
if (values[i] !== null) {
current[side] = new TreeNode(values[i]);
}
i++;
if (i >= values.length) return this;
}
if (current[side]) queue.push(current[side]);
}
}
return this;
}
}
// Execute using BFS
const tree = new TreeNode(1);
tree.insert([2, 3, null, 5, null, 4]);
Complexity Analysis :
Time complexity: O(n)
Space complexity: O(W)
Time complexity: O(n), where n is number of nodes in the binary tree.
Space complexity: O(W), where W is Max width of Binary Tree, since we are using BFS approach. Usually, we can call it is O(n) space complexity.
In BFS, we might traverse through each level of nodes. But our main goal is to find right side view, which means we need to focus on depth of tree instead visiting all nodes. In this case, DFS approach is more suitable. Lets see how we can optimize above problem with DFS approach.
Solution 2 ( Using Depth First Search [ DFS ] ) : ==> Optimized
Depth First Search(DFS) is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.
DFS algorithm is a recursive algorithm that uses the idea of backtracking
// ------ Depth First Search Leetcode solution start - jsdiet ------
// using DFS -> PreOrder NRL traversal
var rightSideView = function (root) {
const result = [];
dfs(root, 0, result);
return result;
};
const dfs = (node, currentLevel, result) => {
if (!node) {
return;
}
if (currentLevel >= result.length) {
result.push(node.val);
}
if (node.right) {
dfs(node.right, currentLevel + 1, result);
}
if (node.left) {
dfs(node.left, currentLevel + 1, result);
}
}
// ------ Depth First Search Leetcode solution end - jsdiet ------
// Leetcode environment provides already generated binary tree.
// So below part of code no need, if you are trying in Leetcode website environment.
// ------- Code to generate our binary tree -------
// This is purely for testing in local machine
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
insert(values) {
const queue = [this];
let i = 0;
while (queue.length > 0) {
let current = queue.shift();
for (let side of ["left", "right"]) {
if (!current[side]) {
if (values[i] !== null) {
current[side] = new TreeNode(values[i]);
}
i++;
if (i >= values.length) return this;
}
if (current[side]) queue.push(current[side]);
}
}
return this;
}
}
const tree = new TreeNode(1);
tree.insert([2, 3, null, 5, null, 4]);
// Execute using DFS
let val = rightSideView(tree);
console.log(val);Complexity Analysis :
Time complexity: O(n)
Space complexity: O(H)
Time complexity: O(n), where n is number of nodes in the binary tree.
Space complexity: O(H), where H is Max height of Binary Tree, since we are using DFS approach. Usually, we can call it is O(n) space complexity because of recursive calls.
DFS is better approach compare to BFS, while finding depth of tree traversal.
If you have any doubts, add in comment section. Will clarify at my level best. Also, if you have better solution, kindly share it, will grow together as to become better engineer.
