How should I practice Vertical Order Traversal of a Binary Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Vertical Order Traversal of a Binary Tree associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Vertical Order Traversal of a Binary Tree

Learn this problem

● Medium

AmazonNEW GRADONSITE INTERVIEW

See Amazon hiring insights

Problem statement

You are given a binary tree serialized as a level-order array levelOrder. Each non-null token is a signed decimal integer, and the token "null" denotes a missing child.

Place the root at row 0, column 0. For a node at row r, column c:

Its left child is at row r + 1, column c - 1.
Its right child is at row r + 1, column c + 1.

Return the node values grouped by column from the smallest column to the largest. Within one column, order nodes by increasing row. When multiple nodes share the same row and column, preserve their breadth-first left-to-right encounter order; do not sort them by value.

If the tree is empty, return an empty list.

Function

verticalOrder(levelOrder: String[]) → List<List<Integer>>

Examples

Example 1

levelOrder = ["3","9","20","null","null","15","7"]return = [[9],[3,15],[20],[7]]

The columns from left to right are -1, 0, 1, and 2.

Example 2

levelOrder = ["1","2","3","4","6","5","7"]return = [[4],[2],[1,6,5],[3],[7]]

Nodes 6 and 5 share row 2 and column 0. Breadth-first left-to-right encounter order places 6 before 5.

Example 3

levelOrder = []return = []

An empty tree has no columns.

Constraints

0 <= non-null node count <= 10^5.
Every non-null token represents a signed 32-bit integer.
levelOrder is a valid level-order serialization using "null" markers.