quiz_9_sol.py

# Randomly generates a binary search tree whose number of nodes
# is determined by user input, with labels ranging between 0 and 999,999,
# displays it, and outputs the maximum difference between consecutive leaves.
#
# Written by Eric Martin for COMP9021

import sys
from random import seed, randrange
from binary_tree import *

def gather_nodes(tree):
    if tree.value == None:
        return []
    nodes = gather_nodes(tree.left_node)
    nodes.extend(gather_nodes(tree.right_node))
    nodes.append(tree)
    return nodes

def max_diff_in_consecutive_leaves(tree):
    leaves = [node for node in gather_nodes(tree)
                         if node.left_node.value is None and
                            node.right_node.value is None]
    if len(leaves) == 1:
        return 0
    return max((leaves[i + 1].value - leaves[i].value
                        for i in range(len(leaves) - 1)))


provided_input = input('Enter two integers, the second one being positive: ')
provided_input = provided_input.split()
if len(provided_input) != 2:
    print('Incorrect input, giving up.')
    sys.exit()
try:
    seed_arg = int(provided_input[0])
    nb_of_nodes = int(provided_input[1])
    if nb_of_nodes < 0:
        raise ValueError
except:
    print('Incorrect input, giving up.')
    sys.exit()

seed(seed_arg)
tree = BinaryTree()
for _ in range(nb_of_nodes):
    datum = randrange(1000000)
    tree.insert_in_bst(datum)
print('Here is the tree that has been generated:')
tree.print_binary_tree()
print('The maximum difference between consecutive leaves is: ', end = '')
print(max_diff_in_consecutive_leaves(tree))