Vertical Order Traversal

Traverse a binary tree column by column, grouping nodes by column and row.

binary-tree bfs dictionary sorting

Given the root of a binary tree, return the vertical order traversal of its node values. The root is at column 0. A left child is at column -1, a right child at column +1. Nodes at the same column are grouped together, with columns sorted from smallest to largest. Within a column, nodes are ordered by row (root row 0, children row+1). If two nodes share the same column and row, order them by value ascending. The tree is provided as a nested dictionary structure for testing purposes. For example, a node is represented as {'val': 3, 'left': ..., 'right': ...}. Implement the function `vertical_order(root) -> List[List[int]]` that accepts such a node (or None) and returns a list of lists of integers as described.

Constraints

- The number of nodes in the tree is in the range [0, 1000].
- Node values are integers from -1000 to 1000.
- The tree may be empty (root is None).
- Expected time complexity O(N log N) in the worst case, where N is the number of nodes.

Example

>>> tree = {'val': 3, 'left': {'val': 9, 'left': None, 'right': None}, 'right': {'val': 20, 'left': {'val': 15, 'left': None, 'right': None}, 'right': {'val': 7, 'left': None, 'right': None}}}
>>> vertical_order(tree)
[[9], [3, 15], [20], [7]]
>>> vertical_order(None)
[]

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use BFS to traverse level by level, tracking column index for each node.

Store nodes in a dictionary mapping column -> list of (row, value).

Sort columns, then within each column sort by (row, value) and extract values.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.