Trees and BSTs

Why it matters

Trees model anything hierarchical: folders on disk, the HTML elements of a web page (the DOM), an organisation chart, a decision tree in machine learning, a parsed expression in a compiler. Database indexes use balanced trees (B-trees) so lookups stay fast as tables grow. Once you can walk a tree recursively, all of these become approachable.

Vocabulary

A tree is made of nodes connected by edges, with one root at the top. Each node can have children; a node with no children is a leaf. In a binary tree, each node has at most two children, called left and right. The height is the number of nodes on the longest path from the root down to a leaf (an empty tree has height 0).

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

#        8
#      /   \
#     3     10
#    / \      \
#   1   6      14
root = TreeNode(8,
                TreeNode(3, TreeNode(1), TreeNode(6)),
                TreeNode(10, None, TreeNode(14)))

Traversals: visiting every node

Every node's left and right are themselves trees (or None), so tree functions are naturally recursive. The base case is the empty tree, None. The three depth-first orders differ only in when you visit the current node:

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

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

When do you use which? Pre-order copies or prints a structure top-down (like listing a folder before its contents). Post-order handles children before parents (like adding up folder sizes, or deleting a tree). In-order gives sorted output for a binary search tree.

A fourth order, level-order (breadth-first), visits row by row: 8, then 3 and 10, then 1, 6, 14. It uses a queue instead of recursion; you will meet it in the next lesson on BFS.

Height

The same pattern answers many questions. The height of a tree is one (for this node) plus the taller of its two subtrees:

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

The example tree has height 3.

Binary search trees (BSTs)

A BST adds one rule: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. The tree above is a BST. That rule means you can search like binary search: compare with the node and go left or right, discarding a whole subtree each time.

Inserting follows the same path until it finds an empty spot:

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

root = None
for v in [8, 3, 10, 1, 6, 14]:
    root = bst_insert(root, v)
inorder(root)        # [1, 3, 6, 8, 10, 14]

The function returns the (possibly new) root of each subtree, so the empty-tree case and the "attach a new child" case are the same line.

Cost. Search and insert take time proportional to the height. A balanced BST with n nodes has height about log n, so operations are O(log n). But inserting values that are already sorted (1, 2, 3, 4, ...) makes every node a right child: the tree becomes a linked list of height n, and operations become O(n). Self-balancing trees (red-black, AVL, B-trees) fix this, and they are what real libraries and databases use.

Common mistakes

• Forgetting the None base case, which causes AttributeError: 'NoneType' object has no attribute 'left'.
• Mixing up the orders. Say it out loud: in-order means the node goes in the middle.
• Not reassigning the result of insert (node.left = bst_insert(node.left, value)), so new nodes are created but never attached.
• Assuming a BST is always fast. Sorted input makes it a list.

Quick recap

• Binary tree: nodes with left and right; None is the empty tree and the base case.
• Pre-order (node first), in-order (node in the middle), post-order (node last).
• BST rule: left smaller, right larger; in-order gives sorted values.
• BST operations cost O(height): O(log n) if balanced, O(n) if not.

Try it

In the Do tab, write inorder, preorder, height and bst_insert, then check that in-order on a BST you built gives sorted values.