Order Binary-Tree Nodes by Column, Depth and Value
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Place the root at(row0,column0). A left child moves to(row+1,column-1), and a right child to(row+1,column+1). Return columns from left to right. Within a column order nodes from top to bottom; nodes sharing both row and column are ordered by value.
```cpp
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root);
};
```
### Examples
**Example 1:**
```text
Input: root = [8,4,12,null,9,3]
Output: [[4],[8,3,9],[12]]
Explanation: Values9 and3 both occur at(row2,column0), so3 precedes9 after root8.
```
**Example 2:**
```text
Input: root = [2,1,3]
Output: [[1],[2],[3]]
Explanation: The three nodes occupy columns-1,0,and1 respectively.
```
### Constraints
- The tree contains1 to1000 nodes.
- `0 <= Node.val <= 1000`.
### Contract considerations
The result order is fully specified, unlike arbitrary-order tree-node collection tasks.
```hint Read the boundary condition
Write the three ordering keys explicitly before choosing a traversal or data structure.
```
### Boundary reminders
The result order is fully specified, unlike arbitrary-order tree-node collection tasks.
Overview: Order Binary-Tree Nodes by Column, Depth and Value. Place the root at(row0,column0). A left child moves to(row+1,column-1), and a right child to(row+1,column+1).