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:

Convert Binary Tree into a Threaded Binary Tree

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:

Data Structures Tutorial

Misc Topic:

Data Structures Tutorial

Misc Topic:

Convert Binary Tree into a Threaded Binary Tree

Implementation