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.
1Example:
2
3Input: [1,2,3,null,5,null,4]
4Output: [1, 3, 4]
5Explanation:
6
7 1 <---
8 / \
92 3 <---
10 \ \
11 5 4 <---
Solution
Performing a traversal of the tree, while keeping track of the current depth, and updating a dictionary at that given depth, with the current node value, in-order naturally results in the right-side view being stored in the dict.
This will work as long as we first visit the left child, update the dictionary, then visit the right child. If we were to visit the right child first, update the dictionary, then visit the left child, this would result in a left-side view of the tree.
1def right_side_view(root):
2 def dfs(node, depth=0):
3 if node:
4 dfs(node.left, depth+1)
5 res[depth] = node.key
6 dfs(node.right, depth+1)
7 res = {}
8 dfs(root)
9 return [*res.values()]
10
11class Tree:
12 def __init__(self, key, left=None, right=None):
13 self.key = key
14 self.left = left
15 self.right = right
16
17tree = Tree('a', Tree('b', Tree('c', Tree('d'), Tree('e')), Tree('f', Tree('g'), Tree('h'))), Tree('i', Tree('j', Tree('k'), Tree('l')), Tree('m', Tree('n'), Tree('o'))))
18
19result = right_side_view(tree)
20print(result)
Time and Space Complexity
Note
A BFS approach is also possible, and is slightly more memory efficient. The space requirement for a DFS is H
, where H
is the height of the tree, which can, in the worst case, be N
. The BFS uses at most the width of the tree in terms of space. The simpler DFS approach is preferred, since there is little point adding extra complexity of theoretical 'worst case' gains.