Leetcode solution 199: Binary Tree Right Side View

Problem Statement 

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.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

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

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

This is a great problem and I highly recommend we solve it in both DFS and BFS for level order traversal because it  covers everything we need to know about trees in interviews.

This would be a better test case because right subtree would not be deep enough to cover the left subtree

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

[1, 3, 5] 

Level order traversal using BFS(queue)

It should be relatively natural for us think about using level order traversal and we can simply use a queue and always find the right most element when we pop out element from each level.

Level order traversal using DFS(map)

A pre-order traversal way, just like order level traversal using DFS with a map(key is depth, value is node). This method utilizes a depth to value map to record the right most value on each order while performing a pre-order traversal, namely record the node value, go left then go right. This way, right value can always overwrite the left value thus keeping a “right side view”



I personally don't like the leetcode official solution, where in DFS you don’t need two stacks and in
BFS you don’t need the maps.

Follow up, how about implement a left side view? Trivial right?

Solutions

Level order traversal using BFS(queue)

Time Complexity: O(N) since we visit each node once
Space Complexity: O(N), more precisely the number of element on the last level, aka queue size when it’s a complete tree

Level order traversal using DFS(map)

Time Complexity: O(N) since we visit each node once

Space Complexity: O(lgN) because we are using a map and map size should be tree height, which worst case could be O(N)

References

• Leetcode official solution  
• Code solving level order traversal using DFS with a map