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.

This tree has one root:

The root has two children:

5 and 20

Node 5 also has two children:

2 and 7

A node with no children is called a leaf.

2, 7, and 20

Why Trees Matter

Trees are useful when data has hierarchy.

Examples:

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

A file system is a tree:

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

A parser often builds a tree:

That tree represents:

1 + 2 * 3

A Basic Tree Node

Here is a simple binary tree node:

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

This node stores:

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

The type ?*Node means:

maybe a pointer to a Node

If there is no child, the pointer is null.

Building a Small Tree

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:

This function:

fn printTree(node: ?*const Node) void

takes an optional pointer to a constant Node.

The tree walk is recursive:

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:

There are several common orders.

Preorder:

10, 5, 2, 7, 20

Visit node first, then left, then right.

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

Inorder:

2, 5, 7, 10, 20

Visit left, then node, then right.

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

Postorder:

2, 7, 5, 20, 10

Visit children first, then node.

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:

left values are smaller
right values are larger

Example:

For root 10:

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

For node 5:

2 is smaller than 5
7 is larger than 5

This rule makes search possible.

Searching a Binary Search Tree

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.

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:

root: *?*Node

This means:

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:

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.

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:

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.

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

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:

true
false

This example shows several important Zig ideas together:

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:

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

Unbalanced:

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:

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:

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.

        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:

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.