Skip to main content

314. Binary Tree Vertical Order Traversal

mediumAsked at Meta

Given a binary tree, return its vertical order traversal of node values. Meta asks this to test whether you reach for BFS with column tracking (so left children get column - 1 and right children get column + 1).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as a recurring 'Meta favorite' tree problem.
  • Blind (2025-11)— Recurring Meta interview problem; the tie-breaking rule (top-to-bottom, left-to-right) is the trap.

Problem

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right.

Constraints

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

Examples

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
[[9],[3,15],[20],[7]]

Example 2

Input
root = [3,9,8,4,0,1,7]
Output
[[4],[9],[3,0,1],[8],[7]]

Approaches

1. DFS with column tracking + sort at end

DFS, recording (row, col, val) for each node. Group by col, sort within column by (row, insertion order).

Time
O(n log n)
Space
O(n)
function verticalOrderDFS(root) {
  if (!root) return [];
  const cols = new Map();
  function dfs(node, row, col) {
    if (!node) return;
    if (!cols.has(col)) cols.set(col, []);
    cols.get(col).push([row, node.val]);
    dfs(node.left, row + 1, col - 1);
    dfs(node.right, row + 1, col + 1);
  }
  dfs(root, 0, 0);
  const sortedCols = [...cols.keys()].sort((a, b) => a - b);
  return sortedCols.map(c => cols.get(c).sort((a, b) => a[0] - b[0]).map(x => x[1]));
}

Tradeoff: Works but sorts at the end — wastes work. The BFS version naturally produces correct ordering.

2. BFS by column (optimal)

BFS the tree, tracking column index per node. Bucket values by column. BFS naturally orders top-to-bottom; queue order handles left-to-right within a row.

Time
O(n)
Space
O(n)
function verticalOrder(root) {
  if (!root) return [];
  const cols = new Map();
  const q = [[root, 0]];
  let minCol = 0, maxCol = 0;
  while (q.length) {
    const [node, col] = q.shift();
    if (!cols.has(col)) cols.set(col, []);
    cols.get(col).push(node.val);
    minCol = Math.min(minCol, col);
    maxCol = Math.max(maxCol, col);
    if (node.left) q.push([node.left, col - 1]);
    if (node.right) q.push([node.right, col + 1]);
  }
  const result = [];
  for (let c = minCol; c <= maxCol; c++) result.push(cols.get(c));
  return result;
}

Tradeoff: BFS guarantees top-to-bottom (row by row) and within-row left-to-right by queue order. No final sort needed. Tracking minCol/maxCol lets us output columns in order without needing to sort keys.

Meta-specific tips

Meta interviewers specifically test whether you understand the tie-breaking rule: same row + same column means left-to-right by tree position. BFS naturally produces this order because it visits the level-order traversal. DFS doesn't without an extra sort. State out loud: 'BFS is the right tool because it gives me row-by-row ordering for free.'

Common mistakes

  • Using DFS without an explicit row tracking — DFS preorder visits left before right within a level but doesn't give true level-by-level ordering, so 'same column, top-down' is broken.
  • Trying to use a sorted map for columns — works but adds log factor.
  • Forgetting to handle the empty tree (return []).

Follow-up questions

An interviewer at Meta may pivot to one of these next:

  • Binary Tree Vertical Order Traversal II (LC 987): within same row+col, sort by VALUE not insertion order.
  • What if you needed the bottom view of the tree?
  • What if the tree could have parent pointers?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why BFS and not DFS?

BFS visits the tree row-by-row, which is exactly the tie-breaking order required: same-column same-row nodes appear in left-to-right order via the BFS queue.

What's the most-common Meta trap here?

Using DFS and then trying to sort the buckets. The sort works but you've shown the interviewer you didn't recognize BFS as the natural fit, which is a missed signal.

Practice these live with InterviewChamp.AI

Drill Binary Tree Vertical Order Traversal and other Meta interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →