Using a Binary Tree to Sort a List of Integers
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
A possible solution to sort a list of integers using a binary tree.
Solution
""" binary_tree.py """
# usage: python3 binary_tree.py < input
import sys
from collections import namedtuple
node = namedtuple('Node', 'data, left, right')
def build_tree(values):
""" binary tree as dictionary of tuples """
index = 0
store = {}
for v in values:
store[index] = node(v, None, None)
if index != 0:
i = 0
while True:
match v < store[i].data, store[i].left, store[i].right:
case True, None, _:
store[i] = store[i]._replace(left=index)
break
case True, i, _:
continue
case False, _, None:
store[i] = store[i]._replace(right=index)
break
case False, _, i:
continue
index += 1
return store
def inorder_tree(store):
""" in-order traversal of binary tree """
i = None
queue = [0]
visited = []
output = []
while queue:
i = queue.pop()
j, k = store[i].left, store[i].right
if j is not None and j not in visited:
queue.append(i)
queue.append(j)
else:
output.append(store[i].data)
visited.append(i)
if k is not None and k not in visited:
queue.append(k)
return output
def main():
""" let's go! """
with sys.stdin as infile:
nums = [int(i) for i in infile]
print('\n', nums)
data = build_tree(nums)
ordered = inorder_tree(data)
print('\n', ordered, '\n')
assert ordered == sorted(nums)
if __name__ == '__main__':
main()