Given a binary tree, return the vertical order traversal of its nodes values. For each node at position (X, Y), its left and right children respectively will be at positions (X - 1, Y - 1) and (X + 1, Y - 1). Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates). If two nodes have the same position, then the value of the node that is reported first is the value that is smaller. Return an list of non-empty reports in order of X coordinates. Every report will have a list of values of nodes.

// Use HashMap to store X // Use TreeMap to store Y // If some nodes have same (X, Y), they are in the Priority Queue. Map<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = newHashMap<>(); intminX=0, maxX = 0;

public List<List<Integer>> verticalTraversal(TreeNode root) { buildMap(root, 0, 0); List<List<Integer>> result = newArrayList<>(); // For each X for (intx= minX; x <= maxX; ++x) { List<Integer> level = newArrayList<>(); // For each Y (in order bc TreeMap) for (int y : map.get(x).keySet()) { PriorityQueue<Integer> pq = map.get(x).get(y); while (pq.size () > 0) { level.add(pq.poll()); } } result.add(level); } return result; }

privatevoidbuildMap(TreeNode node, int x, int y) { // traverse each node O(N) if (node == null) { return; } // record min & max minX = Math.min(minX, x); maxX = Math.max(maxX, x); if (map.get(x) == null) { // Init TreeMap map.put(x, newTreeMap<Integer, PriorityQueue<Integer>>()); } if (map.get(x).get(y) == null) { // Init PQ map.get(x).put(y, newPriorityQueue<Integer>()); // O(log(h)) } PriorityQueue<Integer> pq = map.get(x).get(y); pq.add(node.val); // log // recursive helper(node.left, x - 1, y + 1); helper(node.right, x + 1, y + 1); }

Time: $O(N\log{N})$ for each node the runtime could be upper bounded by $O(\log{N})$. Space: $O(N)$