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

LCA of binary tree

Implementation //Writing a program to find the lowest common factor in a given binary search tree. #include <iostream> #include <vector> using namespace std; // the very first step is to create a binary tree. struct __nod { int...

8 minutes read.

Reverse a Linked List in groups of given size

Reverse a Linked List in groups of given size This article will explain how to reverse a linked list in groups of given size. Here we have given a linked list...

2 minutes read.

What is a Spanning Tree in Data Structure

Data structures Data management is called database management. This allows the computer to sort or organize the data for efficient retrieval. A data model is a system used to store, manage,...

5 minutes read.

Huffman tree in Data Structures

The Huffman trees in the field of data structures are pretty impressive in their work. They are generally treated as the binary tree, which is linked with the least external...

6 minutes read.

What is the difference between Tree and Graph

We usually use a diverse range of data structure to store our data and information. To store them in a more sequential manner and to access them easily, we use...

4 minutes read.

Reverse the Singly Linked List in C

Reverse the Singly Linked List in C This article has given a singly linked list and will reverse the linked list by changing the links between nodes. Example:                         Input:  2 -> 4...

3 minutes read.

B+ Tree Program in Q language

A B+ tree is just an improvised version of a self-balancing and well-maintained tree in which all the key values that hold valuable information is present at the bottom, which...

9 minutes read.

Right side view of binary tree

The right view of the binary tree is generally known to be that side viewed from the right direction of the point of view. To be more precise, the right-side...

8 minutes read.

Extended Binary Tree

A form of binary tree known as an extended binary tree replaces all of the original tree's null subtrees with special nodes known as external nodes, while the remaining nodes...

4 minutes read.

Berkley’s Algorithm

Berkley’s Algorithm is mainly used in clock synchronization system. It is used in distributed systems. To implement this algorithm, we have to think that the network has no accurate time...

4 minutes read.

Convert a Binary Tree into a Binary Search Tree

Implementation #include <stdio.h>   #include <stdlib.h>       //creating a node of the binary tree.  struct __nod{       int record;       struct __nod *Lft;       struct __nod *Rt;   };       // presenting the root of the binary tree.   struct...

5 minutes read.

Operations on 2D-Arrays

Two Dimensional Array Operations Adding Elements to Two-D Arrays We must put data in both rows and columns when inserting items in 2-D Arrays. As a result, we employ the idea of...

10 minutes read.

Merge two sorted linked lists

Merge two sorted linked lists In this article, we are going to learn how to merge two linked lists. Here we have given two linked lists that are sorted in increasing...

7 minutes read.

All About Minimum Cost Spanning Trees in Data Structure

Data management is called database management. This allows the computer to sort or organize the data for efficient retrieval. A data model is a system that stores, manages, and optimizes...

7 minutes read.

What are the types of Trees in Data Structure

Data structures Data management is called database management. This allows the computer to sort or organize the data for efficient retrieval. A data model is a system used to store, manage,...

6 minutes read.

Buffer overflow attack with examples

You have undoubtedly faced the term buffer overflow in your programming journey. Many times it occurs when we try to run a piece of code with user input, but it...

4 minutes read.

Print kth least significant bit number

You have given a number and you have to find out the kth least significant bit of this number. K will be given to you.  The bit will be from...

3 minutes read.

Data Structures Algorithms

What is an Algorithm? An algorithm is a sequence of steps used to complete a job or get a desired result. It is similar to programming building elements that let cell...

4 minutes read.

Threaded Binary Tree

The linked form of binary trees wastes storage capacity because more than half of the connection variables have a Missing value. A binary tree has several nodes. Hence n+1 link fields...

8 minutes read.

What is a Threaded Binary Tree?

When we consider those binary trees that are interlinked with each other, we do come across the fact that the fields present in there do consist of NULL values that...

3 minutes read.