# Why Trees Matter

### Trees

A tree is a collection made of nodes.

Each node can point to other nodes.

The first node is called the root.

```text
        10
       /  \
      5    20
     / \
    2   7
```

This tree has one root:

```text
10
```

The root has two children:

```text
5 and 20
```

Node `5` also has two children:

```text
2 and 7
```

A node with no children is called a leaf.

```text
2, 7, and 20
```

## Why Trees Matter

Trees are useful when data has hierarchy.

Examples:

```text
file systems
HTML documents
JSON values
syntax trees
decision trees
indexes
menus
organization charts
```

A file system is a tree:

```text
/
├── home
│   └── user
│       └── notes.txt
└── tmp
```

A parser often builds a tree:

```text
    +
   / \
  1   *
     / \
    2   3
```

That tree represents:

```text
1 + 2 * 3
```

## A Basic Tree Node

Here is a simple binary tree node:

```zig
const Node = struct {
    value: i32,
    left: ?*Node,
    right: ?*Node,
};
```

This node stores:

```text
a value
an optional pointer to the left child
an optional pointer to the right child
```

The type `?*Node` means:

```text
maybe a pointer to a Node
```

If there is no child, the pointer is `null`.

## Building a Small Tree

```zig
const std = @import("std");

const Node = struct {
    value: i32,
    left: ?*Node,
    right: ?*Node,
};

pub fn main() void {
    var n2 = Node{ .value = 2, .left = null, .right = null };
    var n7 = Node{ .value = 7, .left = null, .right = null };
    var n20 = Node{ .value = 20, .left = null, .right = null };

    var n5 = Node{ .value = 5, .left = &n2, .right = &n7 };
    var root = Node{ .value = 10, .left = &n5, .right = &n20 };

    printTree(&root);
}

fn printTree(node: ?*const Node) void {
    if (node) |n| {
        std.debug.print("{}\n", .{n.value});
        printTree(n.left);
        printTree(n.right);
    }
}
```

Output:

```text
10
5
2
7
20
```

This function:

```zig
fn printTree(node: ?*const Node) void
```

takes an optional pointer to a constant `Node`.

The tree walk is recursive:

```zig
printTree(n.left);
printTree(n.right);
```

Each node prints itself, then asks its children to do the same.

## Tree Traversal

Traversal means visiting every node.

For this tree:

```text
        10
       /  \
      5    20
     / \
    2   7
```

There are several common orders.

Preorder:

```text
10, 5, 2, 7, 20
```

Visit node first, then left, then right.

```zig
fn preorder(node: ?*const Node) void {
    if (node) |n| {
        std.debug.print("{}\n", .{n.value});
        preorder(n.left);
        preorder(n.right);
    }
}
```

Inorder:

```text
2, 5, 7, 10, 20
```

Visit left, then node, then right.

```zig
fn inorder(node: ?*const Node) void {
    if (node) |n| {
        inorder(n.left);
        std.debug.print("{}\n", .{n.value});
        inorder(n.right);
    }
}
```

Postorder:

```text
2, 7, 5, 20, 10
```

Visit children first, then node.

```zig
fn postorder(node: ?*const Node) void {
    if (node) |n| {
        postorder(n.left);
        postorder(n.right);
        std.debug.print("{}\n", .{n.value});
    }
}
```

## Binary Search Trees

A binary search tree is a binary tree with an ordering rule.

For every node:

```text
left values are smaller
right values are larger
```

Example:

```text
        10
       /  \
      5    20
     / \
    2   7
```

For root `10`:

```text
5, 2, 7 are smaller than 10
20 is larger than 10
```

For node `5`:

```text
2 is smaller than 5
7 is larger than 5
```

This rule makes search possible.

## Searching a Binary Search Tree

```zig
fn contains(node: ?*const Node, target: i32) bool {
    if (node) |n| {
        if (target == n.value) return true;

        if (target < n.value) {
            return contains(n.left, target);
        } else {
            return contains(n.right, target);
        }
    }

    return false;
}
```

If the target is smaller than the current node, search left.

If it is larger, search right.

This avoids checking every node when the tree is balanced.

## Inserting into a Binary Search Tree

For a mutable tree, insertion follows the same rule.

```zig
fn insert(root: *?*Node, new_node: *Node) void {
    if (root.*) |node| {
        if (new_node.value < node.value) {
            insert(&node.left, new_node);
        } else {
            insert(&node.right, new_node);
        }
    } else {
        root.* = new_node;
    }
}
```

The parameter is:

```zig
root: *?*Node
```

This means:

```text
a pointer to an optional node pointer
```

That looks strange at first.

We need it because insertion may change a `null` child pointer into a real node pointer.

Example:

```zig
var root: ?*Node = null;
insert(&root, node);
```

The function receives `&root`, so it can modify `root`.

## Heap-Allocated Tree Nodes

Real trees often allocate nodes on the heap.

```zig
const std = @import("std");

const Node = struct {
    value: i32,
    left: ?*Node,
    right: ?*Node,
};

fn createNode(allocator: std.mem.Allocator, value: i32) !*Node {
    const node = try allocator.create(Node);
    node.* = Node{
        .value = value,
        .left = null,
        .right = null,
    };
    return node;
}
```

Using it:

```zig
const n = try createNode(allocator, 10);
```

Later, you must free the node.

## Freeing a Tree

To free a whole tree, use postorder traversal.

Free the children first.

Then free the node.

```zig
fn destroyTree(allocator: std.mem.Allocator, node: ?*Node) void {
    if (node) |n| {
        destroyTree(allocator, n.left);
        destroyTree(allocator, n.right);
        allocator.destroy(n);
    }
}
```

This order matters.

If you destroyed the current node first, you could no longer safely read `n.left` or `n.right`.

## Complete Binary Search Tree Example

```zig
const std = @import("std");

const Node = struct {
    value: i32,
    left: ?*Node,
    right: ?*Node,
};

fn createNode(allocator: std.mem.Allocator, value: i32) !*Node {
    const node = try allocator.create(Node);
    node.* = Node{
        .value = value,
        .left = null,
        .right = null,
    };
    return node;
}

fn insert(root: *?*Node, new_node: *Node) void {
    if (root.*) |node| {
        if (new_node.value < node.value) {
            insert(&node.left, new_node);
        } else {
            insert(&node.right, new_node);
        }
    } else {
        root.* = new_node;
    }
}

fn contains(node: ?*const Node, target: i32) bool {
    if (node) |n| {
        if (target == n.value) return true;

        if (target < n.value) {
            return contains(n.left, target);
        } else {
            return contains(n.right, target);
        }
    }

    return false;
}

fn destroyTree(allocator: std.mem.Allocator, node: ?*Node) void {
    if (node) |n| {
        destroyTree(allocator, n.left);
        destroyTree(allocator, n.right);
        allocator.destroy(n);
    }
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    var root: ?*Node = null;
    defer destroyTree(allocator, root);

    const values = [_]i32{ 10, 5, 20, 2, 7 };

    for (values) |value| {
        const node = try createNode(allocator, value);
        insert(&root, node);
    }

    std.debug.print("{}\n", .{contains(root, 7)});
    std.debug.print("{}\n", .{contains(root, 99)});
}
```

Output:

```text
true
false
```

This example shows several important Zig ideas together:

```text
optional pointers
heap allocation
recursive functions
explicit cleanup
pointer-to-optional mutation
```

## Balanced and Unbalanced Trees

A binary search tree is fast only when it is balanced.

Balanced:

```text
        8
      /   \
     4     12
    / \   /  \
   2   6 10  14
```

Unbalanced:

```text
1
 \
  2
   \
    3
     \
      4
       \
        5
```

The unbalanced tree behaves like a linked list.

Searching may require walking through every node.

This is why production tree structures often use balancing rules.

Examples include:

```text
AVL trees
red-black trees
B-trees
B+ trees
tries
```

## Trees vs Hash Maps

A hash map gives fast lookup by key, but it does not keep sorted order.

A tree can keep items ordered.

| Structure | Lookup | Ordered iteration |
|---|---:|---:|
| `HashMap` | Usually very fast | No |
| Binary search tree | Depends on balance | Yes |
| Balanced tree | Fast | Yes |

Use a hash map when you want direct lookup.

Use a tree when order and range queries matter.

## Common Beginner Mistakes

The first mistake is forgetting that a tree node can be `null`.

That is why child pointers are usually optional:

```zig
left: ?*Node
right: ?*Node
```

The second mistake is freeing a node before reading its children. Save or process children first.

The third mistake is assuming every binary search tree is fast. A badly ordered insertion sequence can create a long chain.

The fourth mistake is making ownership unclear. Decide whether the tree owns its nodes. If it does, the tree must destroy them.

## A Useful Mental Model

A tree is a root with branches.

Each branch leads to smaller trees.

```text
        root
       /    \
  subtree  subtree
```

This recursive shape is why recursive functions fit trees so naturally.

A node contains data and links to child nodes.

A tree is either empty or a node with children.

## Summary

A tree stores hierarchical data.

A binary tree has at most two children per node.

A binary search tree adds an ordering rule:

```text
left < node < right
```

Trees are useful for hierarchy, parsing, searching, indexing, and ordered data.

In Zig, tree code teaches optional pointers, recursion, heap allocation, ownership, and careful destruction.