Logo
×

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:

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:

Convert Binary Tree into a Threaded Binary Tree

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:

Convert Binary Tree into a Threaded Binary Tree

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:

Convert Binary Tree into a Threaded Binary Tree

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:

Convert Binary Tree into a Threaded Binary Tree

Related Topics

Recursion - Factorial and Fibonacci

In this article, we will learn how to find the factorial of a number and the Fibonacci series up to n using the recursion method. What is recursion? Defining anything in terms...

7 minutes read.

Linked List Data Structure

Linked list in DS: The linked list is a non-primitive and linear data structure. It is a list of a particular type of data element that is connected to each...

3 minutes read.

Does Overloading Work with Inheritance

This is a question that occasionally comes to many programmers. Who are curious to know more now has a complete explanation and a solution through this tutorial! Inheritance: The functions of...

3 minutes read.

Hashing

Hashing: Hashing is a process in which a large amount of data is mapped to a small table with the help of hashing function. It is a searching technique. Hash table We...

4 minutes read.

Shell Sort

Shell Sort: Shell sort is a sorting algorithm. It is an extended version of the insertion sort. In this sorting, we compare the elements that are distant apart rather than the...

5 minutes read.

Understanding Data Processing

Introduction Data In our everyday lives, any task that we perform online is related to data. Millions of pieces of data are produced every second across the globe. Data production is largely...

4 minutes read.

What is B tree?

What do you mean by B Tree in Data Structures? In the technological world, a B tree is simply a well-managed and coordinated tree and an integral part of the data...

6 minutes read.

Left View of Binary Tree

Implementation // creating a C++ program to print the Left view of the binary tree. #include <bits/stdc++.h> using namespace std; struct Nod { int record; struct Nod *Lft, *Rt; }; // creating a utility function that will eventually help...

4 minutes read.

Semi-Structured data

In this article, we will discuss the semi-structured data. Data can be defined as the distinct piece of information that is gathered and translated for some purpose. It can be...

5 minutes read.

Structure and Union Data Structure

The array is used for the same type of data, but if we want to store a mixed type of data in a group, then the array cannot be used. The Structure...

4 minutes read.

Deletion in B+ Tree

Make a search for the leaf node that containing the key value by taking the value in a key value. If the required key value is found, then it will remove...

6 minutes read.

Binary tree insertion

As we all know, a binary tree has a maximum of two children and helps us manage the info correctly. Here the name of the tree itself portrays the mechanism...

4 minutes read.

What is the B+ Tree in Data Structures?

We all know that the B+ tree in data structures is nothing but just an extended version of the B tree. It allows the smooth working of all the operations...

7 minutes read.

Flattening a Linked List

In this article, we are going to study about the logic behind the flattening of linked list and we also going to build a code in the C++ to flatten...

3 minutes read.

Check if a Singly Linked List is Palindrome

Check if a Singly Linked List is Palindrome In this section, we have given a singly linked list, and we need to check whether the given list is a palindrome. Example:           1...

3 minutes read.

Counting Sort

Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the...

3 minutes read.

Trim a binary search tree

Implementation //writing a C++ program will help us eliminate the keys that are out of the league.  #include<bits/stdc++.h> using namespace std; //we are now creating a binary search tree node consisting of key left...

8 minutes read.

Binary Tree Inorder Traversal

The binary tree is a type of tree in which each and every node has atleast two children except the leaf nodes. We have various operations in the binary tree,...

4 minutes read.

Strictly binary tree in Data Structures?

What is a strictly Binary Tree in Data Structures? There are various kinds of binary trees that we know exist in data structures, and they all have their purposes. In this...

4 minutes read.

Tim Sort

Tim Sort is a mixture stable arranging calculation that exploits normal examples in information, and uses a mix of an improved Merge sort and Binary Insertion sort alongside an interior...

6 minutes read.