Traversal

Vertical order traversal of a Binary Tree

1. custom sorting

2. level order traversal

3. Map<Integer, List<Node>> map. key is y, val is list of node

4. Node is sort by x in decreasing order, if same x, then sort by val in increasing order

5. keep track of minY and maxY

class Solution {
    public class Node implements Comparable<Node>{
        int x;
        int y;
        TreeNode node;
        public Node(int x, int y, TreeNode node) {
            this.x = x;
            this.y = y;
            this.node = node;
        }
        
        @Override
        public int compareTo(Node that) {
            if (this.x == that.x) {
                return this.node.val - that.node.val;
            }
            return that.x - this.x;
        }
    }
    /*
    Map<Integer, List<Node>> map; key is y, val is list of node
    node is sort by x in decreasing order, if same x, then sort by val in increasing order
    keep track of minY and maxY
    
    */
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Map<Integer, List<Node>> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, root.val, root));
        int minKey = 0, maxKey = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                int x = cur.x;
                int y = cur.y;
                minKey = Math.min(minKey, y);
                maxKey = Math.max(maxKey, y);
                if (!map.containsKey(y)) {
                    map.put(y, new ArrayList<>());
                }
                List<Node> value = map.get(y);
                value.add(cur);
                if (cur.node.left != null) {
                    queue.offer(new Node(x - 1, y - 1, cur.node.left));
                }
                if (cur.node.right != null) {
                    queue.offer(new Node(x - 1, y + 1, cur.node.right));
                }
            }
        }
        
        for (int key = minKey; key <= maxKey; key++) {
            List<Node> nodes = map.get(key);
            if (nodes == null) continue;
            Collections.sort(nodes);
            List<Integer> list = new ArrayList<>();
            for (Node node : nodes) {
                list.add(node.node.val);
            }
            res.add(new ArrayList<>(list));
        }
        return res;
    }
    
}