# 987. Vertical Order Traversal of a Binary Tree¶

• Time: $O(n\log n/k) = O(n\log n)$, where $k = \text{width(tree)}$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: vector> verticalTraversal(TreeNode* root) { vector> ans; map>> xToSortedPairs; // {x: {(-y, val)}} dfs(root, 0, 0, xToSortedPairs); for (const auto& [_, pairs] : xToSortedPairs) { vector vals; for (const pair& pair : pairs) vals.push_back(pair.second); ans.push_back(vals); } return ans; } private: void dfs(TreeNode* root, int x, int y, map>>& xToSortedPairs) { if (root == nullptr) return; xToSortedPairs[x].emplace(y, root->val); dfs(root->left, x - 1, y + 1, xToSortedPairs); dfs(root->right, x + 1, y + 1, xToSortedPairs); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public List> verticalTraversal(TreeNode root) { List> ans = new ArrayList<>(); TreeMap> xToSortedPairs = new TreeMap<>(); // {x: {(-y, val)}} dfs(root, 0, 0, xToSortedPairs); for (List pairs : xToSortedPairs.values()) { Collections.sort( pairs, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0])); List vals = new ArrayList<>(); for (int[] pair : pairs) vals.add(pair[1]); ans.add(vals); } return ans; } private void dfs(TreeNode root, int x, int y, TreeMap> xToSortedPairs) { if (root == null) return; xToSortedPairs.putIfAbsent(x, new ArrayList<>()); xToSortedPairs.get(x).add(new int[] {y, root.val}); dfs(root.left, x - 1, y + 1, xToSortedPairs); dfs(root.right, x + 1, y + 1, xToSortedPairs); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def verticalTraversal(self, root: TreeNode | None) -> list[list[int]]: ans = [] xToNodes = collections.defaultdict(list) def dfs(node: TreeNode | None, x: int, y: int) -> None: if not node: return xToNodes[x].append((-y, node.val)) dfs(node.left, x - 1, y - 1) dfs(node.right, x + 1, y - 1) dfs(root, 0, 0) for _, nodes in sorted(xToNodes.items(), key=lambda x: x[0]): ans.append([val for _, val in sorted(nodes)]) return ans