# Trees & Binary Search Trees

> What a tree actually is - nodes, root, children, leaves - then the binary search tree specifically: the ordering rule that makes search and insert fast, with real code building and searching one.


---

# Trees & Binary Search Trees

A file system has folders inside folders. An org chart has a CEO with reports, who have their own reports.
An HTML page has elements nested inside elements. All three are the same shape wearing different clothes:
a **tree** - and once you can see that shape, a whole category of real code stops looking mysterious.

This guide starts with what a tree actually is, then narrows to one specific, hugely useful kind: the
**binary search tree**, which turns the ordering trick from
[Sorting & Searching, Explained](/guides/sorting-and-searching-explained) into a data structure you can
insert into and search on the fly.

## How to read this

Read in order - Phase 2's binary search tree only makes sense once "node," "child," and "leaf" from Phase 1
are second nature.

## The phases

1. **[What a Tree Is](01-what-a-tree-is.md)** - nodes, root, children, leaves, and why so many real-world
   structures turn out to be trees.
2. **[Binary Search Trees](02-binary-search-trees.md)** - the one ordering rule that makes a tree fast to
   search and insert into, with real code building one from scratch.
3. **[BST Performance & Gotchas](03-bst-performance-and-gotchas.md)** - why a BST is usually `O(log n)`,
   how it can silently degrade to `O(n)`, and what fixes that.


---

# What a Tree Is

You've already met trees, even if nobody called them that. A folder full of folders. An org chart. The
nested tags of an HTML page. All of them share one shape: one thing at the top, branching down into more
things, which branch into more things, until the branching stops.

## The mental model: one parent, any number of children

**What it actually is.** A tree is made of **nodes**, connected so that every node has exactly **one**
parent (except the very top one) and any number of **children**. That "exactly one parent" rule is what
makes it a tree and not just any tangle of connections - there's no way to loop back around to somewhere
you already were.

```mermaid
flowchart TD
  Root["project (root)"] --> Src["src"]
  Root --> Tests["tests"]
  Root --> Readme["README.md (leaf)"]
  Src --> Main["main.py (leaf)"]
  Src --> Utils["utils.py (leaf)"]
  Tests --> TestMain["test_main.py (leaf)"]
```

📝 **Terminology.**
- The **root** is the single node at the top with no parent - `project` above.
- A node's **children** are the nodes directly below it that it points to.
- A **leaf** is a node with *no* children - the branching stops there (`README.md`, `main.py`, and the rest).
- The **height** of a tree is the number of steps from the root down to its deepest leaf.

```python runnable
class Folder:
    def __init__(self, name, children=None):
        self.name = name
        self.children = children or []

root = Folder("project", [
    Folder("src", [Folder("main.py"), Folder("utils.py")]),
    Folder("tests", [Folder("test_main.py")]),
    Folder("README.md"),
])

def is_leaf(node):
    return len(node.children) == 0

def count_leaves(node):
    if is_leaf(node):
        return 1
    return sum(count_leaves(child) for child in node.children)

def height(node):
    if is_leaf(node):
        return 0
    return 1 + max(height(child) for child in node.children)

print(count_leaves(root))
print(height(root))
```
```console
4
2
```
*What just happened:* `count_leaves` and `height` both walk the tree the same way every tree-walking
function does - check the current node, then recurse into each child and combine the results. This is the
same "self-similar problem" shape from [Recursion, Finally](/guides/recursion-finally-clicks): a folder
containing folders is a smaller version of the same problem, all the way down to a leaf.

## Why trees show up everywhere

**File systems.** Folders contain folders and files; a file is a leaf, a folder with contents is an
internal node, the drive's top level is the root.

**Org charts.** A manager has reports, who may have their own reports; an individual contributor with no
reports is a leaf.

**The DOM (a web page).** `<body>` contains `<div>`s, which contain more elements, down to leaf elements like
`<img>` or text nodes. Every time you've called `document.querySelector` and it "found the right element,"
something walked this tree for you.

**Any "this contains smaller versions of itself" data.** Nested comments, a company's category hierarchy,
a decision tree - if the shape is "one thing branching into more things, with no cycles," it's a tree.

💡 **Key point.** A **linked list** (see
[Data Structures, Explained](/guides/data-structures-explained/04-stacks-queues-and-linked-lists)) is
actually a special, restricted case of a tree - one where every node has *at most one* child. A tree just
lets a node branch into more than one.

## Recap

1. A **tree** is nodes connected so every node has exactly one parent (except the root) and any number of
   children.
2. The **root** has no parent; a **leaf** has no children; **height** is the longest path from root to leaf.
3. File systems, org charts, and the DOM are all trees - the shape shows up constantly once you recognize it.
4. Tree-walking code is naturally recursive: handle one node, recurse into its children, combine the results.

Next: one specific rule turns a tree into a structure you can search almost as fast as binary search.

```quiz
[
  {
    "q": "What makes a tree a tree, rather than just any connected structure?",
    "choices": ["Every node has exactly one parent (except the root), with no cycles", "Every node must have exactly two children", "All nodes must hold numbers", "It must be sorted"],
    "answer": 0,
    "explain": "The one-parent, no-cycles rule is what defines the branching tree shape - a binary tree (max two children per node) is one specific kind of tree, not the definition of 'tree' itself."
  },
  {
    "q": "What is a leaf?",
    "choices": ["The root node", "A node with no children", "Any node with exactly one child", "The deepest node in the tree, always"],
    "answer": 1,
    "explain": "A leaf is where the branching stops - it has no children, though it isn't necessarily the single deepest node if the tree is unbalanced."
  }
]
```


---

# Binary Search Trees

A **binary tree** is a tree where every node has *at most two* children, conventionally called **left** and
**right**. That alone doesn't buy you anything - it's just a shape. A **binary search tree (BST)** adds one
rule on top, and that one rule is what makes the whole thing fast to search.

## The ordering invariant

**The rule.** For *every* node in the tree: everything in its **left** subtree is smaller than it, and
everything in its **right** subtree is bigger than it. Not just its immediate children - the entire subtree
on each side.

```mermaid
flowchart TD
  N50["50"] --> N30["30"] & N70["70"]
  N30 --> N20["20"] & N40["40"]
  N70 --> N60["60"] & N80["80"]
```
*Everything under 50's left branch (20, 30, 40) is smaller than 50; everything under its right branch
(60, 70, 80) is bigger. The same rule holds at every node, not just the root - 30's left (20) is smaller
than 30, its right (40) is bigger.*

💡 **Key point.** This is the exact same idea as [binary search on a sorted
array](/guides/sorting-and-searching-explained/2) - "compare, then throw away half" - except the halves are
already laid out as branches instead of being computed from array indices each time.

## Searching a BST

Because of the invariant, searching is a straight walk: compare your target to the current node, and the
rule tells you which single branch could possibly contain it - go there, or stop.

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

class BST:
    def __init__(self):
        self.root = None

    def contains(self, value):
        current = self.root
        while current is not None:
            if value == current.value:
                return True
            current = current.left if value < current.value else current.right
        return False
```
*What just happened:* at each node, `value < current.value` tells you unambiguously which branch to follow
- there's never a reason to check the other side, because the invariant guarantees your target can't be
there. That's identical to binary search discarding the half that can't contain the target.

## Inserting into a BST

Insertion walks the tree the same way search does, following the same left/right rule, until it finds an
empty spot - that's where the new node belongs.

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = Node(value)
                    return
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(value)
                    return
                current = current.right

    def contains(self, value):
        current = self.root
        while current is not None:
            if value == current.value:
                return True
            current = current.left if value < current.value else current.right
        return False

tree = BST()
for n in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(n)

print(tree.contains(40))
print(tree.contains(90))
```
```console
True
False
```
*What just happened:* inserting `30` after `50` compares `30 < 50`, goes left, finds nothing there yet, and
plants it. Inserting `20` next compares `20 < 50` (go left), then `20 < 30` (go left again), then plants it
as `30`'s left child. Every insert is the same walk-and-place pattern, and it's what builds the shape from
the diagram above out of a plain list of numbers.

⚠️ **Gotcha.** Equal values need a rule too, even though the diagram above has none. This implementation
sends anything not strictly less than the current node to the *right* (`value < current.value` is the only
check, so equal values fall into the `else`), which means duplicates are allowed and always land in the right
subtree. That's a reasonable default - just be consistent, since search relies on it.

## The same tree, in other languages

A BST is a small object with two child links, so this is where languages differ the most. Most spell the
"maybe there is a child, maybe not" as a nullable reference; Rust makes it explicit with `Option<Box<Node>>`.
The walk-and-place logic underneath is the same in every one:

[[codegroup Binary Search Tree]]

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = Node(value)
                    return
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(value)
                    return
                current = current.right

    def contains(self, value):
        current = self.root
        while current is not None:
            if value == current.value:
                return True
            current = current.left if value < current.value else current.right
        return False
```

```javascript
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const node = new Node(value);
    if (this.root === null) {
      this.root = node;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (current.left === null) { current.left = node; return; }
        current = current.left;
      } else {
        if (current.right === null) { current.right = node; return; }
        current = current.right;
      }
    }
  }

  contains(value) {
    let current = this.root;
    while (current !== null) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }
}
```

```typescript
class Node {
  value: number;
  left: Node | null = null;
  right: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class BST {
  root: Node | null = null;

  insert(value: number): void {
    const node = new Node(value);
    if (this.root === null) {
      this.root = node;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (current.left === null) { current.left = node; return; }
        current = current.left;
      } else {
        if (current.right === null) { current.right = node; return; }
        current = current.right;
      }
    }
  }

  contains(value: number): boolean {
    let current: Node | null = this.root;
    while (current !== null) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }
}
```

```java
class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}

class BST {
    Node root;

    void insert(int value) {
        Node node = new Node(value);
        if (root == null) { root = node; return; }
        Node current = root;
        while (true) {
            if (value < current.value) {
                if (current.left == null) { current.left = node; return; }
                current = current.left;
            } else {
                if (current.right == null) { current.right = node; return; }
                current = current.right;
            }
        }
    }

    boolean contains(int value) {
        Node current = root;
        while (current != null) {
            if (value == current.value) return true;
            current = value < current.value ? current.left : current.right;
        }
        return false;
    }
}
```

```cpp
struct Node {
    int value;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int v) : value(v) {}
};

struct BST {
    Node* root = nullptr;

    void insert(int value) {
        Node* node = new Node(value);
        if (!root) { root = node; return; }
        Node* current = root;
        while (true) {
            if (value < current->value) {
                if (!current->left) { current->left = node; return; }
                current = current->left;
            } else {
                if (!current->right) { current->right = node; return; }
                current = current->right;
            }
        }
    }

    bool contains(int value) {
        Node* current = root;
        while (current) {
            if (value == current->value) return true;
            current = value < current->value ? current->left : current->right;
        }
        return false;
    }
};
```

```go
type Node struct {
    value       int
    left, right *Node
}

type BST struct {
    root *Node
}

func (t *BST) Insert(value int) {
    node := &Node{value: value}
    if t.root == nil {
        t.root = node
        return
    }
    current := t.root
    for {
        if value < current.value {
            if current.left == nil {
                current.left = node
                return
            }
            current = current.left
        } else {
            if current.right == nil {
                current.right = node
                return
            }
            current = current.right
        }
    }
}

func (t *BST) Contains(value int) bool {
    current := t.root
    for current != nil {
        if value == current.value {
            return true
        }
        if value < current.value {
            current = current.left
        } else {
            current = current.right
        }
    }
    return false
}
```

```rust
struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

#[derive(Default)]
struct Bst {
    root: Option<Box<Node>>,
}

impl Bst {
    fn insert(&mut self, value: i32) {
        let mut current = &mut self.root;
        while let Some(node) = current {
            current = if value < node.value { &mut node.left } else { &mut node.right };
        }
        *current = Some(Box::new(Node { value, left: None, right: None }));
    }

    fn contains(&self, value: i32) -> bool {
        let mut current = &self.root;
        while let Some(node) = current {
            if value == node.value {
                return true;
            }
            current = if value < node.value { &node.left } else { &node.right };
        }
        false
    }
}
```

[[/codegroup]]

## Why this is fast

Search and insert both do the same thing: at each node, one comparison eliminates an entire subtree. On a
**balanced** tree - one where each subtree is roughly the same size - that's `O(log n)`, exactly like binary
search: every step throws away about half the remaining nodes.

```quiz
[
  {
    "q": "What is the ordering invariant of a binary search tree?",
    "choices": ["Every node has exactly two children", "A node's entire left subtree is smaller than it; its entire right subtree is bigger", "The tree must be perfectly balanced", "Leaves must all be at the same depth"],
    "answer": 1,
    "explain": "That rule holds at every node, not just the root - it's what lets a single comparison eliminate an entire subtree."
  },
  {
    "q": "Why does a BST search only ever go one direction (left or right) at each node?",
    "choices": ["It checks both and picks the faster one", "The ordering invariant guarantees the target can't be on the other side", "It's a limitation, not a feature", "BSTs don't actually support search"],
    "answer": 1,
    "explain": "Because every value in the wrong-side subtree is guaranteed to be on the wrong side of the target, checking it would be wasted work."
  },
  {
    "q": "In the insert algorithm, what determines where a new value ends up?",
    "choices": ["It's always added as the root's direct child", "Walking left/right by the same comparison rule as search, until an empty spot is found", "A random position", "It's inserted at the deepest leaf, regardless of value"],
    "answer": 1,
    "explain": "Insert follows the exact same left/right walk as search - it just keeps going until it hits an empty spot, which is where the new node belongs."
  }
]
```


---

# BST Performance & Gotchas

Phase 2 showed why a BST search is fast: each comparison eliminates an entire subtree. That's true *if* the
tree is roughly balanced - similar-sized subtrees on each side. It quietly stops being true depending on the
order you insert values in, and that's the gotcha this phase is about.

## The good case: balanced

Insert `[50, 30, 70, 20, 40, 60, 80]` and you get the same tree from Phase 2 - each level roughly halves the
remaining nodes, so its height stays small.

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = Node(value)
                    return
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(value)
                    return
                current = current.right

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

balanced = BST()
for n in [50, 30, 70, 20, 40, 60, 80]:
    balanced.insert(n)
print("balanced height:", height(balanced.root))
```
```console
balanced height: 2
```
*What just happened:* 7 values, and the tree is only 2 levels tall past the root - each level packs roughly
twice as many nodes as the one above it, which is exactly the `log₂(n)` shape from
[Sorting & Searching, Explained](/guides/sorting-and-searching-explained). Search or insert here costs at
most 3 comparisons, no matter which of the 7 values you're after.

## The gotcha: already-sorted input degenerates the tree

**What it actually is.** Insert always walks right when a value is bigger. Feed it values that are already
in sorted order, and *every single insert* goes the same direction - the "tree" becomes a straight chain.

```python runnable
degenerate = BST()
for n in [10, 20, 30, 40, 50, 60, 70]:
    degenerate.insert(n)
print("degenerate height:", height(degenerate.root))
```
```console
degenerate height: 6
```
*What just happened:* same 7 values, same code, but sorted input means each new value is always bigger than
everything before it - it always becomes the new rightmost node's right child. The tree is now a chain 6
levels deep, and searching for `70` means walking through all 7 nodes one at a time. That's `O(n)`, no
better than [linear search](/guides/sorting-and-searching-explained) on a plain list - the tree structure
bought you nothing.

```mermaid
flowchart LR
  N10["10"] --> N20["20"] --> N30["30"] --> N40["40"] --> N50["50"] --> N60["60"] --> N70["70"]
```
*A binary search tree built from already-sorted input, drawn as what it actually is: a linked list with
extra steps.*

⚠️ **Gotcha.** A plain BST's speed depends entirely on insertion order, not just on the values themselves.
The same 7 numbers produce a fast `O(log n)` tree or a slow `O(n)` chain depending on nothing but the order
you handed them in - and sorted (or nearly sorted) input, which is common in real data, is the *worst* order
you could pick.

## The fix: self-balancing trees

**What it actually is.** A **self-balancing tree** (AVL trees, red-black trees) adds bookkeeping on every
insert: if one side ever grows too much taller than the other, it performs a **rotation** - a local
restructuring that shortens the tall side without breaking the ordering invariant. The result stays
`O(log n)` no matter what order you insert in.

You won't usually implement one by hand - production databases and language standard libraries already do
(Java's `TreeMap`, C++'s `std::map`, and database indexes are typically self-balancing trees under the
hood). What matters here is the intuition: **a plain BST is only as fast as its shape**, and that shape is
an accident of insertion order unless something actively corrects it.

## Recap

1. A BST is `O(log n)` when **balanced** - each subtree roughly half the size of its parent.
2. Inserting already-sorted (or nearly sorted) data can degrade a BST into a chain: `O(n)`, same as a linear
   scan.
3. The tree's speed depends on **insertion order**, not just which values it holds.
4. **Self-balancing trees** (AVL, red-black) fix this with rotations that keep the tree balanced automatically
   - the reason real-world sorted-map implementations stay fast regardless of insert order.

```quiz
[
  {
    "q": "Why does inserting values in already-sorted order produce a bad BST?",
    "choices": ["Sorted values can't be inserted at all", "Every insert goes the same direction, producing a straight chain instead of a branching tree", "It causes duplicate values", "It only affects search, not insert"],
    "answer": 1,
    "explain": "If every new value is bigger than everything before it, it always becomes the rightmost node's right child - height grows by one with every insert."
  },
  {
    "q": "What is the search cost on a degenerate (chain-shaped) BST with n nodes?",
    "choices": ["O(1)", "O(log n)", "O(n) - no better than a linear scan", "O(n²)"],
    "answer": 2,
    "explain": "A chain-shaped tree has to be walked one node at a time from the root to find a value near the end, which is the same cost as scanning a plain list."
  },
  {
    "q": "What do self-balancing trees (AVL, red-black) add to a plain BST?",
    "choices": ["Faster hardware requirements", "Automatic rotations on insert that keep the tree height roughly log(n) regardless of insertion order", "The ability to store duplicate values", "A requirement that all values be pre-sorted"],
    "answer": 1,
    "explain": "Rotations restructure the tree locally after an insert to prevent one side from growing too tall, guaranteeing O(log n) even on adversarial input order."
  }
]
```