from collections import defaultdict, deque
class Solution:
def verticalTraversal(self, root):
node_list = []
# BFS traversal with position tracking
queue = deque([(root, 0, 0)]) # node, x, y
while queue:
node, x, y = queue.popleft()
if node:
node_list.append((x, y, node.val))
queue.append((node.left, x - 1, y + 1))
queue.append((node.right, x + 1, y + 1))
# Sort by x, then y, then value
node_list.sort()
res = []
prev_x = float('-inf')
for x, y, val in node_list:
if x != prev_x:
res.append([])
prev_x = x
res[-1].append(val)
return res
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
vector<tuple<int,int,int>> nodes; // x, y, val
queue<tuple<TreeNode*, int, int>> q;
q.push({root, 0, 0});
while (!q.empty()) {
auto [node, x, y] = q.front(); q.pop();
if (node) {
nodes.emplace_back(x, y, node->val);
q.push({node->left, x-1, y+1});
q.push({node->right, x+1, y+1});
}
}
sort(nodes.begin(), nodes.end());
vector<vector<int>> res;
int prev_x = INT_MIN;
for (auto [x, y, val] : nodes) {
if (x != prev_x) {
res.push_back({});
prev_x = x;
}
res.back().push_back(val);
}
return res;
}
};
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<int[]> nodeList = new ArrayList<>(); // {x, y, val}
Queue<Object[]> queue = new LinkedList<>();
queue.offer(new Object[]{root, 0, 0});
while (!queue.isEmpty()) {
Object[] item = queue.poll();
TreeNode node = (TreeNode)item[0];
int x = (int)item[1], y = (int)item[2];
if (node != null) {
nodeList.add(new int[]{x, y, node.val});
queue.offer(new Object[]{node.left, x-1, y+1});
queue.offer(new Object[]{node.right, x+1, y+1});
}
}
nodeList.sort((a, b) -> {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
return Integer.compare(a[2], b[2]);
});
List<List<Integer>> res = new ArrayList<>();
Integer prevX = null;
for (int[] arr : nodeList) {
if (prevX == null || arr[0] != prevX) {
res.add(new ArrayList<>());
prevX = arr[0];
}
res.get(res.size()-1).add(arr[2]);
}
return res;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var verticalTraversal = function(root) {
let nodeList = [];
let queue = [[root, 0, 0]]; // node, x, y
while (queue.length) {
let [node, x, y] = queue.shift();
if (node) {
nodeList.push([x, y, node.val]);
queue.push([node.left, x - 1, y + 1]);
queue.push([node.right, x + 1, y + 1]);
}
}
nodeList.sort((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
if (a[1] !== b[1]) return a[1] - b[1];
return a[2] - b[2];
});
let res = [];
let prevX = null;
for (let [x, y, val] of nodeList) {
if (x !== prevX) {
res.push([]);
prevX = x;
}
res[res.length - 1].push(val);
}
return res;
};
Given the root of a binary tree, return its vertical order traversal as a list of lists of integers.
For each node, its vertical column index is determined by its horizontal distance from the root: the root is at column 0, left child at column -1, right child at column +1, etc.
Nodes that share the same column should be reported in order from top to bottom (from the root downward).
If two nodes are in the same row and column, they should be ordered by their value in ascending order.
To solve this problem, it's helpful to imagine the tree as being plotted on a 2D grid, with the root at position (0, 0). Each left move decreases the column index by 1, and each right move increases it by 1. The challenge is to group nodes by column, but also to sort them within each column by their row (top-to-bottom), and by value for nodes at the same position.
A brute-force approach might involve traversing the tree multiple times or using inefficient searches, but that's not scalable for large trees. Instead, we want a way to record each node's position as we traverse the tree, and then sort and group them efficiently.
The key insight is to perform a BFS or DFS while recording the (column, row, value) for each node, then sort all nodes by column, row, and value. Finally, we group nodes by their column to produce the required output.
We use a list and sorting instead of a hash map because sorting lets us easily handle the secondary ordering by row and value. BFS ensures we process nodes level by level, but DFS with position tracking also works.
Consider the following binary tree:
3
/ \
9 20
/ \
15 7
Step 1: Traverse and record positions:
Step 2: List of nodes: [ (0,0,3), (-1,1,9), (1,1,20), (0,2,15), (2,2,7) ]
Step 3: Sort by column, then row, then value:
Step 4: Grouped result: [ [9], [3,15], [20], [7] ]
The vertical order traversal problem is elegantly solved by associating each node with its (column, row) coordinates and value, then sorting all nodes by these criteria. This approach guarantees the required ordering and grouping, and is efficient in both time and space. The main insight is to treat the tree as a 2D grid, record positions during traversal, and use sorting to finalize the output.