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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Graph traversal

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:
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


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)]


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


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))
		BFS(root)
		ret = []
		for col in range(min_column, max_column + 1):
			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)]


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


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


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


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