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 balancedA tree whose height stays about log n for n nodes, keeping BST search and insert at O(log n). 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 leafA tree node with no children.. In a binary treeA tree in which each node has at most two children, called left and right., each node has at most two children, called left and right. The heightThe number of nodes on the longest path from the root down to a leaf; an empty tree has height 0. 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 BSTA binary search tree: for every node, values in the left subtree are smaller and values in the right subtree are larger. 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.