Case study: vertical traverse of binary tree algorithm

Feb. 16, 2020

Introduction

It was my 10:00 AM mock interview. I wrote down the algorithm and then asked the interviewee worked on the algorithm, and I would go back to home in 10 minutes. I like to document my mock interview and the interviewee's super good performance.

Case study

I will add more detail later.

	#
	# Your previous Plain Text content is preserved below:
	#
	# Welcome to your interviewing.io interview.
	#
	# Once you and your partner have joined, a voice call will start automatically.
	#
	# Use the language dropdown near the top right to select the language you would like to use.
	#
	# You can run code by hitting the 'Run' button near the top left.
	#
	# Enjoy your interview!
	'''
	Please work on vertical traverse binary tree
	for example,
	1
	/ \
	2 3
	\
	4
	output (2 before 1 right? also, are you able to connect with your phone?)
	[2]
	[1]
	[3]
	If 2 has a right child, 4,
	so output
	[2]
	[1,4]
	[3]
	I am ouside home, please work on coding, 10 minutes I will be home, talk to u and review your code.
	'''
	# return type is list of lists; each inner list contains all the nodes grouped under a single x coordinate
	class Node:
	def __init__(self,val):
	self.val=val
	self.l=None
	self.r=None
	def verticalTraverse(root):
	if root==None:
	return []
	stack,nodes=[(root,0,0)],[(root,0,0)] # put original node
	while stack:
	node,x,y=stack.pop()
	if node==None:
	continue
	if node.l:
	# y is negative of depth
	nodeData=(node.l,x-1,y-1) # x-1, y - 1 - level
	stack.append(nodeData) # data structure,triple,
	nodes.append(nodeData) # nodes - list of nodes - sorted later
	if node.r:
	nodeData=(node.r,x+1,y-1) # x+1
	stack.append(nodeData)
	nodes.append(nodeData)
	# explored all vertices of tree, stored nodes we saw
	# to sort, we want in order of smaller x, larger y, value of the node
	nodes.sort(key=lambda node: (node[1], -node[2], node[0].val))
	order=[[nodes[0]]]
	for i in range(1,len(nodes)):
	# if x position is the same, put nodes in same array
	if nodes[i][1]==nodes[i-1][1]:
	order[-1].append(nodes[i][0].val)
	else:
	order.append([nodes[i-1][0]].val)
	# order is a list of lists
	return order
	a=Node(1)
	b=Node(2)
	c=Node(3)
	d=Node(4)
	a.l=b
	a.r=c
	b.r=d
	print(verticalTraverse(a))

view raw VerticalTraverseTree.py hosted with ❤ by GitHub

Here is the link.