tounament.py

class Node():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

T = Node(0)
T.left = Node(1)
T.right = Node(-2)
T.left.right = Node(2)
T.left.left = Node(3)
T.right.left = Node(-1)

# 1. This function is poorly implemented, and probably buggy. 
#    Talk about what's wrong with it. Can you fix it?
#    What is the runtime of this function?
#
"""
0
    1
        3
        2
    -2
        -1

"""
def indent(count):
    print("  "*count, end="")

def printTree(node, depth=0):
    """ Print the tree as an indented list """
    if not node:
        return
    indent(depth)
    print(node.val)
    printTree(node.left,depth=depth+1)
    printTree(node.right,depth=depth+1)

printTree(T)

# 2. Given a list of players in a tournament, construct a tree representing who won.
#    You may select the winner of any given match in any way you choose.





# 2.a. Would the above printTree() function be suitable for viewing this output?
#      What would you change about it?


players = ["Joe","Jane","Bob","Miranda"]
"""
            Bob            Miranda
        Bob    Jane    Miranda    Jane

Bob Miranda Joe Jane

1. Construct the Tree

2. Fill the leaves with the names

3. Post Order Traversal where each node figures out the winner of it's children

joe jane bob mir | joe bob | bob

 
1 - 1
2 - 3
3 - 5
4 - 7
5 - 9



"""

from collections import deque

def construct_tree(players):
    """
    Time Complexity: n  + n/2 + n/4
    """
    if not players:
        return None
    
    queue = [Node(player) for player in players]
    i = 0
    
    while len(queue) - 1 > i:
         
        p1 = queue[i]
        p2 = queue[i + 1]
        i += 2      
        
        winner = Node(p1.val) if p1.val <= p2.val else Node(p2.val)
        winner.left = p1
        winner.right = p2
        
        queue.append(winner)
        
    return queue[i]
        
printTree(construct_tree(["joe", "jane", "bob", "miranda"]))