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.