A Threaded Binary Tree is an advanced form of a binary tree that improves traversal efficiency. Unlike a normal binary tree, it uses special pointers called threads to connect nodes to their in-order predecessors and successors. This eliminates the need for recursion or stacks during traversal, making operations faster and more memory-efficient. Threaded binary trees are especially useful when frequent in-order traversals are required.
This tutorial explains the Threaded Binary Tree in data structure with examples in C and C++. You will learn its types, need, with examples in C and C++. You will learn its types, need, and operations such as insertion, deletion, and traversal. We will also discuss advantages, disadvantages, and real-world applications. By the end, you will understand how threaded binary trees enhance performance and simplify tree-based algorithms.
Looking to advance your software skills? Check out upGrad’s Online Software Engineering Courses. Start today to strengthen your foundation and accelerate your career growth by learning JavaScript, Node.js, APIs, React, and more!
What is a Binary Tree?
A binary tree is a hierarchical data structure where each node has at most two children, called the left child and the right child. Nodes with no children are called leaves, and the topmost node is called the root.
Boost your career growth by learning in-demand skills across Cloud, DevOps, AI, and Full Stack Development. Work on real-world projects, gain practical expertise, and learn directly from industry experts to stand out in the job market.
For instance, take a look at the threaded binary tree below, written in C++:
#include <iostream>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
};
TreeNode* createNode(int data) {
TreeNode* newNode = new TreeNode;
newNode->data = data;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}
TreeNode* insert(TreeNode* root, int data) {
if (root == nullptr) {
return createNode(data);
} else {
if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}
}
void inOrderTraversal(TreeNode* root) {
if (root != nullptr) {
inOrderTraversal(root->left);
std::cout << root->data << " ";
inOrderTraversal(root->right);
}
}
int main() {
TreeNode* root = nullptr;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 10);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 14);
root = insert(root, 4);
root = insert(root, 7);
root = insert(root, 13);
std::cout << "In-order traversal of the tree: ";
inOrderTraversal(root);
std::cout << std::endl;
return 0;
}
Output:
In-order traversal of the tree: 1 3 4 6 7 8 10 13 14
The code includes the necessary header file for input/output operations (iostream).
- To represent a node in a binary search tree (BST), it specifies a struct TreeNode. Each node has an integer data value and two left and right pointers, respectively, pointing to the left and right child nodes.
- A function called createNode is defined to build a new TreeNode and set its data, and left and right pointers during initialization.
- Another function, called insert, is defined to add a new node to the BST with the specified data.
- Based on the new node's data value, the insert function utilizes recursion to determine where it should be in the tree. The node is inserted to the left if its data is less than that of the current node and to the right otherwise.
- The tree is printed in ascending order using the inOrderTraversal function. It uses an in-order traversal method, visiting the left subtree before moving on to the root and then the right subtree.
- A pointer root to the BST is initialized to nullptr in the main function.
- Using the insert function, nine nodes with the data values 8, 3, 10, 1, 6, 14, 4, 7, and 13 are added to the BST.
- The inOrderTraversal function is used to print the tree's nodes in ascending order after the insertion.
- The BST will be traversed in order as follows: "1 3 4 6 7 8 10 13 14"
Must Read: What are Data Structures & Algorithm
What is the Need for a Threaded Binary Tree?
Ordinary binary trees are an effective way to depict hierarchical relationships, but traversing them in a particular sequence (like in-order traversal) can be difficult and resource-intensive. Threaded binary trees overcome this limitation by adding threads to each node, which allows for efficient in-order traversal.
Types of Binary Trees
Let's briefly examine several prevalent binary tree types before delving into threaded binary trees:
- Full binary tree: Every node in a full binary tree has either 0 or 2 offspring.
- Complete Binary Tree: All levels of the tree, except the bottom one, are filled and nodes are aligned to the left.
- Perfect binary tree: A perfect binary tree has leaf nodes that are all at the same level and internal nodes that all have two offspring.
- Balanced binary tree: A balanced binary tree has a maximum height difference of one between its left and right subtrees.
What is the Significance of a Bool Variable in a Structure?
A bool variable's importance in a structure comes from its capacity to add more details or control to the structure. The bool variable is used as a flag or indicator to reflect a certain condition or state connected with the structure in various data structures, including threaded binary trees.
The bool variable is often used in the context of a threaded binary tree to represent whether a specific pointer is a regular child pointer or a thread that connects to the in-order predecessor or successor. Let's look at a threaded binary tree example:
struct TreeNode {
int data;
TreeNode* left;
bool leftThread;
TreeNode* right;
bool rightThread;
};In this structure, the leftThread and rightThread variables serve as flags. If leftThread is set to true, the left pointer in the threaded tree will instead point to the threaded tree's in-order predecessor rather than the current node's left child. Similar to this, if rightThread is true, it means that the right pointer is pointing to the current node's in-order successor rather than its right child.
Without recursion or an explicit stack, we can efficiently traverse a threaded binary tree using these bool variables because we can use the threads to quickly go to the next node in the in-order sequence.
Also Read: Boolean in C
Inorder Traversal Using Threads
In-order traversal is a common threaded binary tree traversal method. We can efficiently conduct in-order traversal with threads instead of recursion or stacks. Here is a thread-based in-order traversal implementation in C++:
Now that we have the leftMost function, let's consider the following threaded binary tree:
Using the inOrderTraversal function, we will perform an in-order traversal of the given threaded binary tree and print the values of the nodes.
#include <iostream>
struct TreeNode {
int data;
TreeNode* left;
bool leftThread;
TreeNode* right;
bool rightThread;
};
TreeNode* leftMost(TreeNode* node) {
if (node == nullptr)
return nullptr;
while (node->left != nullptr) {
node = node->left;
}
return node;
}
void inOrderTraversal(TreeNode* root) {
TreeNode* curr = leftMost(root);
while (curr) {
std::cout << curr->data << " ";
if (curr->rightThread)
curr = curr->right;
else
curr = leftMost(curr->right);
}
}
int main() {
TreeNode* root = new TreeNode{8, nullptr, false, nullptr, false};
root->left = new TreeNode{3, nullptr, false, nullptr, false};
root->left->left = new TreeNode{1, nullptr, false, nullptr, false};
root->left->right = new TreeNode{6, nullptr, false, nullptr, false};
root->left->right->left = new TreeNode{4, nullptr, false, nullptr, false};
root->left->right->right = new TreeNode{7, nullptr, false, nullptr, false};
root->right = new TreeNode{10, nullptr, false, nullptr, false};
root->right->right = new TreeNode{14, nullptr, false, nullptr, false};
root->right->right->left = new TreeNode{13, nullptr, false, nullptr, false};
std::cout << "In-order traversal of the tree: ";
inOrderTraversal(root);
std::cout << std::endl;
return 0;
}
Output:
In-order traversal of the tree: 1 3 4 6 7 8 10 13 14
The output shows the selected binary tree threaded exploration in the following order: 1 3 4 6 7 8 10 13 14. The ascending order of the nodes in their writing is evidence that thread-based in-order traversal is implemented properly.
Double threaded binary tree
The double threaded binary tree is a variation on the threaded binary tree data structure, where each node has threads to both its in-order predecessor and successor as well as to its predecessor's predecessor and successor's successor.
The left and right pointers of some nodes act as threads linking to specific nodes in the orderly sequence, in addition to acting as conventional child pointers in a double threaded binary tree.
struct DoubleThreadedTreeNode {
int data;
DoubleThreadedTreeNode* left;
bool leftThread;
DoubleThreadedTreeNode* right;
bool rightThread;
DoubleThreadedTreeNode* predecessor;
DoubleThreadedTreeNode* successor;
};A double threaded binary tree does not require recursive calls or other data structures to conduct in-order traversal because the predecessor and successor pointers offer direct access to the in-order predecessor and successor, respectively.
Double threaded binary trees are advantageous in situations where frequent in-order traversal or related operations are required. They can efficiently conduct in-order traversal, in-order predecessor, and in-order successor operations with constant time complexity (O(1)).
In comparison to conventional binary trees, double threaded binary trees offer a compromise between better traversal performance and improved space efficiency, particularly when the same traversal is carried out more than once and traversals occur more frequently than tree structure modifications.
Also Read: Decision Tree Algorithm Explained: From Root to Leaf
Threaded Binary Tree in C++
In a threaded binary tree, each node is enhanced with extra threads (points) that enable efficient traversal without the need for recursion or auxiliary data structures. A threaded binary tree can be created in C++ by setting the proper thread flags and defining the node in a struct.
The node structure while creating a threaded binary tree in C++ can resemble this:
struct TreeNode {
int data;
TreeNode* left;
bool leftThread;
TreeNode* right;
bool rightThread;
};The leftThread and rightThread flags indicate whether the left and right pointers are threads or simple child pointers. Threaded binary trees are advantageous in some situations because they allow for quick and effective in-order traversal, search, and retrieval operations.
Threaded Binary Tree in C
Similar techniques to those used in C++ are used to implement a threaded binary tree in C. Since C doesn't have any object-oriented capabilities, implementations often rely on straightforward structures and pointers. A C struct serves as the representation for each node in the threaded binary tree.
Using structures for the node and thread flags, a threaded binary tree implementation in C might resemble one in C++:
TreeNode* leftMost(TreeNode* node) {
if (node == nullptr)
return nullptr;
while (node->left != nullptr) {
node = node->left;
}
return node;
}
The threaded binary tree in C has similar benefits to those in C++, including increased traversal efficiency, decreased memory overhead, and, under some circumstances, faster search and retrieval. However, because C lacks the syntactic sugar of C++ and requires explicit memory management, the solution is a little trickier.
The Operations in a Threaded Binary Tree
Threaded binary trees support several operations, including:
- Insertion: Inserting a new node into a binary tree while appropriately maintaining threading is known as threaded binary tree insertion.
- Deletion: Removal of a node from the tree and corresponding thread adjustments.
- Search: Effectively locating a certain element in the tree.
- In order: Finding the nodes that come before or after a specific node in an in-order traversal is known as in-order successor and predecessor.
Advantages of Threaded Binary Tree
Threaded binary trees have the following benefits:
- In-order traversal that is quick and doesn't require recursion or extra room.
- Faster search and retrieval processes in some circumstances.
- Various tree-based algorithms are implemented more simply.
Disadvantages of Threaded Binary Tree
Despite their benefits, threaded binary trees have the following disadvantages:
- Increased insertion and deletion complexity as a result of thread management.
- Additional memory use is required to store the threading data.
Applications of Threaded Binary Tree
Threaded binary trees are used in many different fields, including:
- Expression parsing: Easy evaluation of mathematical expressions through the use of expression parsing.
- Database indexing: Finding information quickly in indexed databases.
- Threaded in-order traversal: Ordered threads implementing quick and responsive user interfaces are crucial.
Time and Space Complexity of Operations
The time and space complexity of operations can be summarized as follows:
Operation | Time Complexity | Space Complexity |
Insertion | O(log n) | O(1) |
Deletion | O(log n) | O(1) |
Search | O(log n) | O(1) |
In-order Traversal | O(n) | O(1) |
In-order Successor/Predecessor | O(1) | O(1) |
Conclusion
A Threaded Binary Tree is a practical extension of the binary tree that makes in-order traversal faster and more efficient. It reduces the need for recursion or stacks, saving both time and memory. Though managing threads adds some complexity, the performance benefits often outweigh the drawbacks.
The Threaded Binary Tree in data structure is widely used in expression parsing, database indexing, and quick search operations. Developers can rely on it to simplify tree-based algorithms. Understanding its advantages and limitations helps in applying it effectively. Use threaded binary trees to build efficient, responsive, and structured applications with ease.
FAQs
1. How does a threaded binary tree improve in-order traversal efficiency?
A threaded binary tree uses "threads" to link nodes, enabling efficient in-order traversal without recursion or extra data structures. This reduces memory usage and speeds up frequent in-order traversals. How are threads managed in a threaded binary tree?
2. How are threads managed in a threaded binary tree?
In a threaded binary tree, thread management is achieved through boolean flags, such as leftThread and rightThread, which determine whether the left and right pointers are threads to in-order predecessors and successors or standard child pointers for each node. How do threaded binary trees compare to regular binary trees in terms of memory usage?
3. How do threaded binary trees compare to regular binary trees in terms of memory usage?
Threaded binary trees use slightly more memory due to the added thread flags per node, but they offer memory-saving benefits during in-order traversal by eliminating the need for explicit recursion or stack usage.
