Inserting, and Getting Sorted Order for Free

Insert: search for the gap

To insert a value, go left or right exactly as in a search. When you fall off the tree (reach None), that's where the new node belongs:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node                       # duplicates are ignored

def inorder(node):
    return [] if node is None else inorder(node.left) + [node.value] + inorder(node.right)

root = None
for v in [50, 30, 70, 20, 40, 60, 80, 30]:
    root = insert(root, v)
print(inorder(root))

Output

[20, 30, 40, 50, 60, 70, 80]

Look at that: inorder traversal of a BST gives the values in sorted order. Left (smaller), node, right (bigger) – at every level.

Smallest and largest

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

node = root
while node.left:          # keep going left
    node = node.left
print("smallest:", node.value)

node = root
while node.right:         # keep going right
    node = node.right
print("largest:", node.value)

Output

smallest: 20
largest: 80