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
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)
1 // BFS with a queue
2 public List<Integer> rightSideView(TreeNode root) {
3 List<Integer> res = new ArrayList<>();
4 if (root == null) {
5 return res;
6 }
7
8 // need to put node in the queue, not value
9 Queue<TreeNode> q = new LinkedList<>();
10 q.add(root);
11
12 while (!q.isEmpty()) {
13 int s = q.size();
14 // classic template for bfs, remember the queue size is the current level
15 for (int i = 0; i < s; i++) {
16 TreeNode t = q.poll();
17 // the last element is right side view
18 if (i == s - 1) {
19 res.add(t.val);
20 }
21 if (t.left != null) q.offer(t.left);
22 if (t.right != null) q.offer(t.right);
23 }
24 }
25
26 return res;
27 }
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)
1 private void dfsHelper(Map<Integer, Integer> depthToValue, TreeNode node, int depth) {
2 if (node == null) {
3 return;
4 }
5
6 // this is a pre-order traversal, essentially keep overwriting the depthToValue map (right view)
7 // while traverse the tree from left to right
8 depthToValue.put(depth, node.val);
9 dfsHelper(depthToValue, node.left, depth + 1);
10 // overwrite the right side view since right side recursion comes later
11 dfsHelper(depthToValue, node.right, depth + 1);
12 }
13
14 public List<Integer> rightSideView(TreeNode root) {
15 Map<Integer, Integer> depthToValue = new HashMap<>();
16 dfsHelper(depthToValue, root, 1);
17
18 int depth = 1;
19
20 List<Integer> result = new ArrayList<>();
21
22 while (depthToValue.containsKey(depth)) {
23 result.add(depthToValue.get(depth));
24 depth++;
25 }
26 return result;
27 }
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)