binary tree right side view

🏠

Quite an easy question: write a python function that can return the right side view of a binary tree.

G 45 45 25 25 20 20 10 10 20->10 20->25 30 30 30->20 30->45

This really just involves an inorder traversal, where we write the node data into a dict. The key for the dict is the level.

 1 def right_side_view(T):
 2     def rs(T, l=0):
 3         if T.left:
 4             rs(T.left, l+1)
 5         d[l] = T.key
 6         if T.right:
 7             rs(T.right, l+1)
 8     d = {}
 9     rs(T)
10     return [x[1] for x in sorted(d.items(), key=lambda x: x[0])]
11 
12 class Tree:
13     def __init__(self, key, left=None, right=None):
14         self.key = key
15         self.left = left
16         self.right = right
17 
18 T = Tree(1, Tree(2, None, Tree(5, Tree(7, None, Tree(8)), Tree(6, Tree(5)))), Tree(3))
19 
20 result = right_side_view(T)
21 print(result)