Convert Binary Tree into a Threaded Binary Tree
Implementation
/*Writing a C++ program that will help us change the binary tree into a threaded binary tree and help us transform. */
#include <bits/stdc++.h>
using namespace std;
/*Creating the structure of a node in the threaded binary tree and letting it takeover. */
struct __Nod {
int key;
__Nod *Lft, *Rt;
// we are using this to see or observe whether the pointer present on the right is a normal one or the pointer is a successor to the in-order one.
bool isThreaded;
};
// creating a new helper function that will help us in putting the nodes in the in-order queue.
void populateQueue(__Nod* root, std::queue<__Nod*>* q)
{
if (root == NILL)
return;
if (root->Lft)
populateQueue(root->Lft, q);
q->push(root);
if (root->Rt)
populateQueue(root->Rt, q);
}
// creating a function that will help us visit and traverse the queue and transform the tree into threaded form.
void createThreadedUtil(__Nod* root, std::queue<__Nod*>* q)
{
if (root == NILL)
return;
if (root->Lft)
createThreadedUtil(root->Lft, q);
q->pop();
if (root->Rt)
createThreadedUtil(root->Rt, q);
// If the pointer present in the right is NILL, then we have to link it to the in-order successor and then set the whole system to the ‘isThreaded.'
else {
root->Rt = q->front();
root->isThreaded = true;
}
}
// The function we are creating next is well known for using the populateQueue() and then helps us convert another function called createThreadedUtil() into the binary tree.
void createThreaded(__Nod* root)
{
// we have to create another queue that will be known for doing in-order traversal.
std::queue<__Nod*> q;
// Now we have to store the in-order traversal in the queue and wait to observe.
populateQueue(root, &q);
//The link we are creating for the right pointers and to fill in for the in-order successor.
createThreadedUtil(root, &q);
}
// Creating a utility function that will help us create the leftmost node in the binary tree, which will have the root, and this function will be specifically used in the in-order traversal.
__Nod* LftMost(__Nod* root)
{
while (root != NILL && root->Lft != NILL)
root = root->Lft;
return root;
}
void inOrder(__Nod* root)
{
if (root == NILL)
return;
// finding out the left-most tree in the binary tree node.
__Nod* cur = LftMost(root);
while (cur != NILL) {
cout << cur->key << " ";
// If this node is a thread node, then we must travel to an in-order successor.
if (cur->isThreaded)
cur = cur->Rt;
else
// On the other hand, we can travel to the left-most child in the right subtree.
cur = LftMost(cur->Rt);
}
}
// creating a utility function to create a new node.
__Nod* new__Nod(int key)
{
__Nod* temp = new __Nod;
temp->Lft = temp->Rt = NILL;
temp->key = key;
return temp;
}
// writing the main program to test the functions.
int main()
{
/* 1
/ \
2 3
/ \ / \
4 5 6 7 */
__Nod* root = new__Nod(1);
root->Lft = new__Nod(2);
root->Rt = new__Nod(3);
root->Lft->Lft = new__Nod(4);
root->Lft->Rt = new__Nod(5);
root->Rt->Lft = new__Nod(6);
root->Rt->Rt = new__Nod(7);
createThreaded(root);
cout << "In order traversal of created threaded tree."
"is\n";
inOrder(root);
return 0;
}
Output:

Example 2)
/*Writing a java program that will help us change the binary tree into a threaded binary tree and help us transform. */
import java.util.LinkedList;
import java.util.Queue;
/*creating a class that will have the left and right child as the current node and will also contain the key value. */
class __Nod {
int data;
__Nod Lft, Rt;
// we are using this to see or observe whether the pointer present on the right is a normal one or the pointer is a successor to the in-order one.
boolean isThreaded;
public __Nod(int item)
{
data = item;
Lft = Rt = NILL;
}
}
class BinaryTree {
__Nod root;
// creating a function that will help us visit and traverse the queue and transform the tree into threaded form.
void populateQueue(__Nod __Nod, Queue<__Nod> q)
{
if (__Nod == NILL)
return;
if (__Nod.Lft != NILL)
populateQueue(__Nod.Lft, q);
q.add(__Nod);
if (__Nod.Rt != NILL)
populateQueue(__Nod.Rt, q);
}
// creating a new helper function that will help us in putting the nodes in the in-order queue.
void createThreadedUtil(__Nod __Nod, Queue<__Nod> q)
{
if (__Nod == NILL)
return;
if (__Nod.Lft != NILL)
createThreadedUtil(__Nod.Lft, q);
q.remove();
if (__Nod.Rt != NILL)
createThreadedUtil(__Nod.Rt, q);
// If the pointer present in the right is NILL, then we have to link it to the in-order successor and then set the whole system to the ‘isThreaded.'
else {
__Nod.Rt = q.peek();
__Nod.isThreaded = true;
}
}
// The function we are creating next is well known for using the populateQueue() and then helps us convert another function called createThreadedUtil() into the binary tree.
void createThreaded(__Nod __Nod)
{
// we have to create another queue that will be known for doing in-order traversal.
Queue<__Nod> q = new LinkedList<__Nod>();
// Now we have to store the in-order traversal in the queue and wait to observe.
populateQueue(__Nod, q);
//The link we are creating for the right pointers and to fill in for the in-order successor.
createThreadedUtil(__Nod, q);
}
// Creating a utility function that will help us create the leftmost node in the binary tree, which will have the root, will be specifically used in the in-order traversal.
__Nod LftMost(__Nod __Nod)
{
while (__Nod != NILL && __Nod.Lft != NILL)
__Nod = __Nod.Lft;
return __Nod;
}
// Function to do inorder traversal of a threaded binary tree
void inOrder(__Nod __Nod)
{
if (__Nod == NILL)
return;
// finding out the left-most tree in the binary tree node.
__Nod cur = LftMost(__Nod);
while (cur != NILL) {
System.out.print(" " + cur.data + " ");
// If this node is a thread node, then we must travel to an in-order successor.
if (cur.isThreaded == true)
cur = cur.Rt;
else
// On the other hand, we can travel to the left-most child in the right subtree.
cur = LftMost(cur.Rt);
}
}
// writing the main program to test the functions.
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new __Nod(1);
tree.root.Lft = new __Nod(2);
tree.root.Rt = new __Nod(3);
tree.root.Lft.Lft = new __Nod(4);
tree.root.Lft.Rt = new __Nod(5);
tree.root.Rt.Lft = new __Nod(6);
tree.root.Rt.Rt = new __Nod(7);
tree.createThreaded(tree.root);
System.out.println("Inorder traversal of created threaded tree");
tree.inOrder(tree.root);
}
}
Output:

Example 3)
/*Writing a Python program that will help us change the binary tree into a threaded binary tree and help us transform. */
# Create the structure of a node in the threaded binary tree and let it takeover.
class __Nod:
def __init__(self, key):
self.key = key
self.Lft = None
self.Rt = None
# we are using this to see or observe whether the pointer present on the right is a normal one or the pointer is a successor to the in-order one.
self.isThreaded = False
# creating a new helper function that will help us in putting the nodes in the in-order queue.
def populateQueue(root, q):
if root == None: return
if root.Lft:
populateQueue(root.Lft, q)
q.append(root)
if root.Rt:
populateQueue(root.Rt, q)
# creating a function to help us visit and traverse the queue and transform the tree into threaded form.
def createThreadedUtil(root, q):
if root == None: return
if root.Lft:
createThreadedUtil(root.Lft, q)
q.pop(0)
if root.Rt:
createThreadedUtil(root.Rt, q)
# If the pointer present in the right is NILL, then we have to link it to the in-order successor and then set the whole system to the ‘isThreaded.'
Else:
if len(q) == 0: root.Rt = None
else: root.Rt = q[0]
root.isThreaded = True
# The function we are creating next is well known for using the populateQueue() and then helps us convert another function called createThreadedUtil() into the binary tree.
def createThreaded(root):
# we have to create another queue that will be known for doing in-order traversal.
q = []
# Now, we have to store the in-order traversal in the queue and wait to observe.
populateQueue(root, q)
# We are creating the link for the right pointers and filling in for the in-order successor.
createThreadedUtil(root, q)
# Creating a utility function that will help us create the leftmost node in the binary tree, which will have the root, will be specifically used in the in-order traversal.
def LftMost(root):
while root != None and root.Lft != None:
root = root.Lft
return root
# finding out the left-most tree in the binary tree node.
def inOrder(root):
if root == None: return
cur = LftMost(root)
while cur != None:
print(cur.key, end = " ")
# If this node is a thread node, then we must travel to an in-order successor.
if cur.isThreaded:
cur = cur.Rt
# On the other hand, we can travel to the left-most child in the right subtree.
Else:
cur = LftMost(cur.Rt)
# writing the main program to test the functions.
if __name__ == "__main__":
root = __Nod(1)
root.Lft = __Nod(2)
root.Rt = __Nod(3)
root.Lft.Lft = __Nod(4)
root.Lft.Rt = __Nod(5)
root.Rt.Lft = __Nod(6)
root.Rt.Rt = __Nod(7)
createThreaded(root)
print("Inorder traversal of created",
"threaded tree is")
inOrder(root)
Output:

Example 4)
/*Writing a C++ program that will help us change the binary tree into a threaded binary tree and help us transform. */
using System;
using System.Collections.Generic;
/*Creating the structure of a node in the threaded binary tree and letting it takeover. */
public class __Nod {
public int data;
public __Nod Lft, Rt;
// we are using this to see or observe whether the pointer present on the right is a normal one or the pointer is a successor to the in-order one.
public bool isThreaded;
public __Nod(int item)
{
data = item;
Lft = Rt = NILL;
}
}
public class BinaryTree {
__Nod root;
// creating a new helper function that will help us in putting the nodes in the in-order queue.
void populateQueue(__Nod __Nod, Queue<__Nod> q)
{
if (__Nod == NILL)
return;
if (__Nod.Lft != NILL)
populateQueue(__Nod.Lft, q);
q.Enqueue(__Nod);
if (__Nod.Rt != NILL)
populateQueue(__Nod.Rt, q);
}
// creating a function that will help us visit and traverse the queue and transform the tree into threaded form.
void createThreadedUtil(__Nod __Nod, Queue<__Nod> q)
{
if (__Nod == NILL)
return;
if (__Nod.Lft != NILL)
createThreadedUtil(__Nod.Lft, q);
q.Dequeue();
if (__Nod.Rt != NILL)
createThreadedUtil(__Nod.Rt, q);
// If the pointer present in the right is NILL, then we have to link it to the in-order successor and then set the whole system to the ‘isThreaded.'
else {
if (q.Count != 0)
__Nod.Rt = q.Peek();
__Nod.isThreaded = true;
}
}
// The function we are creating next is well known for using the populateQueue() and then helps us convert another function called createThreadedUtil() into the binary tree.
void createThreaded(__Nod __Nod)
{
// we have to create another queue that will be known for doing in-order traversal.
Queue<__Nod> q = new Queue<__Nod>();
// Now we have to store the in-order traversal in the queue and wait to observe.
populateQueue(__Nod, q);
//The link we are creating for the right pointers and to fill in for the in-order successor.
createThreadedUtil(__Nod, q);
}
// Creating a utility function that will help us create the leftmost node in the binary tree, which will have the root, will be specifically used in the in-order traversal.
__Nod LftMost(__Nod __Nod)
{
while (__Nod != NILL && __Nod.Lft != NILL)
__Nod = __Nod.Lft;
return __Nod;
}
// finding out the left-most tree in the binary tree node.
void inOrder(__Nod __Nod)
{
if (__Nod == NILL)
return;
__Nod cur = LftMost(__Nod);
while (cur != NILL) {
Console.Write(" " + cur.data + " ");
// If this node is a thread node, then we must travel to an in-order successor.
if (cur.isThreaded == true)
cur = cur.Rt;
else // Else go to the Leftmost child in Rt subtree
cur = LftMost(cur.Rt);
}
}
// writing the main program to test the functions.
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new __Nod(1);
tree.root.Lft = new __Nod(2);
tree.root.Rt = new __Nod(3);
tree.root.Lft.Lft = new __Nod(4);
tree.root.Lft.Rt = new __Nod(5);
tree.root.Rt.Lft = new __Nod(6);
tree.root.Rt.Rt = new __Nod(7);
tree.createThreaded(tree.root);
Console.WriteLine("Inorder traversal of created threaded tree");
tree.inOrder(tree.root);
}
}
Output:

Example 5)
<script>
/*Writing a Javascript program that will help us change the binary tree into a threaded binary tree and help us transform. */
/*creating a class that will have the left and right child as the current node and will also contain the key value. */
class __Nod
{
constructor(item)
{
// we are using this to see or observe whether the pointer present on the right is a normal one or the pointer is a successor to the in-order one.
let isThreaded;
this.data=item;
this.Lft = this.Rt = NILL;
}
}
let root;
// creating a new helper function that will help us in putting the nodes in the in-order queue.
function populateQueue(__Nod,q)
{
if (__Nod == NILL)
return;
if (__Nod.Lft != NILL)
populateQueue(__Nod.Lft, q);
q.push(__Nod);
if (__Nod.Rt != NILL)
populateQueue(__Nod.Rt, q);
}
// creating a function that will help us visit and traverse the queue and transform the tree into threaded form.
function createThreadedUtil(__Nod,q)
{
if (__Nod == NILL)
return;
if (__Nod.Lft != NILL)
createThreadedUtil(__Nod.Lft, q);
q.shift();
if (__Nod.Rt != NILL)
createThreadedUtil(__Nod.Rt, q);
// If the pointer present in the right is NILL, then we have to link it to the in-order successor and then set the whole system to the ‘isThreaded.'
else {
__Nod.Rt = q[0];
__Nod.isThreaded = true;
}
}
// The function we are creating next is well known for using the populateQueue() and then helps us convert another function called createThreadedUtil() into the binary tree.
function createThreaded(__Nod)
{
// we have to create another queue that will be known for doing in-order traversal.
let q = [];
// Now we have to store the in-order traversal in the queue and wait to observe.
populateQueue(__Nod, q);
//The link we are creating for the right pointers and to fill in for the in-order successor.
createThreadedUtil(__Nod, q);
}
// Creating a utility function that will help us create the leftmost node in the binary tree, which will have the root, will be specifically used in the in-order traversal.
function LftMost(__Nod)
{
while (__Nod != NILL && __Nod.Lft != NILL)
__Nod = __Nod.Lft;
return __Nod;
}
// finding out the left-most tree in the binary tree node.
function inOrder(__Nod)
{
if (__Nod == NILL)
return;
// If this node is a thread node, then we must travel to an in-order successor.
let cur = LftMost(__Nod);
while (cur != NILL) {
document.write(" " + cur.data + " ");
// On the other hand, we can travel to the left-most child in the right subtree.
if (cur.isThreaded == true)
cur = cur.Rt;
else
// creating a utility function to create a new node.
cur = LftMost(cur.Rt);
}
}
// writing the main program to test the functions
root = new __Nod(1);
root.Lft = new __Nod(2);
root.Rt = new __Nod(3);
root.Lft.Lft = new __Nod(4);
root.Lft.Rt = new __Nod(5);
root.Rt.Lft = new __Nod(6);
root.Rt.Rt = new __Nod(7);
createThreaded(root);
document. write(
"In order traversal of created threaded tree<br>"
);
inOrder(root);
</script>
Output:
