balance.py

# algorithm to order sequence for optimal binary tree construction

import sys

def arrange(numArray):
    if len(numArray) == 0:
        return numArray

    numArray.sort()

    mid = len(numArray) // 2
    optiomalOrder = [numArray[mid]]
    optiomalOrder.extend(arrange(numArray[:mid]))
    optiomalOrder.extend(arrange(numArray[mid + 1:]))

    return optiomalOrder

# numlines=int(sys.stdin.readline())
# for i in range(0,numlines):
#   linearray=list(map(int,sys.stdin.readline().split()))
#   linearray=linearray[1:]
  #linearray now contains the list of values found on the line (excluding the first item which is the number of elements on the line), do something with it...
  # print(*arrange(linearray))  # star unpacks the list and return every element


# print("178 57 26 157 679 397 898",end='')
# print()
# print("342 56 38 79 581 381 709",end='')
# print()

print(arrange([898, 157, 397, 57, 178, 26, 679]))
print(arrange([342, 56, 38, 79, 581, 381, 709]))
print(arrange([25, 50, 100, 150, 200, 250, 300, 350]))