Trees and Binary Search Trees

What a tree is

So far most data we have stored has been linear: a list has a first item, a second item, and so on, in one straight line. A tree is different. A tree is a way of organizing data where each piece of data can branch out to several others below it, the way a family tree or a company org chart does.

A tree is built out of nodes. A node is a small container that holds one value plus links to other nodes. When one node links down to another, we say the first is the parent and the second is the child. The links are called edges.

Some vocabulary you will use constantly. Read it once now; the rest of the lesson will make it concrete.

• Root: the single node at the very top. It has no parent. Every tree has exactly one root.
• Child: a node directly below and linked to another node.
• Parent: the node directly above a child.
• Leaf: a node with no children. These are the “ends” of the tree.
• Subtree: any node together with everything hanging below it. A subtree is itself a smaller tree.
• Depth of a node: how many edges you cross to get from the root down to that node. The root has depth 0.
• Height of a tree: the number of edges on the longest path from the root down to a leaf. A tree with just a root has height 0.

One important rule: in a tree there are no loops. You can never follow child links and end up back where you started. Each node (except the root) has exactly one parent.

Binary trees

A binary tree is a tree where every node has at most two children. “Binary” means “two.” We give the two children fixed names: the left child and the right child. A node might have both, just one, or none.

That “at most two” rule sounds like a small restriction, but it makes binary trees easy to reason about and is the foundation for the structure we care about most here.

The binary search tree ordering property

A binary search tree (BST) is a binary tree with one extra rule that makes it useful for searching. The rule is about how values are placed:

For every node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater than the node’s value.

That single rule holds at every node, not just the root. Because of it, when you are looking for a value you can throw away half the tree at each step: if the value you want is smaller than the current node, it can only be on the left; if larger, only on the right. This is the same idea as binary search on a sorted list, but built into the shape of the data.

Here is a small BST holding the values 8, 3, 10, 1, 6, 14, 4, 7, 13.

graph TD
    A((8)) --> B((3))
    A --> C((10))
    B --> D((1))
    B --> E((6))
    C --> F((14))
    E --> G((4))
    E --> H((7))
    F --> I((13))

Check the rule on the root, 8: everything on the left (3, 1, 6, 4, 7) is less than 8, and everything on the right (10, 14, 13) is greater than 8. Now check it on node 3: everything in its left subtree (just 1) is less than 3, and everything in its right subtree (6, 4, 7) is greater than 3. The property holds everywhere.

Building a tree in Python

To store a node we make a small class. A class is a blueprint for creating objects that bundle some data together. Each TreeNode holds a value and two links, left and right, which start out empty (None means “no node here”).

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

__init__ is the setup method that runs when you create a node. self refers to the particular node being created. So TreeNode(8) gives you a node holding 8 with no children yet. We build a whole tree by linking nodes together.

root = TreeNode(8)
root.left = TreeNode(3)
root.right = TreeNode(10)
print(root.value)        # -> 8
print(root.left.value)   # -> 3
print(root.right.value)  # -> 10

Insert: adding a value in the right place

To insert a value we start at the root and walk down. At each node we compare: if the new value is smaller we go left, if larger we go right. When we reach an empty spot (None), that is where the new value belongs. This is naturally recursive: a function that solves a small problem by calling itself on a smaller piece. Inserting into a tree is the same as inserting into one of its subtrees.

def insert(node, value):
    if node is None:
        return TreeNode(value)   # empty spot: create the node here
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    # if value == node.value we ignore it (no duplicates)
    return node

root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)

print(root.value)             # -> 8
print(root.left.value)        # -> 3
print(root.right.value)       # -> 10
print(root.left.right.value)  # -> 6

Each insert walks from the root down to a leaf position, so it does about as much work as the tree is tall. That height is written h. Insert costs O(h) time. The extra space is the chain of recursive calls, also O(h).

Watching one insert change the tree

Start from this smaller tree and insert the value 7:

graph TD
    A((8)) --> B((3))
    A --> C((10))
    B --> D((1))
    B --> E((6))
    C --> F((14))

We walk down from the root, comparing at each node until we reach an empty spot. The walk goes 7 < 8 (left) to 3, then 7 > 3 (right) to 6, then 7 > 6 (right) and lands on an empty spot. That empty spot becomes the new node’s home, as the right child of 6:

graph TD
    A((8)) --> B((3))
    A --> C((10))
    B --> D((1))
    B --> E((6))
    C --> F((14))
    E --> G((7))

Exactly one edge is new (6 → 7). Nothing else in the tree moved.

Trace: building the tree one insert at a time

Here is the full state of the tree after each insert as we add [8, 3, 10, 1, 6] in that order. The “Edges” column lists every parent → child link that exists so far, which fully describes the tree’s shape at that point.

Each insert does a bit more comparing as the tree grows taller, which is exactly why one insert costs O(h).

Search: finding a value

Search uses the exact same walk, but instead of stopping at an empty spot to build, it stops when it finds the value (or runs out of tree).

def search(node, value):
    if node is None:
        return False          # ran off the bottom: not found
    if value == node.value:
        return True
    if value < node.value:
        return search(node.left, value)
    else:
        return search(node.right, value)

print(search(root, 7))    # -> True
print(search(root, 5))    # -> False

Searching for 7 in the tree above visits 8 (7 < 8, go left), then 3 (7 > 3, go right), then 6 (7 > 6, go right), then 7. Four nodes out of nine. We never looked at the entire right half of the tree. Search is O(h) time and O(h) space for the recursion.

Here is that same search as a table, one row per node visited:

In-order traversal gives sorted order

To traverse a tree means to visit every node. There are several orders you can visit in; the one that matters for a BST is in-order: visit the whole left subtree first, then the current node, then the whole right subtree.

Because of the BST ordering rule (left is smaller, right is larger), in-order traversal visits the values from smallest to largest. It hands you the data sorted, for free.

def in_order(node, out):
    if node is None:
        return
    in_order(node.left, out)   # everything smaller, first
    out.append(node.value)     # then this node
    in_order(node.right, out)  # then everything larger

result = []
in_order(root, result)
print(result)   # -> [1, 3, 4, 6, 7, 8, 10, 13, 14]

A traversal must touch every node once, so in-order is O(n) time for n nodes. It uses O(h) space for the recursion stack.

Delete: removing a value

Deleting is the trickiest operation because after you pull a node out, the tree still has to satisfy the ordering rule. There are three cases for the node you found:

1. No children (a leaf). Just remove it; return None to the parent.
2. One child. Splice the node out by returning its single child to the parent.
3. Two children. You cannot just delete it, because it holds a spot two subtrees depend on. Instead, find the in-order successor (the smallest value in the right subtree), copy that value into the node, then delete the successor from the right subtree. The successor always has at most one child, so removing it falls back to case 1 or 2.

def find_min(node):
    while node.left is not None:
        node = node.left
    return node

def delete(node, value):
    if node is None:
        return None
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        # this is the node to remove
        if node.left is None:
            return node.right          # 0 or 1 child (on the right)
        if node.right is None:
            return node.left           # 1 child (on the left)
        successor = find_min(node.right)   # two children
        node.value = successor.value
        node.right = delete(node.right, successor.value)
    return node

Deleting a node with one child

Take this tree and delete 3:

graph TD
    A((5)) --> B((3))
    A --> C((8))
    B --> D((4))

Node 3 has a single child, 4, so 3 is spliced out and 4 is promoted into its place:

graph TD
    A((5)) --> D((4))
    A --> C((8))

The edge 5 → 3 became 5 → 4, and node 3 is gone. The subtree that hung under 3 (here just 4) simply moves up one level.

Deleting a node with two children

Now delete 8 from this tree:

graph TD
    A((5)) --> B((3))
    A --> C((8))
    C --> D((7))
    C --> E((9))

Node 8 has two children (7 and 9), so we take case 3. The in-order successor is the smallest value in 8’s right subtree, which is 9. We copy 9 into the node, then delete the original 9:

graph TD
    A((5)) --> B((3))
    A --> F((9))
    F --> D((7))

The value at that position changed from 8 to 9, the leftover 9 leaf was removed, and 7 stays put. The ordering rule still holds everywhere. Delete walks down to the node and, in the two-child case, walks down once more to the successor, so it costs O(h) time and O(h) space.

Why balance matters

The cost of insert and search is O(h), where h is the height. So everything depends on how tall the tree is, and that depends on the order values were inserted.

If the tree stays balanced (both sides filled in fairly evenly), the height is about log2(n). For a million nodes that is only about 20 levels. Insert and search are then O(log n), which is extremely fast.

But a BST does not balance itself. Watch what happens if you insert values that are already sorted:

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

print(root.value)              # -> 1
print(root.right.value)        # -> 2
print(root.right.right.value)  # -> 3

Every value is larger than the last, so every node becomes a right child. The tree is a straight line, one node per level. Its height is n - 1, and search degrades to O(n) — no better than scanning a plain list. This shape is sometimes called a degenerate or stringy tree, and drawn out it is just a straight line:

graph TD
    A((1)) --> B((2))
    B --> C((3))
    C --> D((4))
    D --> E((5))

This is the central tradeoff: a BST gives you O(log n) operations only when it stays roughly balanced. More advanced structures (AVL trees, red-black trees) keep the tree balanced automatically. The plain BST in this lesson does not, so the order you insert in decides whether you get O(log n) or O(n).

Cost of every operation

Every operation that walks the tree costs O(h), where h is the height. The two columns below show why the shape matters so much: a balanced tree makes h ≈ log2(n), while a degenerate (stringy) tree makes h ≈ n. Space is the depth of the recursion, also O(h).

In-order traversal is O(n) in both columns because it must visit every node no matter the shape; the others do a single root-to-leaf walk, so they ride entirely on the height.

Common pitfalls

• Assuming O(log n) always. It is O(h). Only a balanced tree makes h ≈ log n. Inserting sorted or reverse-sorted data gives you the worst case, O(n).
• Confusing depth and height. Depth is measured from the root down to a node; height is the longest root-to-leaf distance for the whole tree. They are related but not the same thing.
• Forgetting the None base case in recursion. Every recursive tree function must first check if node is None. Skip it and you will try to read .left off None and get an AttributeError, or recurse forever.
• Reassigning the link on insert. Write node.left = insert(node.left, value). If you call insert(node.left, value) without assigning the result back, a newly created node never gets attached to the tree.
• The property is about whole subtrees, not just immediate children. A value in the left subtree must be less than this node even if it is several levels down. Checking only the direct children is not enough to call something a valid BST.

Practice

1. Write a function find_min(node) that returns the smallest value in a non-empty BST. You should not need to look at every node — think about which direction “smaller” always lies.
2. Write height(node) that returns the height of a tree (an empty tree can count as -1, a single node as 0). Use recursion: a node’s height is 1 plus the taller of its two subtrees.
3. Write count_nodes(node) that returns how many nodes are in the tree. Confirm it returns 9 for the first example tree in this lesson.