Approach
Breadth-first search
For Binary Tree Vertical Order Traversal, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 38 lines of C++ from the credited upstream file 314.cpp.
- The implementation visibly relies on sequence storage, work queue.
- 1 loop block detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution {2 public:3 vector<vector<int>> verticalOrder(TreeNode* root) {4 if (root == nullptr)5 return {};6 7 vector<int> range(2);8 getRange(root, range, 0); 9 10 vector<vector<int>> ans(range[1] - range[0] + 1);11 queue<pair<TreeNode*, int>> q{{{root, -range[0]}}}; 12 13 while (!q.empty()) {14 const auto [node, x] = q.front();15 q.pop();16 ans[x].push_back(node->val);17 if (node->left)18 q.emplace(node->left, x - 1);19 if (node->right)20 q.emplace(node->right, x + 1);21 }22 23 return ans;24 }25 26 private:27 void getRange(TreeNode* root, vector<int>& range, int x) {28 if (root == nullptr)29 return;30 31 range[0] = min(range[0], x);32 range[1] = max(range[1], x);33 34 getRange(root->left, range, x - 1);35 getRange(root->right, range, x + 1);36 }37};38