Trees — Brief ☧

Deep version → | Lab → | Flashcards →

Q: Matthew 1 begins: "Abraham begat Isaac; and Isaac begat Jacob;

and Jacob begat Judah and his brethren." If you were to draw this

family line on a piece of parchment, what shape would it make?

A: You would put Abraham at the top, then draw lines down to his

children, then lines from each child to their children, and so on.

The result fans out like the branches of a great cedar. That shape is

a tree — one of the most fundamental

structures in computer science.

Q: What makes a tree different from any other

graph?

A: Three things:

There is exactly one starting point at the top, called the root (Abraham, in our example).

Every other person has exactly one parent — you can trace a single line upward from anyone back to the root.

There are no cycles — you can never follow the branches downward and end up back where you started.

If any of these rules were broken (say, two different parents for the

same person), it would be a general graph, not a tree.

Q: What do we call a person at the bottom who has no children?

A: A leaf. In the genealogy of Jesus (Matthew 1), Jesus himself

is a leaf — the final node in the lineage. Everyone between the root

and the leaves is an internal node. The depth of a node is how

many generations separate it from the root: Abraham is depth 0, Isaac

is depth 1, Jacob is depth 2, and so on.

Q: How do we search through a tree? Say we want to confirm that

David is an ancestor of Jesus.

A: Start at the root (Abraham) and walk downward, choosing which

branch to follow at each fork. This walking process is called **tree

traversal**. There are different orders you can visit the nodes:

Pre-order: visit the parent first, then the children (like reading a genealogy top-down).

In-order: visit left child, then parent, then right child (useful for sorted data in a binary tree).

Post-order: visit all children first, then the parent (like evaluating an expression from the leaves up).

Q: You mentioned "binary tree." What is that?

A: A tree where each node has at most two children — a left

child and a right child. Binary trees are especially important because

they enable binary search:

keep smaller values on the left, larger on the right, and you can find

any value in O(log N) steps —

halving the possibilities at each level, just like the scribe with the

sorted scroll in Big-O.

Q: How does this connect to our FPGA?

A: In miniKanren, every term is a cons tree: (cons car cdr).

Each cons cell has exactly two children — car (left) and cdr (right) —

making it a binary tree. The path through the tree — car, cdr, car,

car — becomes a binary encoding that our FPGA stores as a compact

bit string. Car = 0, Cdr = 1. Tree traversal is what the unification

engine does at every step.

The Genealogy Tree (Simplified)

          Abraham
          /     \
       Isaac    Ishmael
       /
     Jacob
    /    \
  Judah   Joseph
  /
 David
  |
 ...
  |
 Jesus

Root: Abraham (depth 0)
Internal nodes: Isaac, Jacob, Judah, David, ...
Leaves: Ishmael, Joseph, Jesus
Depth of Jesus: the number of generations from Abraham

Key Concepts

Term	Definition	Biblical Example
Root	Top node, no parent	Abraham
Leaf	Node with no children	Jesus (end of lineage)
Depth	Distance from root	David is depth 4 from Abraham
Binary tree	Each node has at most 2 children	Cons cells: car and cdr
Path	Sequence from root to a node	Abraham → Isaac → Jacob → Judah
Traversal	Systematic way to visit every node	Reading the genealogy in order

The key concept column tells you the vocabulary, but the FPGA connection column is where it gets practical. In miniKanren, every piece of data — every list, every pair, every nested structure — is stored as a tree of cons cells. The path from the root of that tree to any element can be encoded as a sequence of bits (0 for "go left" and 1 for "go right"), and the depth of the tree determines how many bits that path needs. This is why tree depth matters: deeper trees mean longer paths, which mean more bits to store and compare.

Trees are how miniKanren represents data. Every list [1, 2, 3] is

a tree of cons cells. Every pattern match walks this tree. Understanding tree structure is essential for understanding how unification works — because unification is, at its core, a simultaneous traversal of two trees, checking whether they can be made to match.

Learn more in the deep version

Related: Graphs | Hash Tables

Big-O Notation Unification

Soli Deo Gloria