Vertical Order Traversal of a Binary Tree

Problem Id: 987 Difficulty: Hard Tag: Hash Table Tag: Tree


Intuition

Just do a BFS and get the order. Please notice that we use a dict instead of list to save the result because the x index could be negative.

Also, one important thing is that, if two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque


class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        queue = deque([[root, 0, 0]])
        vertical_data = {}
        while queue:
            node, x, y = queue.popleft()
            if x not in vertical_data:
                vertical_data[x] = {}
            if y not in vertical_data[x]:
                vertical_data[x][y] = []
            vertical_data[x][y].append(node.val)
            if node.left:
                queue.append([node.left, x - 1, y + 1])
            if node.right:
                queue.append([node.right, x + 1, y + 1])
        vertical_order = []
        for x in sorted(vertical_data.keys()):
            vertical_order.append([])
            for y in sorted(vertical_data[x].keys()):
                for record in sorted(vertical_data[x][y]):
                    vertical_order[-1].append(record)
        return vertical_order