Sharedsage_worksheets / binary_tree_sort.sagewsOpen in CoCalc
Worksheets related to Applied Discrete Structures

# Binary Tree Sorting

For more information on the algorithm, see Section 10.4 of Applied Discrete Structures. This is really all Python, although it's evaluated in Sage.

We implement the binary tree sort algorthm in SageMath by first defining a Node in the the tree to contain three components, a key value, a left child and a right child. This is accomplished with the following code. An expression of the form Node(k) creates a node with key k and no children.
class Node:
def __init__(self, keyval=None,Lchild=None,Rchild=None):
self.key = keyval
self.left = Lchild
self.right = Rchild
def depth(self):
if self.left==None and self.right==None:
return 0
else:
if self.left==None:
return 1+self.right.depth()
else:
if self.right==None:
return 1+self.left.depth()
else:
return max(self.left.depth(),self.right.depth())


We define the function insert_sort to recursively insert a key value, b, into a tree rooted at r. We will use this function to build a binary tree. Smaller key values are steered to the left and larger ones to the right.
def insert_sort(r,b):
if b<r.key:
if r.left==None:
r.left=Node(b)
else:
insert_sort(r.left,b)
else:
if r.right==None:
r.right=Node(b)
else:
insert_sort(r.right,b)

Once the tree is built, we traverse it with the function inorder_traverse, which assembles a sorted list.
def inorder_traverse(r):
if r.left!=None:
ls=inorder_traverse(r.left)
else:
ls=[]
m=r.key
if r.right!=None:
rs=inorder_traverse(r.right)
else:
rs=[]
return ls+[m]+rs


We demonstrate the process with a list of integers.
a=[6953,811,2324,1884,8945,1943,2923,7909,3390,8229,8337,9656,4545,7082,7333,6461,5306,2945,8414,9352,2993,8663,8260,6810,4263]

The first number in the list is placed at the root of our tree and then the rest are inserted using insert_sort. Note: In Python (and hence in SageMath), all but the first entry in a list a is most easily specified using slice notation, a[1:].
root=Node(a[0])
for b in a[1:]:
insert_sort(root,b)

Now we traverse the tree to get our sorted list.
a2=inorder_traverse(root)
a2

[811, 1884, 1943, 2324, 2923, 2945, 2993, 3390, 4263, 4545, 5306, 6461, 6810, 6953, 7082, 7333, 7909, 8229, 8260, 8337, 8414, 8663, 8945, 9352, 9656]