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 coordinate.  Every report will have a list of values of nodes.
 
Example 1:


Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).


Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

 

Note:

The tree will have between 1 and 1000 nodes.
Each node's value will be between 0 and 1000.

Difficulty: interview

Starter code:

# 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:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        

Solutions:
# 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
from collections import deque

class Solution:
    def bfs(self, root, col_table):
        min_col = 0
        max_col = 0
        queue = deque([(root, 0, 0)])
        
        while queue:
            node, col, row = queue.popleft()
            col_value = col_table.get(col, [])
            col_value.append((row, node.val))
            col_table[col] = col_value
            min_col = min(min_col, col)
            max_col = max(max_col, col)
            if node.left:
                queue.append((node.left, col - 1, row + 1))
            if node.right:
                queue.append((node.right, col + 1, row + 1))
        return min_col, max_col
                
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        col_table = dict()
        min_col, max_col = self.bfs(root, col_table)
        
        res = []
        for col_idx in range(min_col, max_col + 1):
            col_res = []
            col = sorted(col_table[col_idx])
            for i in range(len(col)):
                col_res.append(col[i][1])
            res.append(col_res)
        return res

# 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:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        nMap = collections.defaultdict(list)
        queue = collections.deque([(root,0)])
        xMin, xMax = 0, 0
        while queue:
            tmp = collections.defaultdict(list)
            for i in range(len(queue)):
                node, nX = queue.popleft()
                tmp[nX].append(node.val)
                if node.left:
                    queue.append((node.left,nX-1))
                    xMin = min(xMin,nX-1)
                if node.right:
                    queue.append((node.right,nX+1))
                    xMax = max(xMax,nX+1)
            for i in tmp:
                nMap[i] += sorted(tmp[i])
        traversalLst = []
        return [nMap[i] for i in range(xMin,xMax+1)]

# 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:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        XYAndNode = namedtuple('XYAndNode', ('x', 'y', 'node'))

        q = deque([XYAndNode(0, 0, root)])
        group_by_x = defaultdict(list)
        min_x = max_x = 0
        
        while q:
            x, y, node = q.popleft()
            group_by_x[x].append((y, node.val))
            min_x = min(min_x, x)
            max_x = max(max_x, x)
            
            if node.left:
                q.append(XYAndNode(x - 1, y + 1, node.left))
            if node.right:
                q.append(XYAndNode(x + 1, y + 1, node.right))

        output = []
        for x in range(min_x, max_x + 1):
            column = [i[1] for i in sorted(group_by_x[x])]
            output.append(column)
        
        return output


# 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:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []

        columnTable = 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
            ret.append([val for row, val in sorted(columnTable[col])])

        return ret

class Solution(object):
    def verticalTraversal(self, root):
        colTable = defaultdict(list)
        minCol, maxCol = 0, 0
        q = [(root, 0, 0)]
        
        while q:
            node, x, y = q.pop()
            if x < minCol: minCol = x
            if x > maxCol: maxCol = x
            colTable[x].append((-y, node.val))
            if node.left: q.append((node.left, x-1, y-1))
            if node.right: q.append((node.right, x+1, y-1))
            
        return [[x[1] for x in sorted(colTable[col])] 
                      for col in range(minCol, maxCol+1)]        


# 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
from collections import defaultdict
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        self.dictionary = defaultdict()
        
        def dfs(node, x, y):
            if not node:
                return None
            if x not in self.dictionary:
                self.dictionary[x] = defaultdict(list)
            self.dictionary[x][y].append(node.val)
            dfs(node.left, x - 1, y - 1)
            
            dfs(node.right, x + 1, y - 1)
        
        dfs(root, 0, 0)
        ans = []
        for k in sorted(self.dictionary.keys()):
            tmp = []
            for l in sorted(self.dictionary[k].keys(), key=lambda y: -y):
                tmp += sorted(self.dictionary[k][l])
            
            ans.append(tmp)
        return ans

# 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
from collections import deque
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        q = deque()
        q.append((root, 0, 0))
        res_l = []
        res_r = []
        while q:
            node, x, y = q.popleft()
            if node.left: q.append((node.left, x - 1, y + 1))
            if node.right: q.append((node.right, x + 1, y + 1))
            if x >= 0:
                if x == len(res_r): res_r.append([])
                res_r[x].append((y, node.val))
            else:
                x = - x - 1
                if x == len(res_l): res_l.append([])
                res_l[x].append((y, node.val))
        res = []
        for line in res_l[::-1] + res_r:
            res.append([val for _, val in sorted(line)])
        return res
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
\"\"\"
        if not root:
            return []
        nodeset = []
        queue = deque()
        queue.append((root, 0, 0))
        while queue:
            node, x, y = queue.popleft()
            nodeset.append((x, y, node.val))            
            if node.left:
                queue.append((node.left, x-1, y+1))
            if node.right:
                queue.append((node.right, x+1, y+1))
                
        nodeset = sorted(nodeset)
        res = {}
        for (x, y, val) in nodeset:
            if x not in res:
                res[x] = []
            res[x].append(val)
        return res.values()
\"\"\"

# 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
from collections import deque
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:

        if not root: return []
        q = deque()
        q.append((root, 0, 0))
        nodeset = []
        while q:
            node, x, y = q.popleft()
            nodeset.append((x, y, node.val))
            if node.left: q.append((node.left, x - 1, y + 1))
            if node.right: q.append((node.right, x + 1, y + 1))
        res = []
        nodeset.sort()
        x = nodeset[0][0] - 1
        for node in nodeset:
            if node[0] > x: 
                res.append([])
                x = node[0]
            res[-1].append(node[-1])
        return res
        
        
      
        
        
        
        
        
\"\"\"
        if not root: return []
        q = deque()
        q.append((root, 0, 0))
        res_l = []
        res_r = []
        while q:
            node, x, y = q.popleft()
            if node.left: q.append((node.left, x - 1, y + 1))
            if node.right: q.append((node.right, x + 1, y + 1))
            if x >= 0:
                if x == len(res_r): res_r.append([])
                res_r[x].append((y, node.val))
            else:
                x = - x - 1
                if x == len(res_l): res_l.append([])
                res_l[x].append((y, node.val))
        res = []
        for line in res_l[::-1] + res_r:
            res.append([val for _, val in sorted(line)])
        return res
\"\"\"        
        
        
        
        
        
        
        
\"\"\"
        if not root:
            return []
        nodeset = []
        queue = deque()
        queue.append((root, 0, 0))
        while queue:
            node, x, y = queue.popleft()
            nodeset.append((x, y, node.val))            
            if node.left:
                queue.append((node.left, x-1, y+1))
            if node.right:
                queue.append((node.right, x+1, y+1))
                
        nodeset = sorted(nodeset)
        res = {}
        for (x, y, val) in nodeset:
            if x not in res:
                res[x] = []
            res[x].append(val)
        return res.values()
\"\"\"

# 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:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        res = []
        frontier = [(root, 0)]
        h = defaultdict(list)
        while frontier:
            next = []
            for u, x in frontier:
                h[x].append(u.val)
                if u.left: next.append((u.left, x-1)) 
                if u.right: next.append((u.right, x+1))
                next.sort(key = lambda x: (x[1], x[0].val))
            frontier = next
        for k in sorted(h):
            res.append(h[k])
        return res

# 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:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        from queue import Queue
        Q = Queue()
        dic = {}
        horizontal_distance = 0
        level = 1
        Q.put([root, horizontal_distance, level])
        
        dic[horizontal_distance] = dic.get(horizontal_distance, [])+[[root.val, level]]
        
        while not Q.empty():
            p = Q.get()
            currentRoot = p[0]
            currentHD = p[1]
            currentLevel = p[2]
            
            if currentRoot.left:
                Q.put([currentRoot.left, currentHD-1, currentLevel+1])
                dic.setdefault(currentHD-1, []).append([currentRoot.left.val, currentLevel+1])
            if currentRoot.right:
                Q.put([currentRoot.right, currentHD+1, currentLevel+1])
                dic.setdefault(currentHD+1, []).append([currentRoot.right.val, currentLevel+1])
        
        del currentRoot, currentHD, currentLevel, p, Q
        templist = []
        
        from operator import itemgetter
  
        for key in sorted(dic.keys()):
            templist.append(i[0] for i in sorted(dic[key], key = itemgetter(1,0)))
        
        
        return templist

            
            
        
       
         
        
            
        

            
        
        
        
            
            # templist.append(sorted(dic[key]))
            
        


# 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:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        hmap = defaultdict(list)
        x_min, x_max = 0, 0
        queue = deque()
        report = list()
        if root:
            queue.append((root, 0, 1))
        else:
            return report
        
        while queue:
            root, x, y = queue.popleft()
            
            x_min = min(x, x_min)
            x_max = max(x, x_max)
            while y > len(hmap[x]):
                hmap[x].append([])
            hmap[x][-1].append(root.val)
                
            if root.left:
                queue.append((root.left, x - 1, y + 1))
            if root.right:
                queue.append((root.right, x + 1, y + 1))
                
        print(hmap) 
        print(x_min, x_max)
        for i in range(x_min, x_max + 1):
            report.append([])
            for l in hmap[i]:
                print(l)
                print(report)
                if l:
                    l.sort()
                    report[-1].extend(l)
        return report