LC199. Binary Tree Right Side View

Problem Description#

Source: https://leetcode.com/problems/binary-tree-right-side-view/

Given 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.

For example: Given binary tree [1, 2, 3, null, 6, null, 4, null, null, 5],

1 <----- 1
/ \
2 3 <----- 3
\ \
6 4 <----- 4
/
5 <----- 5

return [1, 3, 4, 5].

BFS Solution#

High level strategy#

Our strategy to solve this problem is to conduct a breadth-first search. On each level, we traverse from the left to right, but only keeping the value of the right-most node. To implement this solution, we will make use of the index property of arrays. The index of every element in the resulting array is the level of the corresponding right-most node on the tree. To see this, one can simply flip the tree on its side. The time complexity of this solution is O(n), where 'n' is equal to the number of nodes. The space complexity of this solution is O(logn), or O(h), where 'h' is equal to the height of the tree.

result: [1, 3, 4, 5];
1 <----- the right-most element is 1, which is equal to result[0];
/ \
2 3 <----- the right-most element is 3, which is equal to result[1];
\ \
6 4 <----- the right-most element is 4, which is equal to result[2];
/
5 <----- the right-most element is 5, which is equal to result[3];

Code#

/**
* 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)
* }
**/
const rightSideView = (root) => {
let result = [];
let recurse = (node, level) => {
if (node === null) return;
result[level] = node.val; // as we traverse from the left to right, the element on that level in the result array will be replaced with the right most node in the tree.
recurse(node.left, level + 1);
recurse(node.right, level + 1);
};
recurse(root, 0);
return result;
};

DFS Solutions#

High level strategy#

We can modify the code and covert it into a DFS solution, the same concept applies.

Code#

class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new LinkedList<>();
dfs(root, 1, ans);
return ans;
}
private void dfs(TreeNode node, int level, List<Integer> ans){
if(node == null){
return;
}
if(level > ans.size()){ // push current node to it
ans.add(node.val);
}
dfs(node.right, level+1, ans);
dfs(node.left, level+1, ans);
}
}