• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
if (!root)
return {};

vector<int> range(2);
getRange(root, range, 0);  // get the leftmost and rightmost x index

vector<vector<int>> ans(range[1] - range[0] + 1);
queue<pair<TreeNode*, int>> q{{{root, -range[0]}}};  // (TreeNode, x)

while (!q.empty()) {
const auto [node, x] = q.front();
q.pop();
ans[x].push_back(node->val);
if (node->left)
q.emplace(node->left, x - 1);
if (node->right)
q.emplace(node->right, x + 1);
}

return ans;
}

private:
void getRange(TreeNode* root, vector<int>& range, int x) {
if (!root)
return;

range[0] = min(range[0], x);
range[1] = max(range[1], x);

getRange(root->left, range, x - 1);
getRange(root->right, range, x + 1);
}
};
``````

## JAVA

``````class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
if (root == null)
return new ArrayList<>();

List<List<Integer>> ans = new ArrayList<>();
Queue<Pair<TreeNode, Integer>> q = new ArrayDeque<>(); // (TreeNode, x)
int[] range = new int[2];
getRange(root, range, 0); // get the leftmost and rightmost x index

for (int i = range[0]; i <= range[1]; ++i)

q.offer(new Pair<>(root, -range[0]));

while (!q.isEmpty()) {
final TreeNode node = q.peek().getKey();
final int x = q.poll().getValue();
if (node.left != null)
q.offer(new Pair<>(node.left, x - 1));
if (node.right != null)
q.offer(new Pair<>(node.right, x + 1));
}

return ans;
}

private void getRange(TreeNode root, int[] range, int x) {
if (root == null)
return;

range[0] = Math.min(range[0], x);
range[1] = Math.max(range[1], x);

getRange(root.left, range, x - 1);
getRange(root.right, range, x + 1);
}
}
``````

## Python

``````class Solution:
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []

range_ = [0] * 2

def getRange(root: Optional[TreeNode], x: int) -> None:
if not root:
return

range_[0] = min(range_[0], x)
range_[1] = max(range_[1], x)

getRange(root.left, x - 1)
getRange(root.right, x + 1)

getRange(root, 0)  # get the leftmost and rightmost x index

ans = [[] for _ in range(range_[1] - range_[0] + 1)]
q = deque([(root, -range_[0])])  # (TreeNode, x)

while q:
node, x = q.popleft()
ans[x].append(node.val)
if node.left:
q.append((node.left, x - 1))
if node.right:
q.append((node.right, x + 1))

return ans
``````