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

 1from collections import defaultdict as dd
 2
 3
 4class 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
14class 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
29null = None
30
31t = [0, 8, 1, null, null, 3, 2, null, 4, 5, null, null, 7, 6]
32t = 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)
41r = Solution().verticalTraversal(t)
42print(r)