Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - No Derivative Works 3.0 United States License.
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.
Nodein 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
kand no children.
insert_sortto 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.
inorder_traverse, which assembles a sorted list.
insert_sort. Note: In Python (and hence in SageMath), all but the first entry in a list
ais most easily specified using