Neel Mishra
← All Posts
DSA Series · Trees · Threaded · Part 1

Threaded Binary Trees: Introduction

March 2026 · 8 min read

Why Threaded Trees?

In a standard binary tree, more than half of all pointer fields are null, wasted memory doing nothing. A threaded binary tree replaces these null pointers with threads: pointers to the in-order predecessor or successor. This enables $O(1)$ space in-order traversal without a stack or recursion.

But how do we know exactly how many null pointers exist? Let's derive it rigorously.

The Null Pointer Problem

Setup

In a binary tree, every node has exactly two pointer fields: left and right. Some point to children, the rest are null. Let's count precisely how many are null.

Let $n$ = total number of nodes in the tree.

Step 1: Count Total Pointer Fields

Since every node has exactly 2 pointer fields (left and right):

$$\text{Total pointer fields} = 2n$$

Step 2: Count Non-Null Pointers (Edges)

A non-null pointer is one that actually points to a child node, in other words, it represents an edge in the tree.

Key observation: every node except the root has exactly one parent pointing to it. The root has no parent. Therefore:

$$\text{Number of edges} = n - 1$$

Each edge corresponds to exactly one non-null pointer field (the parent's left or right pointer that points to this child). So:

$$\text{Non-null pointers} = n - 1$$

Step 3: Count Null Pointers

Null pointers = Total pointers − Non-null pointers:

$$\text{Null pointers} = 2n - (n - 1) = 2n - n + 1 = n + 1$$
Theorem: A binary tree with $n$ nodes has exactly $n + 1$ null pointers.

Fraction Wasted

The fraction of pointer fields that are null:

$$\frac{n + 1}{2n} = \frac{1}{2} + \frac{1}{2n}$$

As $n \to \infty$, this approaches $\frac{1}{2}$, meaning roughly half of all memory allocated for pointers is wasted. For small trees, it's even worse.

Alternative Derivation (by Node Type)

We can verify this by classifying nodes. Let:

Total null pointers:

$$N_{\text{null}} = 2n_0 + n_1$$

We also know from tree theory that in any binary tree:

$$n_0 = n_2 + 1$$

(the number of leaves is always one more than the number of degree-2 nodes). Substituting:

$$N_{\text{null}} = 2n_0 + n_1 = 2(n_2 + 1) + n_1 = 2n_2 + 2 + n_1$$

Since $n = n_0 + n_1 + n_2$ and $n_0 = n_2 + 1$:

$$n = (n_2 + 1) + n_1 + n_2 = 2n_2 + n_1 + 1$$ $$\therefore\; 2n_2 + n_1 = n - 1$$

Substituting back:

$$N_{\text{null}} = (n - 1) + 2 = n + 1 \;\; \checkmark$$

Both derivations agree.

Concrete Example

Consider a binary tree with 7 nodes:

4 2 6 1 3 5 7 null null null null null null null null
7 nodes → 14 pointer fields total. 8 are null ($n+1 = 8$). That's $\frac{8}{14} \approx 57\%$ waste!

Verification for this tree:

The problem: $n + 1$ pointer fields sit as nullptr, storing no useful information. That's $(n+1) \times 8$ bytes on a 64-bit system doing absolutely nothing. Threaded trees repurpose these pointer fields to store useful traversal links instead.

Types of Threading

Single Threaded (Right-Threaded)

The most common variant. Null right pointers are replaced with threads to the in-order successor.

4 2 6 1 3 5 7 Dashed orange = threads to in-order successor
Right-threaded BST: 1→2, 3→4, 5→6. Node 7's right is null (no successor).

Double Threaded

Both null left and right pointers are threaded:

Node Structure

Each node needs a boolean flag to distinguish a real child pointer from a thread:

struct ThreadedNode {
    int val;
    ThreadedNode* left;
    ThreadedNode* right;
    bool leftThread;   // true = left points to predecessor
    bool rightThread;  // true = right points to successor

    ThreadedNode(int v)
        : val(v), left(nullptr), right(nullptr),
          leftThread(true), rightThread(true) {}
};

Wait: Doesn't This Add Memory?

Sharp observation. The null pointer fields don't disappear, the left and right pointers are still there. What changes is their content: instead of storing nullptr (useless), they now store a pointer to the in-order predecessor or successor (useful). And we add two boolean flags on top. So what's the real tradeoff?

The Honest Accounting

Standard TreeThreaded Tree
Pointer fields per node2 (many are nullptr)2 (none are nullptr, all point somewhere useful)
Extra storage per node02 booleans ($\approx$ 2 bytes, or 2 bits with bit-packing)
Traversal auxiliary space$O(h)$, stack or recursion$O(1)$, no stack needed
Find in-order successor$O(h)$ worst case$O(1)$ amortized

So the per-node cost is $2n$ extra bytes (or $\frac{n}{4}$ bytes with bit-packing). But the real gain is algorithmic, not memory:

Can We Avoid the Booleans Entirely?

Yes. Some implementations use tag bits, stealing the lowest bit of the pointer itself. Since pointers are aligned to even addresses on most architectures, the lowest bit is always 0 for a real pointer. Setting it to 1 signals "this is a thread." This makes the overhead literally zero extra bytes, at the cost of masking the bit on every pointer access.

Bottom line: Threaded trees don't save memory by removing pointers, the pointer fields are still there. What they do is repurpose $n + 1$ useless nullptr values into useful traversal links, at the cost of 2 boolean flags per node. The real payoff is algorithmic: $O(1)$ space traversal and $O(1)$ successor lookup.

Comparison with Standard Trees

Feature Standard Binary Tree Threaded Binary Tree
In-order traversal$O(n)$ time, $O(h)$ space (stack)$O(n)$ time, $O(1)$ space
Find successor$O(h)$ worst case$O(1)$ amortized
Find predecessor$O(h)$ worst case$O(1)$ (double threaded)
Insert complexityStandard BST insertSlightly more complex (maintain threads)
Null pointer fields$n + 1$ storing nullptr$0$, all repurposed as threads
Extra storage per nodeNone2 boolean flags (eliminable via tag bits)

Summary