Vertical Order Traversal of a Binary Tree

Hard·Tagstreebfsdfssortinghash-table

Problem Statement

Given the `root` of a binary tree, calculate the vertical order traversal of the binary tree. For each node at position `(row, col)`, its left and right children will be at positions `(row + 1, col - 1)` and `(row + 1, col + 1)` respectively. The root of the tree is at `(0, 0)`. The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. Return the vertical order traversal of the binary tree. Note: Assume a standard `TreeNode` class is already provided in the execution environment, containing `val`, `left`, and `right` properties.

Examples

Example 1

Input

root: [3, 9, 20, null, null, 15, 7]

Tree

Output

"[[9], [3, 15], [20], [7]]"

Why

Column -1: Only node 9 is in this column. Column 0: Nodes 3 and 15 are in this column in that order from top to bottom. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.

Example 2

Input

root: [1, 2, 3, 4, 5, 6, 7]

Tree

Output

"[[4], [2], [1, 5, 6], [3], [7]]"

Why

Column -2: Only node 4 is in this column. Column -1: Only node 2 is in this column. Column 0: Nodes 1, 5, and 6 are in this column. 1 is at the top, so it comes first. 5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6. Column 1: Only node 3 is in this column. Column 2: Only node 7 is in this column.

Constraints

•The number of nodes in the tree is in the range [1, 1000].
•0 <= Node.val <= 1000

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

You need to keep track of the vertical column and the horizontal row for every node. The root is at `(0, 0)`. Its left child is at `(1, -1)` and right child is at `(1, 1)`.

Hint 2

Traverse the tree (using BFS or DFS) and store every node in a list as a tuple: `(column, row, value)`.

Hint 3

Once you have all the nodes, sort the list! Sort primarily by `column`, secondarily by `row`, and finally by `value` to handle ties.

Hint 4

After sorting, simply group the values by their `column` to construct the final 2D array.