Inserting Into a Binary Search Tree

class BNode:
    __slots__ = ("data", "left", "right")

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def insert_correct(root, value):
    if root is None:
        return BNode(value)
    if value < root.data:
        root.left = insert_correct(root.left, value)
    elif value > root.data:
        root.right = insert_correct(root.right, value)
    return root


def insert_broken(root, value):
    """The new node is created and then thrown away."""
    if root is None:
        return BNode(value)
    if value < root.data:
        insert_broken(root.left, value)            # no assignment
    elif value > root.data:
        insert_broken(root.right, value)
    return root


def inorder(node, out=None):
    out = [] if out is None else out
    if node is not None:
        inorder(node.left, out)
        out.append(node.data)
        inorder(node.right, out)
    return out


for name, insert in (("correct", insert_correct), ("broken ", insert_broken)):
    root = None
    for value in (50, 30, 70, 20, 40):
        root = insert(root, value)
    print("%s: tree holds %s" % (name, inorder(root)))

print()
print("the broken version raised no error and kept only the root's first child.")

correct: tree holds [20, 30, 40, 50, 70]
broken : tree holds [50]

the broken version raised no error and kept only the root's first child.

The broken version holds one of the five values and reported nothing wrong. Only the first insertion worked, because at the top level the caller does assign the return value (root = insert(root, value)). Every insertion after that descended into the tree, created its node, and threw it away.

What the insertion order does to the shape

The same values, inserted in different orders, give completely different trees. This is the setup for chapter 68.

class BNode:
    __slots__ = ("data", "left", "right")

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def insert(root, value):
    if root is None:
        return BNode(value)
    if value < root.data:
        root.left = insert(root.left, value)
    elif value > root.data:
        root.right = insert(root.right, value)
    return root


def build(values):
    root = None
    for value in values:
        root = insert(root, value)
    return root


def height(node):
    return -1 if node is None else 1 + max(height(node.left), height(node.right))


def shape(node):
    if node is None:
        return "."
    if node.left is None and node.right is None:
        return str(node.data)
    return "%s(%s, %s)" % (node.data, shape(node.left), shape(node.right))


orders = [
    ("balanced order ", [50, 30, 70, 20, 40, 60, 80]),
    ("sorted order   ", [20, 30, 40, 50, 60, 70, 80]),
    ("reverse sorted ", [80, 70, 60, 50, 40, 30, 20]),
    ("almost sorted  ", [20, 30, 40, 50, 80, 70, 60]),
]
for name, values in orders:
    tree = build(values)
    print("%s height %d  %s" % (name, height(tree), shape(tree)))

balanced order  height 2  50(30(20, 40), 70(60, 80))
sorted order    height 6  20(., 30(., 40(., 50(., 60(., 70(., 80))))))
reverse sorted  height 6  80(70(60(50(40(30(20, .), .), .), .), .), .)
almost sorted   height 6  20(., 30(., 40(., 50(., 80(70(60, .), .)))))

The same seven values. Height 2 in one order and height 6 in another, which is a line.

Sorted input is not an unusual case: data often arrives sorted, from a database, a file, or a previous sort. The commonest real input produces the worst possible tree, and that is chapter 68.

The cost

The last row is worth noticing against the array of chapter 12, which moved everything after the insertion point. A tree pays with pointer-following rather than with movement.

Quick revision

• Insertion searches for the value; where the search falls off the tree is where the new leaf goes.
• A new value always becomes a leaf and nothing existing moves.
• node.left = insert(node.left, value): the assignment is what attaches the node. Omitting it inserts

nothing and raises no error.

• A duplicate is ignored under this book's convention.
• Insertion order decides the shape: the same seven values gave height 2 in one order and height 6 in

sorted order, which is a line.

• Sorted input is common, which makes the worst case common.
• O(log n) balanced, O(n) degenerate, and zero nodes moved either way.

Test yourself

1. Where does a newly inserted value end up? As a leaf, at the position where the search for it falls off the tree.

2. Why must the recursive call be assigned back to the child pointer? Because the function returns the subtree's new root, which for an empty subtree is the newly created node. Without the assignment the new node is discarded and nothing is inserted.

3. What happens if the assignment is omitted, and why is it dangerous? Only the first insertion takes effect, because only the top level caller assigns the return value. No error is raised: in the run, five insertions left a tree holding one value, silently.

4. The same seven values gave heights 2 and 6 in different orders. Which order gave 6 and why? Sorted order, ascending or descending. Each new value is larger (or smaller) than everything present, so it goes to the same side every time and the tree becomes a line.

5. Why is that the dangerous case in practice? Because sorted input is common: data often arrives already in order from a file, a database or an earlier sort. The commonest input produces the worst tree.

6. How many existing nodes move during an insertion? None, ever. The cost is in walking to the position, not in moving anything, which is the difference from an array.