# vertical order traversal of a binary tree

🏠

My solution. Runs faster than 82% of python solutions. I also think it's the cleanest.

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree

 1 from collections import defaultdict as dd
2
3
4 class TreeNode:
5     def __init__(self, val=0, left=None, right=None):
6         self.val = val
7         self.left = left
8         self.right = right
9
10     def __str__(self):
11         return str(self.val)
12
13
14 class Solution:
15     def verticalTraversal(self, root):
16         def rec(node, lr, d):
17             if node:
18                 vals[lr].append((d, node.val))
19                 rec(node.left, lr - 1, d + 1)
20                 rec(node.right, lr + 1, d + 1)
21
22         vals = dd(list)
23         rec(root, 0, 0)
24         return [
25             *map(lambda x: [*map(lambda x: x[1], sorted(x[1]))], sorted(vals.items()))
26         ]
27
28
29 null = None
30
31 t = [0, 8, 1, null, null, 3, 2, null, 4, 5, null, null, 7, 6]
32 t = TreeNode(
33     0,
34     TreeNode(8),
35     TreeNode(
36         1,
37         TreeNode(3, None, TreeNode(4, None, TreeNode(7))),
38         TreeNode(2, TreeNode(5, TreeNode(6))),
39     ),
40 )
41 r = Solution().verticalTraversal(t)
42 print(r)