noodleProblems/
Binary Tree Vertical Order Traversal
#133

Binary Tree Vertical Order Traversal

AlgorithmmediumHash TableTreeDepth First SearchBreadth First SearchBinary Tree

Given the root of a binary tree, return its **vertical order traversal** — the node values grouped by column, from the leftmost column to the rightmost.

Assign the root column 0; a left child is one column to the left (col - 1) and a right child one column to the right (col + 1). Within a column, list nodes **top to bottom**; when two nodes share a column *and* a row, list them **left to right** (i.e. in the order a level-order scan reaches them).

The tree is given as a level-order array where null marks a missing child: [3, 9, 20, null, null, 15, 7].

Example cases

  • classic
    in root = [3,9,20,null,null,15,7]9315207
    out [[9],[3,15],[20],[7]]
    Columns -1..2: [9], then root 3 with 15 (both at col 0), then 20, then 7.
  • with collision
    in root = [3,9,8,4,0,1,7]4903187
    out [[4],[9],[3,0,1],[8],[7]]
    Column 0 holds 3, then 0 and 1 sharing a row, left-to-right.
  • empty
    in root = []null
    out []

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Saved
root =
[3,9,20,null,null,15,7]