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

Javascript

/**

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

};

Python

# Trick: Just store the lest element on each level

def rightSideView(self, root: TreeNode) -> List[int]:

if not root:

return []

trav, q = [], collections.deque([root])

while q:

cur = None

for i in range(len(q)):

cur = q.popleft()

if cur.left:

q.append(cur.left)

if cur.right:

q.append(cur.right)

trav.append(cur.val)

return trav

DFS Solutions

High level strategy

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

Code

Java

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

}

}

Python

# Trick: Keep track of depth and update it via the traversal length. Make sure you stack left first then right to ensure properly visiting right first.

def rightSideView(self, root: TreeNode) -> List[int]:

if not root:

return []

s, maxdepth = [(root, 1)], -1

trav = []

while s:

cur, depth = s.pop()

if cur:

maxdepth = max(maxdepth, depth)

if len(trav) < depth:

trav.append(cur.val)

if cur.left:

s.append((cur.left, depth+1))

if cur.right:

s.append((cur.right, depth+1))

return trav

C++

//C++

class Solution {

public:

vector<int> rightSideView(TreeNode* root) {

ans = {};

dfs(root, 1);

return ans;

}

void dfs(TreeNode* root, int h) {

if (root == nullptr) return;

if (ans.size() < h) {

ans.push_back(root->val);

}

dfs(root->right, h + 1);

dfs(root->left, h + 1);

}

private:

vector<int> ans;

};