Trees

Overview

A tree is a hierarchical structure of nodes where each node has one parent (except the root) and zero or more children. A binary search tree (BST) keeps smaller values to the left and larger to the right, giving O(log n) search, insert, and delete when balanced. If the tree becomes lopsided it degrades to O(n), behaving like a linked list.

Syntax / Usage

Define a node with left and right children, then insert by comparison.

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

def insert(root, value):        # O(log n) if balanced
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

root = None
for v in [5, 3, 8, 1]:
    root = insert(root, v)

Examples

Search a BST by following the ordering rule:

def search(root, target):
    node = root
    while node:                 # O(log n) if balanced
        if target == node.value:
            return True
        node = node.left if target < node.value else node.right
    return False

print(search(root, 8))  # True

In-order traversal visits values in sorted order:

def in_order(node):
    if node is None:
        return
    in_order(node.left)
    print(node.value)           # visits ascending
    in_order(node.right)

in_order(root)  # 1 3 5 8

Common Mistakes

• Forgetting the base case in recursion, causing infinite loops or errors
• Assuming O(log n) even when the tree is unbalanced (really O(n))
• Not reassigning the returned node (root = insert(root, v))
• Confusing tree traversal orders (in-order vs pre-order vs post-order)
• Dereferencing a None child without checking first

See Also

data-structures-graphs data-structures-heaps data-structures-hash-tables