Vertical Order Traversal of a Binary Tree

HardTreesbfs

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

Place the root of a binary tree at row 0, column 0. A node at (row, col) has its left child at (row + 1, col - 1) and its right child at (row + 1, col + 1). Return the **vertical order traversal**: one list per column, with columns ordered from the leftmost to the rightmost. Inside a column, list nodes from top to bottom by row. When several nodes share the same row **and** column, list them in ascending order of value (duplicates allowed). The output is fully determined by these rules, so graders compare it exactly. Collecting (col, row, val) triples and sorting them gives O(n log n) time.

Examples

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Column -1 holds 9; column 0 holds 3 (row 0) then 15 (row 2); column 1 holds 20; column 2 holds 7.
Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
In column 0, 5 and 6 share row 2, so they are ordered by value after 1.
Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Swapping 5 and 6 in the tree does not change the output, because ties sort by value.

Constraints

  • 1 <= number of nodes <= 1000
  • 0 <= Node.val <= 1000
  • Values may repeat; nodes sharing a row and column are ordered by value

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