class Employee:
    subordinates = []

    #Constructor, Time O(1), Space O(1)
    def __init__(self, id, name, managerId): # constructor method
        self.id = id
        self.name = name
        self.managerId = managerId

class BuildHierarchyTree:
    employees = {}
    root = None

    #Read data and build map, Iteration, Time O(n), Space O(n), n is number of employees
    def readDataAndCreateMap(self, lines):
        employee = None         			
        for strLine in lines: 
            values = strLine.split(" ")
            if len(values) >= 4:
                employee = Employee (values[0], values[1] + " " + values[2], values[3])
            else: 
                employee = Employee (values[0], values[1] + " " + values[2], 0)
            self.employees[employee.id] = employee
            if employee.managerId == 0 :
                self.root = employee
    
    #Build tree, Recursion, Time O(n), Space O(h), n is number of employees, h is levels of hierarchy tree
    def buildHierarchyTree(self, root) :
        employee = root
        subs = self.getSubsById(employee.id)
        employee.subordinates = subs
        if len(subs) == 0:
            return
        for em in subs: 
            self.buildHierarchyTree(em)
	
    #Get subordinates list by given id, Time O(n), Space O(k) ~ O(n), k is number of subordinates
    def getSubsById(self, managerId) :
        subs = []
        for em in self.employees.values():
            if em.managerId == managerId: 
                subs.append(em)
        return subs
	
    #Print tree, Recursion, Time O(n), Space O(h)
    def printHierarchyTree(self, root, level) :
        for  i in range(0, level, 1):
            print("\t", end='')
        print(root.name);		 
        subs = root.subordinates
        for em in subs: 
            self.printHierarchyTree(em, level+1)
	  
lines = {
        "1 Rob Choi 6",
        "2 Paul Marmolejo 5",
        "3 Lois Lemer 6",
        "4 Christie Jacobs 5",
        "5 Moises Medina 6",
        "6 Joseph Grant",
        "7 Andy Zuckeman 1",
        "8 Melaney Partner 3",
        "9 Cliff Gannett 5",
        "10 Mark O'Donnell 1"
	}	

tree = BuildHierarchyTree()
tree.readDataAndCreateMap(lines)
tree.buildHierarchyTree(tree.root)
tree.printHierarchyTree(tree.root, 0)