Name : Tejas Gitkhane
Roll no. : S511042
Class : SE
Div. :A
Batch : A2
Experiment 6
Implement Inordered binary tree and traverse it in in-order and pre-order
#include <iostream> using
namespace std;
// Node structure for Threaded Binary Tree struct
ThreadedNode {
int data;
ThreadedNode *left, *right;
bool isLeftThread, isRightThread;
ThreadedNode(int val) : data(val), left(nullptr), right(nullptr),
isLeftThread(false), isRightThread(false) {} };
// Class to represent the Threaded Binary Tree
class ThreadedBinaryTree { private:
ThreadedNode *root;
// Helper function to create a new threaded node
ThreadedNode* insert(ThreadedNode* root, int data) {
if (root == nullptr) {
return new ThreadedNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
return root;
// Function to create threads void
createThreads(ThreadedNode* node) {
if (node == nullptr) return;
if (node->left) {
createThreads(node->left);
// Create right thread if
(node->right) {
createThreads(node->right);
// Creating threads if (node-
>left == nullptr) { node-
>isLeftThread = true; node->left
= predecessor(node);
if (node->right == nullptr) { node-
>isRightThread = true; node->right =
successor(node);
}
// Find the predecessor
ThreadedNode* predecessor(ThreadedNode* node) {
ThreadedNode* temp = node->left;
while (temp && !temp->isRightThread) {
temp = temp->right;
return temp;
// Find the successor
ThreadedNode* successor(ThreadedNode* node) {
ThreadedNode* temp = node->right; while (temp
&& !temp->isLeftThread) { temp = temp->left;
return temp;
public:
ThreadedBinaryTree() : root(nullptr) {}
// Insert function void
insert(int data) { root =
insert(root, data);
createThreads(root);
// In-order traversal void
inOrderTraversal() {
ThreadedNode* current = root;
while (current != nullptr) {
while (current->left != nullptr && !current->isLeftThread) {
current = current->left;
}
cout << current->data << " ";
// If there is a right thread, go to the right
if (current->isRightThread) {
current = current->right;
} else {
current = current->right;
while (current != nullptr && current->left != nullptr) {
current = current->left;
// Pre-order traversal void
preOrderTraversal() {
ThreadedNode* current = root;
while (current != nullptr) {
cout << current->data << " ";
// If left child is present
if (current->left != nullptr && !current->isLeftThread) {
current = current->left;
// If no left child, follow right thread
else if (current->isRightThread) {
current = current->right;
// Move to the next node
else {
while (current != nullptr && current->isRightThread) {
current = current->right;
if (current != nullptr) {
current = current->right;
}
}
};
// Main function to demonstrate the Threaded Binary Tree int
main() {
ThreadedBinaryTree tbt;
// Inserting values into the tree
tbt.insert(20); tbt.insert(10);
tbt.insert(30); tbt.insert(6);
tbt.insert(14); tbt.insert(24);
tbt.insert(36);
cout << "In-order Traversal: ";
tbt.inOrderTraversal(); cout
<< endl;
cout << "Pre-order Traversal: ";
tbt.preOrderTraversal(); cout
<< endl;
return 0;
}
OUTPUT:
