Binary Tree Vertical Order Traversal

MediumTreesbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree, return its node values grouped by vertical column, with columns listed from left to right. The root is in column 0. A left child is one column to the left of its parent (col - 1) and a right child one column to the right (col + 1). Within a column, list values from top to bottom by depth. When two nodes share both the same column and the same depth, list them in left-to-right order as they appear on that level (the order a breadth-first traversal visits them). Return a list of columns, each a list of values. An empty tree returns [].

Examples

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Column 0 holds the root 1, then 5 and 6 at depth 2, with 5 to the left of 6 on that level.
Input: root = [1,2,3,null,4,5]
Output: [[2],[1,4,5],[3]]
4 (right child of 2) and 5 (left child of 3) both land in column 0 at depth 2; 4 comes first on that level.
Input: root = []
Output: []
No nodes, no columns.

Constraints

  • 0 <= number of nodes <= 100
  • -100 <= Node.val <= 100

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems