Vertical Order Traversal of a Binary Tree
Hard · Trees · about 25 minutes
Asked at Meta, Amazon, Google, Microsoft, Uber, Salesforce, HubSpot, SAP.
Place the root of a binary tree at (row 0, col 0); a node at (r, c) has its left child at (r + 1, c - 1) and its right child at (r + 1, c + 1). Return the vertical order traversal: one list per column from the leftmost to the rightmost. Within a column, order nodes by row (top to bottom), and nodes in the same row and column by value.