Binary Trees, From Links to Traversals

This is the plain version of the red-black tree tutorial. Before colors, rotations, and repair cases, there is the smaller idea: a node may point to a left child and a right child. That is enough structure to support many algorithms, but not enough to promise balance or search order.

The demo below uses the same setup as the red-black tree entry. XState owns the tutorial state. Phaser renders the current snapshot. Press Random to generate a new set of labels, then step through insertion and traversal without adding any balancing rules.

Jump to the interactive tree.

What a binary tree promises

A binary tree promises only arity. Each node has at most two children. The children are named left and right because position matters, not because the left value must be smaller than the parent. That distinction is easy to miss if your first tree is a binary search tree.

With no ordering invariant, values are just labels. You can store numbers, strings, syntax tokens, or decision states. The useful information is the shape: which nodes are parents, which nodes are siblings, and which paths lead from the root to leaves.

Insertion needs a policy

A regular binary tree does not tell you where the next node belongs. The tutorial uses level-order insertion: fill the root, then the left child, then the right child, then continue one level down from left to right. This is a policy for the demo, not a universal rule for binary trees.

That is the main contrast with the red-black tree tutorial. Red-black insertion starts with binary-search placement and then repairs color invariants. Plain binary insertion only attaches a node to an available child slot. No rotation is waiting afterward.

Traversal gives the shape a sequence

Once the links exist, algorithms often need a sequence. Pre-order visits a node before its children. In-order visits the left subtree, then the node, then the right subtree. Post-order visits children before the node. Level-order reads breadth first.

None of those traversals changes the tree. They are different lenses over the same structure. In a binary search tree, in-order traversal has a special property because it returns sorted values. In a regular binary tree, it is just one consistent walk among several.

Why the state machine still helps

The state machine is simpler here, but it still earns its place. Empty, attach root, attach left, attach right, built, then traversal states. Each state has one explanation and one snapshot. That keeps the animation honest instead of letting the renderer imply rules the data structure does not have.

That matters for teaching. A binary tree is not a weak red-black tree. It is a more general shape. Starting here makes the later constraints easier to see because every added rule has to pay rent.

What to watch for

Step through the insertion phase first and ignore the numbers. Watch only child slots. Then step through traversal and watch how the highlighted node moves while the links stay fixed. That separation is the foundation for search trees, heaps, expression trees, and balanced trees.