Leet Code 987. Vertical Order Traversal of a Binary Tree — Explained Python3 Solution

Photo by Berat Çıldır on Unsplash

Problem Description

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: [1,3,5,null,null,7,9,null,null, 11,13]
Output: [[3],[1,7],[5,11],[9],[13]]

Solution

As the graph for above example shows, it is actually asking for one thing: output all Y values (from smallest to largest) by X value from smallest to largest.

Since Y axis’s direction is downward, it will be natural to visit the tree to top to down layer by layer, taking notes of nodes’ values in a manner of {x: node’s value} (for example, for the second layer, I will have {-1:[3], 1:[5]} meaning for x = -1 in this layer, there is a node with value [3]). One tricky thing is that if in a specific layer, if there are 2 nodes in the same X values, a smaller value is required to be ahead of a larger one). While visiting current layer nodes, I can in the same time storing each node’s left and right children nodes to prepare for next layer’s visit.

Finally, when I finish visiting all layers, I should have a dictionary like {x0 : [[y1,y2],[y3]], x2:[[y2]],x1:[[y1,y4],[y5]]}, since the required output asks for left to right order, I will sort the keys (x0,x2,x1) and then add each key’s value to return result.

The whole solution is pretty straightforward. But it actually requires a clear understanding of what I’m doing especially in the middle of programming and appropriate use of multiple data structures. Therefore, it can be very error prone. For myself, I actually forgot to reset nodesInNextLayer to an empty list after finish visiting a layer and it took me like 10 minutes to figure out that. For those details, I will cover them inline in below codes.

	# 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
	'''
	Detailed explanation is available at
	https://medium.com/@edward.zhou/leet-code-987-vertical-order-traversal-of-a-binary-tree-explained-python3-solution-20f2f6e0118a
	Runtime: 28 ms, faster than 94.59% of Python3 online submissions for Vertical Order Traversal of a Binary Tree.
	Memory Usage: 14.2 MB, less than 17.27% of Python3 online submissions for Vertical Order Traversal of a Binary Tree.
	'''
	class Solution:
	def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
	'''
	I can visit the tree layer by layer to get each node's coordinates
	and then put them in a dictionary whose keys are X while values are
	node.val.
	2 things to note:
	1, when handling the same layer, for nodes in same position, I need to
	put smaller value one ahead of larger one
	2, when the visit finishes, I need to sort keys so that reported results
	are from left to right
	'''
	if not root:
	return []
	d = {}
	nodesInCurrentLayer = [(root, 0)] #each node in layer is represented by a tuple of (node, X value)
	nodesInNextLayer = []
	while(len(nodesInCurrentLayer) > 0): #use BFS to navigate layer by layer
	tempDict = {}
	while(len(nodesInCurrentLayer) > 0):
	nodeWithX = nodesInCurrentLayer.pop(0)
	#add childrens of next layer
	if nodeWithX[0].left:
	nodesInNextLayer.append((nodeWithX[0].left, nodeWithX[1] - 1))
	if nodeWithX[0].right:
	nodesInNextLayer.append((nodeWithX[0].right, nodeWithX[1] + 1))
	#add node's value and X to a temp list
	if tempDict.get(nodeWithX[1]) == None:
	tempDict[nodeWithX[1]] = []
	tempDict[nodeWithX[1]].append(nodeWithX[0].val)
	#now tempDict looks like {'x1':[val1, val2],'x2':[val3, val4]}
	#need to sort each [val1, val2]., [val3, val4]
	for key in tempDict:
	if d.get(key) == None:
	d[key] = []
	d[key] += sorted(tempDict[key])
	nodesInCurrentLayer = nodesInNextLayer
	nodesInNextLayer = [] #remember to do this!
	#end of the first while
	res = []
	for x in sorted(d.keys()): #don't forget to sort keys
	res.append(d[x])
	return res

view raw lc987.py hosted with ❤ by GitHub

Time & Space Complexity

With above solution, there are 3 parts needed to take into consideration when concluding time complexity:

1. I need to visit each and every node once to gather its X/Y coordinates and for this part time complexity is O(N).
2. Within the visit of each layer, there will have some sorting occurring which can take O(MlogM) assuming average M collisions for the same (x,y). M is directly related to N so I can say this is O(NlogN).
3. Now for the third part: before I return the res where I will sort d.keys(), the more nodes the input has, normally the more X values would be so that part will take O(NlogN).

In conclusion, the sum of time complexity will be O(NlogN).

I use several dictionaries and lists but their sizes are scaling in the same level as input size (N) so total space complexity is O(N).

Python 3 knowledge points

1. Basic data structures like tuple, dictionary, list. Please refer to my Python3 cheatsheet.