Skip to main content

314. Binary Tree Vertical Order Traversal

mediumAsked at Airbnb

Return the values of a binary tree visited in vertical order, top to bottom, left to right. Airbnb asks this to test BFS with column tracking and how you order ties (left before right at the same row).

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

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb onsite reports consistently list this as a recurring tree medium.
  • Blind (2025-12)— Frequently mentioned in Airbnb new-grad and L4 interview reports.

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 (wrong ordering)

DFS recording (col, node). Sort by col, then by depth. Fails ties: at the same row, left-child of an earlier visit can appear right of a later visit.

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

Tradeoff: Stable-sorting on row preserves left-before-right ONLY if you DFS left first AND the sort is stable. JS .sort is now stable, but interviewers want the BFS framing because it's robust without that assumption.

2. BFS with column index (optimal)

BFS the tree, recording each node's column. Group by column; iteration order is the row order so left-before-right falls out naturally.

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

Tradeoff: BFS guarantees row order. Tracking min/max columns avoids sorting keys at the end. Clean and naturally left-to-right within a row.

Airbnb-specific tips

Airbnb interviewers love this problem because the BFS framing is elegant. Say: 'I'll BFS the tree carrying a column index — left child is col-1, right is col+1. BFS gives the row order naturally; grouping by column gives the output.' That description alone is half the answer.

Common mistakes

  • DFS with unstable sort — at the same row, left-before-right is not guaranteed unless the sort is stable.
  • Returning an object instead of an array sorted by column.
  • Forgetting empty tree -> [].

Follow-up questions

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

  • Vertical Order II (LC 987) — same problem but ties broken by value, not BFS order.
  • Bottom view / top view of a binary tree — same column tracking, different output.
  • What if the tree had millions of nodes? (Linear time still works; the Map grows with width.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

BFS or DFS — which does Airbnb prefer?

BFS, because the row-order guarantee falls out of the traversal. DFS can produce the same answer with a stable sort, but BFS is the cleaner interview narration.

Why track minCol and maxCol?

To avoid sorting the column keys at the end. Tree depth bounds the columns: at most n columns total, between -depth and +depth from root.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →