// Runtime: 3 ms, faster than 75.00% of Java online submissions for Vertical Order Traversal of a Binary Tree.
// Memory Usage: 36.5 MB, less than 100.00% of Java online submissions for Vertical Order Traversal of a Binary Tree.

import java.util.SortedMap;

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        SortedMap<Integer, SortedSet<Pair>> map = new TreeMap<>();
        traverse(root, 0, 0, map);

        List<List<Integer>> result = new LinkedList<>();
        for (SortedSet<Pair> line: map.values()) {
            List<Integer> r = new LinkedList<>();

            for (Pair p: line) r.add(p.val);

            result.add(r);
        }
        return result;
    }

    private void traverse(TreeNode root, int x, int y, SortedMap<Integer, SortedSet<Pair>> map) {
        if (root == null) return;

        if (!map.containsKey(x)) map.put(x, new TreeSet<Pair>());
        map.get(x).add(new Pair(root.val, y));

        traverse(root.left, x-1, y-1, map);
        traverse(root.right, x+1, y-1, map);
    }

    class Pair implements Comparable<Pair> {
        public int val;
        public int y;

        public Pair(int val, int y) {
            this.val = val;
            this.y = y;
        }

        public int compareTo(Pair another) {
            int yDiff = -y + another.y;
            if (yDiff != 0) return yDiff;
            else return val - another.val;
        }
    }
}