See how unused NULL links become useful predecessor and successor pointers. Learn single and double threading, forward and reverse Inorder Traversal, and tested C code with simple examples.
What Is a Threaded Binary Tree in Data Structure?
In a normal Binary Tree, each node normally has a left pointer and a right pointer. But many of these pointers are NULL because a node may not have both children. What if we use some of these empty pointers to help us visit the next node?
A predecessor means the node visited immediately before the current node. A successor means the node visited immediately after it. Both words are based on the chosen traversal order.
Binary Tree Diagram Before Adding Threads
We will use these seven values: 40, 20, 60, 10, 30, 25 and 70. Notice that node 30 has only a left child, while node 60 has only a right child. These missing links make the example useful for understanding threading.
-
40
-
20
- 10
-
30
- 25
-
60
- 70
-
20
For this original tree, the traversal orders are:
Inorder (Left, Root, Right)
10 → 20 → 25 → 30 → 40 → 60 → 70
Preorder / Postorder
Preorder: 40, 20, 10, 30, 25, 60, 70
Postorder: 10, 25, 30, 20, 70, 60, 40
How Many NULL Child Pointers Does It Have?
Seven nodes have 14 child-pointer fields in total. A non-empty tree with seven nodes has six real parent-to-child edges, so 14 − 6 = 8 NULL positions. In general, a Binary Tree with n nodes has n + 1 NULL child-pointer positions. Threading can reuse some or all of these positions.
Types of Threaded Binary Trees
Threaded trees can be classified in two useful ways: which pointer is threaded and which traversal order defines the threads. The most common classroom example is Inorder Threading.
1. Left-Threaded Binary Tree
If a left child is missing, its left pointer can refer to its Inorder predecessor. Right pointers continue to represent ordinary right children in a left-only threaded design.
2. Right-Threaded Binary Tree
If a right child is missing, its right pointer can refer to its Inorder successor. This is especially useful for forward Inorder traversal.
3. Double-Threaded Binary Tree
Both missing left and missing right child links may become threads: left points to the predecessor and right points to the successor. This supports forward and reverse Inorder traversal.
4. Based on Traversal Order
Threads may be defined using Inorder, Preorder or Postorder relationships. The same link must always be interpreted according to the chosen type.
| Type | Unused Left Pointer | Unused Right Pointer | Usual Goal |
|---|---|---|---|
| Left-threaded (Inorder) | Predecessor thread | NULL if no child | Backward links |
| Right-threaded (Inorder) | NULL if no child | Successor thread | Forward links |
| Double-threaded (Inorder) | Predecessor thread | Successor thread | Forward and backward |
| Preorder / Postorder threaded | Threads refer to predecessor/successor in the named traversal; traversal algorithms differ | Order-specific navigation | |
Threaded Binary Tree Node Structure: lthread and rthread
Because a pointer may mean either
a real child or a
thread,
we need extra flags (tags).
In our C program, we use
lthread and
rthread.
Some textbooks use the opposite bit convention. Always read the definitions in the given question or program. The code below consistently uses 1 for a thread.
Double-Threaded Binary Tree Example with Pointer Diagram
Inorder is 10, 20, 25, 30, 40, 60, 70. We attach a thread only where a real child pointer was originally NULL. Real child links remain unchanged.
These shortcut arrows are not new child edges. For example, 30's right pointer points to 40 as a thread, even though 40 is an ancestor rather than 30's child.
| Node | Left Pointer | LTag | Right Pointer | RTag |
|---|---|---|---|---|
| 10 | THREAD → NULL | 1 | THREAD → 20 | 1 |
| 20 | CHILD → 10 | 0 | CHILD → 30 | 0 |
| 25 | THREAD → 20 | 1 | THREAD → 30 | 1 |
| 30 | CHILD → 25 | 0 | THREAD → 40 | 1 |
| 40 | CHILD → 20 | 0 | CHILD → 60 | 0 |
| 60 | THREAD → 40 | 1 | CHILD → 70 | 0 |
| 70 | THREAD → 60 | 1 | THREAD → NULL | 1 |
How to Create Inorder Threads Step by Step
One straightforward method starts
with an ordinary linked Binary Tree.
Perform a normal recursive Inorder
walk once, maintaining
a pointer previous
to the most recently visited node.
-
Start
previous = NULLand visit the far-left node 10 first. -
If the current node has no real left
child, change its left link into a thread
pointing to
previous. -
If
previousexists and its right child is missing, make its right pointer thread to the current node. -
Update
previous = currentand continue the Inorder walk. - At the end, the right thread of last node 70 points to NULL, because it has no successor.
previous is 20.
Since 25 has no left child,
set 25's left thread to 20.
Since node 20 already has a real
right child 30, its right link is
not changed into a thread.
The conversion itself uses recursion in the demonstrated program. The benefit of threading appears during later traversals, when we can walk Inorder without using a separate recursion stack.
Inorder Traversal of Threaded Binary Tree without Stack or Recursion
For a double Inorder-threaded tree, first reach the leftmost real node. Then repeatedly follow one of two rules to get the next node.
Right tag = 0 → enter real right subtree, then go leftmost
- Start at root 40 and follow real left-child pointers 40 → 20 → 10. Visit 10.
- 10 has right thread to 20. Follow it and visit 20.
- 20 has real right child 30. Enter 30's subtree, then go left to 25. Visit 25.
- 25 has a right thread to 30. Visit 30.
- 30 has a right thread to 40. Visit 40.
- 40 has real right child 60. That subtree's leftmost real node is 60. Visit 60.
- 60 has real right child 70. Visit 70. Its right thread is NULL, so stop.
| Visited Node | How to Reach Next? | Next Node |
|---|---|---|
| 10 | Right thread | 20 |
| 20 | Real right child 30, then leftmost | 25 |
| 25 | Right thread | 30 |
| 30 | Right thread | 40 |
| 40 | Real right child 60, then leftmost | 60 |
| 60 | Real right child 70, then leftmost | 70 |
| 70 | Right thread → NULL | Stop |
Inorder Traversal Pseudocode
current = LEFTMOST(root)
WHILE current is not NULL
VISIT(current)
IF current.rthread == 1
current = current.right
ELSE
current = LEFTMOST(current.right)
Reverse Inorder Traversal in a Double-Threaded Binary Tree
Reverse Inorder visits nodes in Right → Root → Left order. Because double threading also stores predecessor links, we can walk backward without a separate stack.
Left tag = 0 → enter real left subtree, then go rightmost
Start at the rightmost node 70. Its left thread takes us to 60. Node 60's left thread takes us to 40. Node 40 has a real left subtree rooted at 20, whose rightmost node is 30. Continue similarly.
current = RIGHTMOST(root)
WHILE current is not NULL
VISIT(current)
IF current.lthread == 1
current = current.left
ELSE
current = RIGHTMOST(current.left)
Preorder and Postorder Threaded Binary Tree Traversal
Threading is not restricted to Inorder. You can design threads around another traversal, but you must use its correct predecessor/successor rules.
Preorder Threading
Order: Root → Left → Right. For our tree: 40, 20, 10, 30, 25, 60, 70. A missing pointer may be used to store the next/previous node in Preorder, according to the chosen design.
Postorder Threading
Order: Left → Right → Root. For our tree: 10, 25, 30, 20, 70, 60, 40. Navigating to the next Postorder node can be harder, because it may require parent information or a special header.
Threaded Binary Tree Traversal Visualizer
Choose forward or reverse Inorder. Press Next Visit to reveal the visited nodes and understand whether the next move follows a thread or a real child subtree. This is a guided trace of the same seven-node example.
Thread Pointer Trace Console
This simulator is optional. The full dry run and pointer map above remain readable if a Blogger theme blocks JavaScript in posts.
Threaded Binary Tree Program in C with Inorder and Reverse Inorder Traversal
This complete C program first creates an ordinary seven-node tree. It converts missing child links into predecessor/successor threads using the Inorder sequence, then traverses forward and backward without recursion or a separate stack. The conversion step itself uses recursion.
The flags lthread
and rthread are 0 for
real children and 1 for threads.
When freeing the tree, the function visits
only real children,
not thread pointers.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
unsigned char lthread, rthread;
} Node;
Node *create(int value) {
Node *p = malloc(sizeof *p);
if (!p) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
p->data = value;
p->left = p->right = NULL;
p->lthread = p->rthread = 0;
return p;
}
/* Run once on an ordinary tree, before any threads exist. */
void addThreads(Node *p, Node **previous) {
if (!p) return;
Node *originalLeft = p->left;
Node *originalRight = p->right;
addThreads(originalLeft, previous);
if (originalLeft == NULL) {
p->lthread = 1;
p->left = *previous;
/* Inorder predecessor, possibly NULL */
}
if (*previous && (*previous)->right == NULL) {
(*previous)->rthread = 1;
(*previous)->right = p;
/* Inorder successor */
}
*previous = p;
addThreads(originalRight, previous);
}
void convertToInorderThreads(Node *root) {
Node *previous = NULL;
addThreads(root, &previous);
if (previous && previous->right == NULL) {
previous->rthread = 1;
previous->right = NULL;
/* Last node has no successor */
}
}
Node *leftmost(Node *p) {
while (
p &&
p->lthread == 0 &&
p->left
) {
p = p->left;
}
return p;
}
Node *rightmost(Node *p) {
while (
p &&
p->rthread == 0 &&
p->right
) {
p = p->right;
}
return p;
}
void inorderNoStack(Node *root) {
for (
Node *p = leftmost(root);
p != NULL;
) {
printf("%d ", p->data);
p = p->rthread
? p->right
: leftmost(p->right);
}
}
void reverseInorderNoStack(Node *root) {
for (
Node *p = rightmost(root);
p != NULL;
) {
printf("%d ", p->data);
p = p->lthread
? p->left
: rightmost(p->left);
}
}
void showLinks(Node *root) {
for (
Node *p = leftmost(root);
p != NULL;
) {
printf(
"%2d: left=%s",
p->data,
p->lthread ? "THREAD " : "CHILD "
);
if (p->left)
printf("%d", p->left->data);
else
printf("NULL");
printf(
", right=%s",
p->rthread ? "THREAD " : "CHILD "
);
if (p->right)
printf("%d", p->right->data);
else
printf("NULL");
putchar('\n');
p = p->rthread
? p->right
: leftmost(p->right);
}
}
/* Ignore thread links to avoid cycles/double-free. */
void freeThreadedTree(Node *p) {
if (!p) return;
if (p->lthread == 0)
freeThreadedTree(p->left);
if (p->rthread == 0)
freeThreadedTree(p->right);
free(p);
}
int main(void) {
/* Ordinary tree before conversion:
40
/ \
20 60
/ \ \
10 30 70
/
25
*/
Node *root = create(40);
root->left = create(20);
root->right = create(60);
root->left->left = create(10);
root->left->right = create(30);
root->left->right->left = create(25);
root->right->right = create(70);
convertToInorderThreads(root);
printf("Inorder: ");
inorderNoStack(root);
printf("\nReverse: ");
reverseInorderNoStack(root);
printf("\n\nPointer map:\n");
showLinks(root);
freeThreadedTree(root);
return 0;
}
Expected Output
Inorder: 10 20 25 30 40 60 70 Reverse: 70 60 40 30 25 20 10 Pointer map: 10: left=THREAD NULL, right=THREAD 20 20: left=CHILD 10, right=CHILD 30 25: left=THREAD 20, right=THREAD 30 30: left=CHILD 25, right=THREAD 40 40: left=CHILD 20, right=CHILD 60 60: left=THREAD 40, right=CHILD 70 70: left=THREAD 60, right=THREAD NULL
C Program Explained in Simple Steps
- create(): Allocates a new regular node with two initially empty child pointers.
- addThreads(): Walks the ordinary tree in Inorder and connects missing left/right pointers to their predecessor/successor.
- leftmost() / rightmost(): Follow only real child links, never threads.
- inorderNoStack(): Uses right-thread shortcuts or the leftmost node of a real right subtree.
- reverseInorderNoStack(): Uses left-thread shortcuts or the rightmost node of a real left subtree.
- freeThreadedTree(): Traverses only child links to free each node exactly once.
How to Run the C Program on Windows
Save the code as
threaded_binary_tree_ch68.c.
With GCC installed, open PowerShell
in the same folder and run:
gcc -std=c11 -Wall -Wextra -pedantic threaded_binary_tree_ch68.c -o threaded_binary_tree_ch68 .\threaded_binary_tree_ch68.exe
Time and Space Complexity of Threaded Binary Tree
| Operation | Time | Extra Space |
|---|---|---|
| Convert ordinary tree into Inorder threads (shown code) | O(n) | O(h) recursion stack |
| Forward Inorder traversal after threading | O(n) | O(1) |
| Reverse Inorder traversal after double threading | O(n) | O(1) |
| Stored nodes and thread tags | — | O(n) total node storage |
Here n is the number of real nodes, and h is the tree height. A full traversal still visits every node, so it cannot take less than O(n) time. The improvement is that later Inorder walks do not need an auxiliary stack.
Advantages of Threaded Binary Trees
- Can reuse NULL child pointers for helpful navigation links.
- Forward Inorder traversal can avoid recursion and an explicit stack.
- Double-threaded trees support reverse Inorder traversal as well.
- Useful for repeated traversal in some pointer-based applications.
Disadvantages of Threaded Binary Trees
- Need extra tag bits to distinguish children from threads.
- Insertion and deletion may require carefully updating neighbouring threads.
- Preorder and Postorder variants need different navigation logic.
- Threading does not automatically balance a tree or speed up every search.
Difference Between Binary Tree and Threaded Binary Tree
| Feature | Ordinary Linked Binary Tree | Inorder Threaded Binary Tree |
|---|---|---|
| Missing child link | NULL | May become predecessor/successor thread |
| Tag needed? | Usually not | Yes, to identify child versus thread |
| Inorder traversal | Commonly recursion or stack | No stack/recursion needed after threading |
| Extra navigation | Only child pointers | Child pointers plus traversal shortcuts |
| Updates | Maintain child links | Maintain child links and affected threads |
| Full traversal time | O(n) | O(n) |
Common Mistakes in Threaded Binary Tree Questions
- Calling every pointer a thread: Only missing child links are replaced. Real child links must remain real.
- Mixing predecessor and successor: For Inorder, the left thread points backward; the right thread points forward.
- Ignoring lthread/rthread: Recursing along a thread as if it were a child may create cycles.
- Assuming threading changes Inorder: It changes pointers, not the original traversal order.
- Claiming O(1) build space in this code: Construction uses recursive calls; only the final threaded traversal has O(1) auxiliary space.
- Following the same algorithm for Postorder: Order-specific successor navigation can be more complicated.
- Freeing through threads: Threads can lead back to existing nodes; only true child links should be recursively freed.
FAQs on Threaded Binary Tree in Data Structure
1. What is a Threaded Binary Tree?
It is a Binary Tree that replaces selected NULL child pointers with traversal-based links called threads, often to an Inorder predecessor or successor.
2. What are the main types of Threaded Binary Trees?
Left-threaded, right-threaded and double-threaded trees. Threading can also be designed for Inorder, Preorder or Postorder traversal.
3. What is a double-threaded Binary Tree?
It can store predecessor threads in missing left pointers and successor threads in missing right pointers. Flags identify which links are threads.
4. Why do we use lthread and rthread flags?
They distinguish an actual child link from a traversal shortcut, preventing incorrect traversal and memory handling.
5. Can we perform Inorder Traversal without recursion?
Yes. After constructing a suitable Inorder-threaded tree, follow the successor threads or the leftmost node of real right subtrees, using O(1) extra space.
6. Does a Threaded Binary Tree improve search complexity?
Not automatically. Threads primarily support traversal navigation; they do not by themselves impose a search ordering or keep the tree balanced.
7. Are external/dummy nodes and threads the same thing?
No. Extended Binary Trees add special external nodes at missing links. Threaded Binary Trees use missing pointer fields to reference actual predecessor/successor nodes or NULL/sentinels.
Threaded Binary Tree Quick Revision Notes
- Purpose: Use missing child pointers as useful traversal links.
- Left thread: Inorder predecessor in a left-threaded Inorder design.
- Right thread: Inorder successor in a right-threaded Inorder design.
- Single: One direction; Double: Both directions.
- lthread / rthread: Our code uses 0 = child and 1 = thread.
- Forward Inorder: 10, 20, 25, 30, 40, 60, 70.
- Reverse Inorder: 70, 60, 40, 30, 25, 20, 10.
- Traversal: O(n) time and O(1) extra space after threading.
- Construction: O(n) time; recursive code uses O(h) extra stack space.
- Key warning: Never treat a thread as a real child edge.
