FastPrepVertical Order Traversal of a Binary Tree
Problems/Vertical Order Traversal of a Binary Tree

Vertical Order Traversal of a Binary Tree

Amazon logoAmazon● MediumNEW GRADONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The source reports classic binary-tree vertical traversal but omits the same-position tie rule, serialization, empty-tree behavior, and bounds. The judged core task matches the visible source at about 90%.

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.

More Amazon problems

  • Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
  • First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
See Amazon hiring insights
Saved
class Solution {
    public List<List<Integer>> verticalOrder(String[] levelOrder) {
      // write your code here
    }
}
Checking account…