Tree sort using a closure to hold tree nodes

treesort_nestedfunctions.py

#!/usr/bin/env python3
# https://en.wikipedia.org/wiki/Tree_sort#Example
opRead = 0
opWrite = 1

varVal = 0
varLeft = 1
varRight = 2

# learned this was possible from https://aphyr.com/posts/340-reversing-the-technical-interview

def make_node(value, left, right):
    def node(op, var, newVal=0):
        nonlocal value, left, right
        if op == opRead:
            if var == varVal:
                return value
            if var == varLeft:
                return left
            if var == varRight:
                return right
        if op == opWrite:
            if var == varVal:
                value = newVal
            if var == varLeft:
                left = newVal
            if var == varRight:
                right = newVal
    return node

def insert_node(head, newValue):
    if head == None:
        return make_node(newValue, None, None)
    orighead = head
    parentnode = None
    direction = varRight
    while head != None:
        value = head(opRead, varVal)
        direction = varRight
        if newValue < value:
            direction = varLeft
        parentnode = head
        head = head(opRead, direction)
    parentnode(opWrite, direction, make_node(newValue, None, None))
    return orighead

def inorder(node):
    if node == None:
        return
    inorder(node(opRead, varLeft))
    print(node(opRead, varVal))
    inorder(node(opRead, varRight))

def main1():
    root = None

    while True:
        inval = int(input())
        if inval < 0:
            break
        root = insert_node(root, inval)

    inorder(root)
def main():
    # first two rows from A Million Random Digits with 100,000 Normal Deviates
    # https://www.rand.org/pubs/monograph_reports/MR1418.html
    numbers = [10097, 32533, 76520, 13586, 34673, 54876, 80959, 9117, 39292, 74945, 37542, 4805, 64894, 74296, 24805, 24037, 20636, 10402, 822, 91665]
    root = None
    for n in numbers:
        root = insert_node(root, n)
    inorder(root)
if __name__ == "__main__":
    main()