Vertical traverse tree - Feb. 15, 2020 10:00 PM - as an interviewer, interviewee is the compiler algorithm in silicon valley

VerticalTraverseTree.py

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