package com.freetymekiyan.algorithms.level.medium;

import com.freetymekiyan.algorithms.utils.Utils.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by
 * column).
 * <p>
 * If two nodes are in the same row and column, the order should be from left to right.
 * <p>
 * Examples:
 * <p>
 * Given binary tree [3,9,20,null,null,15,7],
 * |   3
 * |  /\
 * | /  \
 * | 9  20
 * |    /\
 * |   /  \
 * |  15   7
 * return its vertical order traversal as:
 * |[
 * |  [9],
 * |  [3,15],
 * |  [20],
 * |  [7]
 * |]
 * Given binary tree [3,9,8,4,0,1,7],
 * |     3
 * |    /\
 * |   /  \
 * |   9   8
 * |  /\  /\
 * | /  \/  \
 * | 4  01   7
 * return its vertical order traversal as:
 * |[
 * |  [4],
 * |  [9],
 * |  [3,0,1],
 * |  [8],
 * |  [7]
 * |]
 * Given binary tree [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5),
 * |     3
 * |    /\
 * |   /  \
 * |   9   8
 * |  /\  /\
 * | /  \/  \
 * | 4  01   7
 * |    /\
 * |   /  \
 * |   5   2
 * return its vertical order traversal as:
 * |[
 * |  [4],
 * |  [9,5],
 * |  [3,0,1],
 * |  [8,2],
 * |  [7]
 * |]
 * Company Tags: Google, Snapchat, Facebook
 * Tags: Hash Table
 * Similar Problems: (E) Binary Tree Level Order Traversal
 */
public class BinaryTreeVerticalOrderTraversal {

    /**
     * BFS, Hash Table.
     * Use a map to record level and relative node values.
     * Initialize level value of root as 0.
     * When accessing a left child, col value decrement by 1.
     * When accessing right, col value increment by 1.
     * Use a separate queue to store column.
     */
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> cols = new LinkedList<>();
        queue.add(root);
        cols.add(0);
        int min = 0;
        int max = 0;

        while (!queue.isEmpty()) {
            TreeNode n = queue.poll();
            int level = cols.poll();
            if (!map.containsKey(level)) {
                map.put(level, new ArrayList<>());
            }
            map.get(level).add(n.val);
            if (n.left != null) {
                queue.add(n.left);
                cols.add(level - 1);
                min = Math.min(min, level - 1);
            }
            if (n.right != null) {
                queue.add(n.right);
                cols.add(level + 1);
                max = Math.max(max, level + 1);
            }
        }

        for (int i = min; i <= max; i++) {
            res.add(map.get(i));
        }
        return res;
    }

}

@@ -128,24 +128,54 @@
 .ArrayList;%0A
+import java.util.Collections;%0A
 import java.
@@ -1822,16 +1822,17 @@
 e column
+s
 .%0A     *
@@ -1907,114 +1907,134 @@
     
-List%3CList%3CInteger%3E%3E res = new ArrayList%3C%3E();%0A        if (root == null) %7B%0A            return res;%0A        %7D
+if (root == null) %7B%0A            return Collections.emptyList();%0A        %7D%0A        List%3CList%3CInteger%3E%3E res = new ArrayList%3C%3E();
 %0A   
@@ -2085,24 +2085,66 @@
 ashMap%3C%3E();%0A
+        int min = 0;%0A        int max = 0;%0A
         Queu
@@ -2206,20 +2206,21 @@
 nteger%3E 
-cols
+level
  = new L
@@ -2271,20 +2271,21 @@
     
-cols
+level
 .add(0);
 %0A   
@@ -2284,50 +2284,8 @@
 (0);
-%0A        int min = 0;%0A        int max = 0;
 %0A%0A  
@@ -2339,16 +2339,19 @@
 eeNode n
+ode
  = queue
@@ -2379,20 +2379,22 @@
 int 
-level = cols
+curLvl = level
 .pol
@@ -2431,20 +2431,21 @@
 ainsKey(
-leve
+curLv
 l)) %7B%0A  
@@ -2466,20 +2466,21 @@
 map.put(
-leve
+curLv
 l, new A
@@ -2532,20 +2532,21 @@
 get(
-leve
+curLv
 l).add(n
 .val
@@ -2541,16 +2541,19 @@
 l).add(n
+ode
 .val);%0A 
@@ -2568,16 +2568,19 @@
    if (n
+ode
 .left !=
@@ -2615,16 +2615,19 @@
 ue.add(n
+ode
 .left);%0A
@@ -2642,29 +2642,31 @@
         
-cols.add(leve
+level.add(curLv
 l - 1);%0A
@@ -2701,20 +2701,21 @@
 in(min, 
-leve
+curLv
 l - 1);%0A
@@ -2745,16 +2745,19 @@
    if (n
+ode
 .right !
@@ -2793,16 +2793,19 @@
 ue.add(n
+ode
 .right);
@@ -2825,21 +2825,23 @@
     
-cols.add(leve
+level.add(curLv
 l + 
@@ -2880,20 +2880,21 @@
 ax(max, 
-leve
+curLv
 l + 1);%0A

update Binary Tree Vertical Order Traversal