A Threaded Binary Tree is a binary tree variant where null pointers are replaced with special links called threads. These threads allow the traversal of the tree in order without requiring a stack or recursion, making traversal efficient in terms of time and space.
Types of Threaded Binary Trees
- Single Threaded Binary Tree:
- Only one type of null pointer (either left or right) is replaced with a thread.
- Double Threaded Binary Tree:
- Both left and right null pointers are replaced with threads.
Purpose of Threaded Binary Tree
The main goal is to improve the efficiency of traversal:
- In a regular binary tree, null pointers are wasted space.
- Threaded binary trees utilize these null pointers to point to the inorder predecessor or inorder successor, enabling in-order traversal without recursion or stack.
Structure of a Node in Threaded Binary Tree
The node structure includes:
- Data: Stores the node’s value.
- Left and Right Pointers: Pointers to the left and right children.
- Thread Flags: Indicators for whether the pointers are threads or regular child pointers.
C Code for Node Structure:
struct Node {
int data;
struct Node* left;
struct Node* right;
int leftThread; // 1 if left points to the inorder predecessor
int rightThread; // 1 if right points to the inorder successor
};
Operations on Threaded Binary Tree
1. Insertion in Threaded Binary Tree
Algorithm:
- Find the position to insert the new node using the threads.
- Adjust the pointers and thread flags.
C Code:
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
int leftThread;
int rightThread;
};
// Create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->leftThread = 1; // Initially points to predecessor
newNode->rightThread = 1; // Initially points to successor
return newNode;
}
// Insert a node into the threaded binary tree
struct Node* insert(struct Node* root, int data) {
struct Node* parent = NULL;
struct Node* current = root;
// Find the position to insert
while (current != NULL) {
if (data == current->data) {
printf(“Duplicate data not allowed.\n”);
return root;
}
parent = current;
if (data < current->data) {
if (current->leftThread == 0) {
current = current->left;
} else {
break;
}
} else {
if (current->rightThread == 0) {
current = current->right;
} else {
break;
}
}
}
// Create the new node
struct Node* newNode = createNode(data);
if (parent == NULL) {
// Tree was empty
root = newNode;
} else if (data < parent->data) {
newNode->left = parent->left;
newNode->right = parent;
parent->leftThread = 0;
parent->left = newNode;
} else {
newNode->right = parent->right;
newNode->left = parent;
parent->rightThread = 0;
parent->right = newNode;
}
return root;
}
2. Inorder Traversal of Threaded Binary Tree
Algorithm:
- Start from the leftmost node.
- Follow the inorder successor using the threads.
C Code:
void inorderTraversal(struct Node* root) {
struct Node* current = root;
// Go to the leftmost node
while (current != NULL && current->leftThread == 0) {
current = current->left;
}
// Traverse the tree using threads
while (current != NULL) {
printf(“%d “, current->data);
// Use right thread to move to the inorder successor
if (current->rightThread == 1) {
current = current->right;
} else {
// Go to the leftmost node in the right subtree
current = current->right;
while (current != NULL && current->leftThread == 0) {
current = current->left;
}
}
}
}
Example Program: Threaded Binary Tree
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
int leftThread;
int rightThread;
};
// Function prototypes
struct Node* createNode(int data);
struct Node* insert(struct Node* root, int data);
void inorderTraversal(struct Node* root);
int main() {
struct Node* root = NULL;
root = insert(root, 20);
root = insert(root, 10);
root = insert(root, 30);
root = insert(root, 5);
root = insert(root, 15);
printf(“Inorder Traversal of Threaded Binary Tree:\n”);
inorderTraversal(root);
return 0;
}
// Create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->leftThread = 1;
newNode->rightThread = 1;
return newNode;
}
// Insert a node into the threaded binary tree
struct Node* insert(struct Node* root, int data) {
struct Node* parent = NULL;
struct Node* current = root;
// Find the position to insert
while (current != NULL) {
if (data == current->data) {
printf(“Duplicate data not allowed.\n”);
return root;
}
parent = current;
if (data < current->data) {
if (current->leftThread == 0) {
current = current->left;
} else {
break;
}
} else {
if (current->rightThread == 0) {
current = current->right;
} else {
break;
}
}
}
// Create the new node
struct Node* newNode = createNode(data);
if (parent == NULL) {
root = newNode;
} else if (data < parent->data) {
newNode->left = parent->left;
newNode->right = parent;
parent->leftThread = 0;
parent->left = newNode;
} else {
newNode->right = parent->right;
newNode->left = parent;
parent->rightThread = 0;
parent->right = newNode;
}
return root;
}
// Inorder Traversal
void inorderTraversal(struct Node* root) {
struct Node* current = root;
// Go to the leftmost node
while (current != NULL && current->leftThread == 0) {
current = current->left;
}
// Traverse the tree
while (current != NULL) {
printf(“%d “, current->data);
if (current->rightThread == 1) {
current = current->right;
} else {
current = current->right;
while (current != NULL && current->leftThread == 0) {
current = current->left;
}
}
}
}
Output
For the tree:
markdown
Copy code
20
/ \
10 30
/ \
5 15
Output:
Inorder Traversal of Threaded Binary Tree:
5 10 15 20 30
Advantages of Threaded Binary Tree
- Eliminates the need for recursion or stack during traversal.
- Utilizes otherwise wasted null pointers for efficient traversal.
- Improves memory usage.
Disadvantages
- Complex insertion and deletion operations compared to standard binary trees.
- Increased maintenance of thread pointers.