Binary Tree Vertical Order Traversal
Medium · Trees · about 20 minutes
Asked at Meta, Apple, Bloomberg, Amazon, Google, Optiver, Arm.
Group a binary tree's values by column. The root sits in column 0, a left child sits one column left of its parent, and a right child one column right. Return the columns from leftmost to rightmost. Inside a column, values go from the top level down, and values on the same level and column keep their left-to-right order (the order a breadth-first search meets them).