Variants of the Binary Tree
Strict · Complete · Perfect · Extended · ThreadedA plain binary tree allows any shape. Special shapes have special names and special powers: strict trees never have a lonely child, complete trees fit in an array, perfect trees are completely full. An extended tree makes every empty spot visible, and a threaded tree reuses its NULL pointers so it can be walked in order without recursion or a stack. Type a tree, then check it against each definition.
- Strictevery node has 0 or 2 children
- Completefull levels, last level filled from the left
- Perfectall levels full: 2^(h+1) − 1 nodes
- Extendedempty spots become external nodes
- ThreadedNULL pointers point to inorder neighbours
- Strict–
- Complete–
- Perfect–
- Current
- In progress
- Checked / done
- New
- External node
- Right thread
- Left thread
- Breaks the rule
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Same nodes, special shapes
The variants are rules about the SHAPE of a binary tree: how many children each node has and how full the levels are. Strict, complete and perfect trees use the ordinary node. An extended tree adds placeholder (external) nodes for the empty spots. A threaded tree keeps the same shape but gives each node two flags, so a NULL pointer can be reused as a "thread" to the next node in inorder.
// An ordinary binary tree node
struct Node {
int data;
struct Node *left, *right;
};
// A threaded node: two flags say whether a pointer is a REAL child or a thread
struct TNode {
int data;
struct TNode *left, *right;
int lthread; // 1: left is a thread to the inorder predecessor
int rthread; // 1: right is a thread to the inorder successor
};
// Extended tree: every empty spot (NULL) becomes an external node
// (the squares in the picture). Internal nodes keep the data.
Strict (full / proper) tree
- Look at every node and count its children.
- Allowed: 0 children (a leaf) or 2 children.
- One node with exactly 1 child breaks the rule.
- Bonus: a strict tree has one more leaf than internal nodes (L = I + 1).
Complete tree
- Walk level by level with a queue; queue the empty spots too.
- The first empty spot sets gap = 1.
- After a gap, any real node means NOT complete.
- Complete trees fit in an array with no holes — that is how heaps work.
Perfect tree
- Count the nodes on every level.
- Level d must hold exactly 2^d nodes.
- All levels full means n = 2^(h+1) − 1 and 2^h leaves.
- Every perfect tree is also strict and complete.
Extended tree (2-tree)
- Walk the tree; wherever a child is missing, put an external node (a square).
- Now every real (internal) node has exactly 2 children.
- External nodes E = internal nodes I + 1.
- External path length = internal path length + 2I.
One-way (right) threaded tree
- Walk the tree in inorder and remember the previous node.
- If the previous node has no right child, its right pointer becomes a thread to the current node.
- Traverse: go to the leftmost node, then follow a thread or step into the right subtree.
- No recursion and no stack: O(1) extra space.
Two-way threaded tree
- Do the same, and ALSO reuse the null LEFT pointers.
- A null left pointer becomes a thread to the inorder predecessor.
- Now the tree can be walked forwards AND backwards in inorder.
- Cost: both flags (lthread, rthread) in every node.
How the shapes relate
- Perfect ⊂ complete, and perfect ⊂ strict.
- A complete tree may have ONE node with a single (left) child, so it need not be strict.
- A strict tree need not be complete: its leaves can sit on different levels.
- An extended tree is always strict (every internal node has 2 children).
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
n = number of nodes, h = height. A recursive traversal needs O(h) stack space; a threaded traversal needs O(1).
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Check strict | O(1) |
O(n) |
O(n) |
Grows with n |
| Check complete | O(1) |
O(n) |
O(n) |
Grows with n |
| Check perfect | O(n) |
O(n) |
O(n) |
Grows with n |
| Extend with external nodes | O(n) |
O(n) |
O(n) |
Grows with n |
| Thread a tree (one-way or two-way) | O(n) |
O(n) |
O(n) |
Grows with n |
| Inorder of a threaded tree (time) | O(n) |
O(n) |
O(n) |
Grows with n |
| Inorder of a threaded tree (extra space) | O(1) |
O(1) |
O(1) |
Instant |
The variants side by side
| Strict (full) | Complete | Perfect | Extended | |
|---|---|---|---|---|
| Rule | Every node has 0 or 2 children | Every level full except the last, which fills from the left | Every level completely full | Every empty spot is an external node |
| Nodes with exactly 1 child | None | At most one (the last internal node) | None | None |
| Number of nodes | Odd: n = 2I + 1, between 2h + 1 and 2^(h+1) − 1 | Between 2^h and 2^(h+1) − 1 | Exactly 2^(h+1) − 1 | I internal + (I + 1) external = 2I + 1 |
| Leaves | L = I + 1 | ⌈n / 2⌉ | 2^h | E = I + 1 (the external nodes) |
| Typical use | Expression trees, Huffman trees | Heaps, stored in an array | The ideal balanced shape | Analysis: path lengths, counting |
I = internal nodes, L = leaves, E = external nodes, h = height (a single node has h = 0).
One-way vs two-way threaded trees
| One-way (right) | Two-way (both) | |
|---|---|---|
| What a thread replaces | A NULL right pointer | A NULL right AND a NULL left pointer |
| A thread points to | The inorder successor | The inorder successor and the inorder predecessor |
| Walk forwards (inorder) | Yes — no stack | Yes — no stack |
| Walk backwards | No (a stack is needed) | Yes — no stack |
| Flags per node | 1 (rthread) | 2 (lthread, rthread) |
Recursive inorder vs threaded inorder
| Recursive inorder | Threaded inorder | |
|---|---|---|
| Time | O(n) | O(n) |
| Extra space | O(h) — the call stack | O(1) — none |
| Needs thread flags | No | Yes |
| Inserting a node | Simple | Harder: the threads must be updated |
Threading trades a little complexity (and a flag per pointer) for a traversal that needs no stack.
Check your understanding
Answer each question — you will see the explanation straight away.
Which binary tree has NO node with exactly one child?
In a strict (full / proper) binary tree every node has either 0 or 2 children.
A strict binary tree has 7 leaves. How many internal nodes does it have?
In a strict tree L = I + 1, so I = 7 − 1 = 6.
In a complete binary tree, how is the last level filled?
Every level except the last is full, and the last level is filled from the left with no empty spot before a node.
A perfect binary tree has height 3 (the root is on level 0). How many nodes does it have?
2^(h+1) − 1 = 2^4 − 1 = 15: levels of 1, 2, 4 and 8 nodes.
Is every perfect binary tree also a complete binary tree?
Every level of a perfect tree is full, so there is no gap anywhere: it is complete (and strict) too.
An extended binary tree has 9 internal nodes. How many external nodes does it have?
E = I + 1 = 10: every empty spot of the original tree became an external node.
In a one-way (right) threaded binary tree, what does a thread replace?
A node with no right child reuses that NULL pointer as a thread to the next node in inorder, so the pointer is not wasted.
Why can a threaded tree be traversed in inorder without recursion or a stack?
Instead of going back up through parents (which needs a stack), a thread jumps directly to the inorder successor.
Which tree variant can be stored in an array with no wasted slots?
A complete tree has no gaps, so the children of the node at index i sit at 2i + 1 and 2i + 2. This is exactly how a heap is stored.
Trees quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.