'''
keys: we have to use two-dimension coordinates to locat a node since the 
final result should be from left col to right col, then from top to bottom
One-dimension works with more tricks.
Solutions:
Similar: 
T:
S:
'''
from typing import List
import collections
from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
        
class Solution:
    # partial sorting + DFS, using 
    # T: O(Nlog(N/k)), where  k is the width of the tree, 
    # i.e.  k is also the number of columns in the result.
    # S: O(N) 

    # BFS iteration with 1-d coordinates
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        col2vals = collections.defaultdict(list)
        queue = [(root, 0)] 
        while queue:
            new_queue = []
            tmp_col2vals = collections.defaultdict(list)
            for node, col_idx in queue:
                tmp_col2vals[col_idx].append(node.val)
                if node.left:
                    new_queue += [(node.left, col_idx-1)]
                if node.right:
                    new_queue += [(node.right, col_idx+1)]
            for col_idx in tmp_col2vals:
                col2vals[col_idx].extend(sorted(tmp_col2vals[col_idx]))
            queue = new_queue
        # when using sorted on hashmap, it returns a list of sorted keys
        return [col2vals[col] for col in sorted(col2vals)]


    # partial sorting + DFS recursion
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []

        columnTable = collections.defaultdict(list)
        min_column = max_column = 0

        def DFS(node, row, column):
            if node is not None:
                nonlocal min_column, max_column
                columnTable[column].append((row, node.val))
                min_column = min(min_column, column)
                max_column = max(max_column, column)

                # preorder DFS
                DFS(node.left, row + 1, column - 1)
                DFS(node.right, row + 1, column + 1)

        # step 1). DFS traversal
        DFS(root, 0, 0)

        # step 2). extract the values from the columnTable
        ret = []
        for col in range(min_column, max_column + 1):
            # sort first by 'row', then by 'value', in ascending order
            ret.append([val for row, val in sorted(columnTable[col])])

        return ret
    
    # partial sorting + BFS recursion
    def verticalTraversal1(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []

        columnTable = collections.defaultdict(list)
        min_column = max_column = 0

        def BFS(root):
            nonlocal min_column, max_column
            queue = deque([(root, 0, 0)])

            while queue:
                node, row, column = queue.popleft()

                if node is not None:
                    columnTable[column].append((row, node.val))
                    min_column = min(min_column, column)
                    max_column = max(max_column, column)

                    queue.append((node.left, row + 1, column - 1))
                    queue.append((node.right, row + 1, column + 1))

        # step 1). BFS traversal
        BFS(root)

        # step 2). extract the values from the columnTable
        ret = []
        for col in range(min_column, max_column + 1):
            # sort first by 'row', then by 'value', in ascending order
            # sorted also works on list of tuples
            ret.append([val for row, val in sorted(columnTable[col])])

        return ret
    
    # DFS. 
    # T: O(NlogN), O(N) for traversal and O(NlogN) for sorting
    # S: O(N);  At any given moment, the queue contains no 
    # more than two levels of nodes in the tree.
    def verticalTraversal1(self, root: TreeNode) -> List[List[int]]:
        node_list = []

        def DFS(node, row, column):
            if node is not None:
                node_list.append((column, row, node.val))
                # preorder DFS
                DFS(node.left, row + 1, column - 1)
                DFS(node.right, row + 1, column + 1)

        # step 1). construct the node list, with the coordinates
        DFS(root, 0, 0)
        node_list.sort() # sort by x
        
        res = {} # or OrderedDict()
        for x, y, val in node_list:
            if x in res:
                res[x].append(val)
            else:
                res[x] = [val]
        return res.values()


    def verticalTraversal0(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res
        
        queue = deque([(root, 0, 0)])
        while queue:
            node, c, r = queue.popleft()
            if node:
                res.append([c , r, node.val])
                if node.left:
                    queue.append([node.left, c-1, r+1])
                if node.right:
                    queue.append([node.right, c+1, r+1])
        
        # print (res)
        res = sorted(res)
        # print (res)
        ret = OrderedDict()
        for c, r, val in res:
            if c not in ret:
                ret[c] = [val]
            else:
                ret[c].append(val)
        return ret.values()

    
    # BFS
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        node_list = []
        
        def bfs(root):
            queue = deque([(root, 0, 0)]) # 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))

        
        bfs(root)
        node_list.sort() # sort by x
        
        res = {} # regualr dict will also work
        for x, y, val in node_list:
            if x in res:
                res[x].append(val)
            else:
                res[x] = [val]
        return res.values()


    
            
        
            
            
        