Python Trees and Binary Search Trees

Key terms, using a plant catalogue as the example:

• Root: the single top node ("Plants").
• Parent / child: "Trees" is a child of "Plants" and the parent of "Oak".
• Leaf: a node with no children ("Oak").
• Subtree: a node together with all its descendants.
• Depth of a node: its number of edges from the root. Height of the tree: the depth of its deepest leaf.

catalogue = {"Plants": {"Trees": {"Oak": {}, "Birch": {}}, "Herbs": {"Mint": {}}}}

def leaves(tree):
    for name, children in tree.items():
        if children:
            yield from leaves(children)
        else:
            yield name

print(list(leaves(catalogue)))   # ['Oak', 'Birch', 'Mint']

Nested dictionaries and objects with a children list represent general trees, where a node can have any number of children. In an ordinary rooted tree every node except the root has exactly one parent and there are no cycles, which is what lets recursive functions process trees cleanly: handle this node, then recurse into each subtree.

A BST keeps a rule at every node: all keys in the left subtree are smaller, all keys in the right subtree are larger. Searching compares the target with the current key and goes left or right, discarding a whole subtree each time, like binary search:

def search(node, key):
    while node is not None:
        if key == node.key:
            return node
        node = node.left if key < node.key else node.right
    return None

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

Insertion follows the same path as a search and adds the new node where the search fell off the tree. You must choose a duplicate policy: ignore repeats (as here), store a count on the node, or consistently send equal keys to one side. Leaving it undecided produces trees whose searches disagree with their inserts.

A traversal visits every node once. The three classic depth-first orders differ only in when the current node is visited relative to its subtrees:

def inorder(node):
    if node:
        yield from inorder(node.left)
        yield node.key
        yield from inorder(node.right)

def preorder(node):
    if node:
        yield node.key
        yield from preorder(node.left)
        yield from preorder(node.right)

Inorder traversal of a valid BST always yields sorted keys, which makes it a handy correctness check. The order you get depends on the tree's shape: the same keys inserted in a different order build a different tree with a different preorder. Breadth-first (level-order) traversal, using a queue, visits nodes row by row, and is covered in graph traversal.

Search and insertion follow one path from the root, so their cost is proportional to the tree's height:

• A balanced tree with n nodes has height about log₂ n: around 20 for a million keys.
• A skewed tree, built by inserting keys in sorted order, becomes a chain where every node has only a right child: height n, and search degrades to O(n), no better than a linked list.

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

A plain BST is not automatically balanced. Self-balancing variants, such as AVL trees and red-black trees, rotate nodes after insertions to keep the height logarithmic, guaranteeing O(log n) operations. Python doesn't include a balanced tree in the standard library; in practice, a dict covers exact lookups, and the bisect module or the third-party sortedcontainers package covers sorted data and range queries.

Task: implement BST insertion and search with a duplicate policy, then compare balanced and skewed shapes. Store a count for duplicates instead of ignoring them:

class Node:
    def __init__(self, key):
        self.key, self.count, self.left, self.right = key, 1, None, None

def insert(node, key):
    if node is None:
        return Node(key)
    if key == node.key:
        node.count += 1
    elif key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node

def find(node, key):
    while node and node.key != key:
        node = node.left if key < node.key else node.right
    return node.count if node else 0

root = None
for plant in [42, 17, 63, 17, 8, 42, 42]:
    root = insert(root, plant)
print(find(root, 42), find(root, 17), find(root, 99))   # 3 2 0

Then build trees from range(1, 8) and from [4, 2, 6, 1, 3, 5, 7] and compare their heights: 7 versus 3. For the worked check, the search cost in a simple BST is determined by the tree height.

For production needs, see the bisect module and the sortedcontainers package. Continue with graphs and graph traversal and revisit recursion. Practise with the Python exercises and Python quiz.