Binary Trees

Motivation (why this concept exists)

When you first learn “trees,” the number of children a node can have is usually unconstrained: a node may have 0, 1, 2, 10… children. Many algorithms and data structures become simpler and faster when you restrict the shape.

A binary tree is the most common restriction: each node has at most two children. That might seem arbitrary, but it buys you:

• •Simple recursive structure: problems split into “solve left subtree” and “solve right subtree.”
• •Clear, ordered positions: “left child” and “right child” are distinct roles.
• •Compact array representations for special cases (e.g., complete trees → heaps).

Definition

A binary tree is a rooted tree where each node has at most two children, and the two child positions are ordered.

There are three atomic ideas to keep in your head:

1. 1)At-most-two-children: a node can have 0, 1, or 2 children.
2. 2)Ordered children: the two slots are distinct: left vs right. Swapping them generally changes the tree.
3. 3)Recursive definition: a binary tree is either empty or a node whose left and right are themselves binary trees.

A common formal recursive definition is:

• •A binary tree is either empty (represented by NULL), or
• •A node containing a value and two pointers: left and right, each pointing to a binary tree (or NULL).

In pseudocode, a node is often modeled as:

Node {
  value
  left  // Node or NULL
  right // Node or NULL
}

A diagram you should be able to “read”

The key visualization: each node has two labeled outgoing edges (slots), and NULL is meaningful.

Here is an inline static SVG diagram labeling left/right pointers and NULL slots:

<svg width="650" height="220" viewBox="0 0 650 220" xmlns="http://www.w3.org/2000/svg">
  <style>
    .node { fill: #fff; stroke: #111; stroke-width: 2; }
    .null { fill: #f6f6f6; stroke: #666; stroke-width: 2; stroke-dasharray: 5 4; }
    .lbl { font: 14px sans-serif; fill: #111; }
    .small { font: 12px sans-serif; fill: #333; }
    .edge { stroke: #111; stroke-width: 2; }
    .dedge { stroke: #666; stroke-width: 2; stroke-dasharray: 5 4; }
  </style>

  <!-- root -->
  <circle class="node" cx="325" cy="40" r="22" />
  <text class="lbl" x="325" y="45" text-anchor="middle">A</text>

  <!-- left child -->
  <circle class="node" cx="220" cy="110" r="22" />
  <text class="lbl" x="220" y="115" text-anchor="middle">B</text>

  <!-- right child (NULL) -->
  <rect class="null" x="410" y="88" width="60" height="44" rx="8" />
  <text class="small" x="440" y="115" text-anchor="middle">NULL</text>

  <!-- B's children -->
  <rect class="null" x="155" y="160" width="60" height="44" rx="8" />
  <text class="small" x="185" y="187" text-anchor="middle">NULL</text>

  <circle class="node" cx="285" cy="182" r="22" />
  <text class="lbl" x="285" y="187" text-anchor="middle">C</text>

  <!-- edges -->
  <line class="edge" x1="310" y1="58" x2="236" y2="95" />
  <line class="dedge" x1="340" y1="58" x2="410" y2="95" />

  <line class="dedge" x1="205" y1="128" x2="185" y2="160" />
  <line class="edge" x1="235" y1="128" x2="270" y2="165" />

  <!-- labels for slots -->
  <text class="small" x="265" y="78" text-anchor="middle">left</text>
  <text class="small" x="385" y="78" text-anchor="middle">right</text>

  <text class="small" x="175" y="150" text-anchor="middle">left</text>
  <text class="small" x="260" y="150" text-anchor="middle">right</text>
</svg>

Read it like this:

• •Node A has:
• •A.left = B
• •A.right = NULL
• •Node B has:
• •B.left = NULL
• •B.right = C

Notice how “having one child” still means you must decide which slot is used. A node with only a right child is different from a node with only a left child.

Ordered children means swapping changes the tree

If you swap every left and right pointer, you get the tree’s mirror image. In general, the original tree and its mirror are not the same binary tree (even if they contain the same values).

This is a major difference from some “un-ordered” tree models where children are just a set/list without named positions.

Why recursion fits perfectly

Binary trees are defined in terms of smaller binary trees. That means many algorithms naturally look like:

1. 1)Handle the empty tree (NULL)
2. 2)Solve for the left subtree
3. 3)Solve for the right subtree
4. 4)Combine results

This is not just programming convenience—it’s a direct consequence of the definition.

The recursive definition (made explicit)

Let $T$ be a binary tree. Then:

• •$T = \text{NULL}$ (empty), or
• •$T = (value, left, right)$ where left and right are binary trees.

If you like, you can think of a node as a 3-tuple:

where $T_L$ is the left subtree and $T_R$ is the right subtree, and either may be empty (NULL).

NULL is not “nothing”; it’s part of the shape

A common beginner mistake is to treat “missing child pointers” as irrelevant. But for binary trees, NULL is what makes the recursive definition work cleanly and what makes many representations unambiguous.

Example: Suppose we want to count nodes.

Let size(T) be the number of non-NULL nodes in tree T.

We define:

• •If $T = \text{NULL}$, then size(T) = 0.
• •Otherwise, if $T$ has root with left $L$ and right $R$:

That “0 for NULL” is the base case that stops recursion.

Height and depth (and why people mix them up)

Two related measures:

• •Depth of a node: number of edges from the root to that node.
• •Height of a tree: number of edges on the longest path from the root down to a leaf.

Conventions vary: sometimes height counts nodes instead of edges. Pick one and be consistent.

A recursive height definition (edge-counting) is:

• •height(NULL) = -1 (so a leaf node has height 0)
• •height(node) = 1 + max(height(left), height(right))

This choice is nice because it makes the math clean.

Interactive-canvas suggestion (visualization focus)

If you’re building or using an interactive canvas for this node, add a toggle that:

• •Shows left/right pointers as two fixed slots per node
• •Draws NULL markers explicitly (e.g., dashed boxes labeled NULL)
• •Lets learners toggle traversal animations:
• •Preorder (N-L-R)
• •Inorder (L-N-R)
• •Postorder (L-R-N)
• •Lets learners toggle a “serialize with NULLs” mode, so they can see output change when NULLs are omitted vs included

A crucial demonstration:

• •Two different trees can produce the same traversal output if you omit NULL markers.
• •Adding NULL markers (or parentheses structure) makes the serialization unambiguous.

For example, preorder without NULLs:

• •Tree 1: A with left child B
• •Tree 2: A with right child B

Both produce preorder sequence: A, B.

But preorder with NULL markers distinguishes them:

• •Tree 1: A, B, NULL, NULL, NULL
• •Tree 2: A, NULL, B, NULL, NULL

That difference is exactly “ordered child positions + base case.”

Why traversals matter

A traversal is a rule for visiting every node exactly once. Traversals are how we:

• •Print or serialize trees
• •Evaluate expression trees
• •Implement many algorithms cleanly

Binary trees have especially standard traversals because “left vs right” gives a built-in order.

The three depth-first traversals

Assume a node N with left subtree L and right subtree R.

You can write them recursively. For preorder:

preorder(T):
  if T == NULL: return
  visit(T.root)
  preorder(T.left)
  preorder(T.right)

Inorder:

inorder(T):
  if T == NULL: return
  inorder(T.left)
  visit(T.root)
  inorder(T.right)

Postorder:

postorder(T):
  if T == NULL: return
  postorder(T.left)
  postorder(T.right)
  visit(T.root)

Breathing room: what changes between these?

Only one thing: when you visit the node relative to its subtrees.

But that one thing changes the meaning:

• •Preorder: good for “copying” a tree structure (especially with NULL markers), or prefix notation.
• •Inorder: special for binary search trees (it yields sorted order). For a general binary tree, it’s just a consistent left-to-right listing.
• •Postorder: useful for deleting/freeing nodes, evaluating expression trees in postfix order.

Traversals + NULL markers = serialization

If your goal is to reconstruct the exact tree shape later, you typically must record NULLs (or use parentheses).

A common preorder-with-NULL serialization scheme:

serialize(T):
  if T == NULL: output "NULL"; return
  output T.value
  serialize(T.left)
  serialize(T.right)

This produces a sequence that uniquely identifies the tree (given ordered child slots).

BFS / level-order (bonus, but common)

Level-order traversal visits nodes by depth: root, then all depth-1 nodes left-to-right, then depth-2, etc. This is typically implemented with a queue.

While not part of the classic “three DFS traversals,” level-order is heavily used in heaps and in array representations.

Visualization note for the interactive canvas

To improve intuition, the canvas should animate a moving “cursor”:

• •Highlight current node
• •Show a call stack panel (or recursion depth) as you traverse
• •In “include NULLs” mode, the animation should also step into missing children and emit a NULL token

Learners should be able to watch preorder vs inorder vs postorder produce different sequences from the same static shape.

Representation 1: Pointer-based nodes (general binary trees)

The most general representation uses explicit nodes with left/right pointers.

Pros:

• •Supports any shape (sparse trees, skewed trees)
• •Easy to mutate locally

Cons:

• •Memory overhead per node (pointers)
• •Cache locality can be worse than arrays

Representation 2: Array-based (works best for complete trees)

If a binary tree is complete (all levels filled except maybe the last, filled left-to-right), you can store it compactly in an array.

Using 1-based indexing:

• •Node at index $i$
• •Left child at $2i$
• •Right child at $2i + 1$
• •Parent at $\lfloor i/2 \rfloor$

This is the key trick behind heaps.

If the tree is sparse, the array representation wastes space because you’d need many NULL slots.

Heaps and BSTs: what binary trees unlock

Binary trees are the “host structure.” Additional rules turn them into specialized data structures:

Binary trees are not automatically fast. A badly shaped (skewed) BST can degrade to a chain with $O(n)$ operations. That’s why shape and invariants matter.

A small but important conceptual bridge

• •Binary tree is about shape + left/right order + NULL base case.
• •BST is about adding a value ordering invariant on top of the binary tree.
• •Heap is about adding a shape constraint (complete) and a parent/child priority invariant.

So this node is the “shape vocabulary” you need before learning those invariants.