Meta Interview Problem #2 · Vertical Order Traversal of a Binary Tree

Problem Statement (English original)
Assume a binary-tree node:

class Node {
  int val;
  Node left, right;
}

Given the root of a binary tree, output the node values in vertical order (column order) from leftmost column to rightmost column.
Within each column, list nodes top-to-bottom in the order they are encountered by a standard BFS (or by row index if you compute coordinates).

Illustrative example (matching the screenshot tree):

        6
       / \
      3   4
     / \   \
    5   1   0
     \ /   /
      2 8 7
     / \
    9   7   (shape illustrative)

Expected vertical-order output:

[5, 9, 3, 2, 6, 1, 7, 4, 8, 0]

(Columns from left to right:
-2: [5]
-1: [9, 3, 2]
0: [6, 1, 7]
+1: [4, 8]
+2: [0])

Brief Summary / Idea
Do level-order BFS tagging each node with a column index (root 0; left −1; right +1). Append values to a map col → list, track minCol/maxCol, then concatenate columns left→right. Complexity O(n) time, O(n) space.

The VOprep team has long accompanied candidates through various major company OAs and VOs, including OpenAI, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Stripe or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.