# In Order Traversal of Threaded Binary Tree

More over half of the link fields in the linked representation of binary trees have NULL values, wasting storage space. When a binary tree has n nodes, the link fields for nodes n+1 have NULL values.

Therefore, in order to effectively manage the space, Perlis and Thornton created a method in which the NULL links are replaced with special links known as threads. These threaded binary trees are the threaded binary trees. In a threaded binary tree, each node either has a connection to a child node or a thread to other nodes.

To explore a binary tree in reverse order, one can use recursion or an auxiliary stack. Through the use of stack-free and recursion-free threaded binary trees, inorder traversal can be accelerated. In order to create a threaded binary tree, all right child pointers that would ordinarily point to NULL in a binary tree are altered to point to the node's inorder successor (if it exists).

The threaded binary tree comes in two varieties

1. In a single-threaded application, when the in-order successor is pointed to by a NULL right pointer (if successor exists)

If a process is double-threaded, the left and right NULL pointers are changed to point to the inorder predecessor and successor of the process, respectively. The predecessor threads are useful for postorder traversal and reverse inorder navigation.

A node's ancestors can also be rapidly accessed using the threads.

The following diagram shows an example of a single threaded binary tree. The dotted lines represent the threads.

The single node representation of a threaded node in C language is as follows:

``````struct Node
{
int data;
struct Node * left, * right;
}
``````

The single node representation of a threaded node in C++ language is as follows:

``````// To represent a threaded node, use any of the methods below.

// Method 1: Creating user-define data types using "struct"
struct node {
int data;
struct node * left;
struct node * right;
};

// Utilizing "class" to create user-define data types is method two.

class Node {
public:
int data;
Node * left;
Node * right;
// The value or key that needs to be added to the data portion is called Val.
Node (int val){
data = val;
// The left and right children of the node will initially be set to null.
left = NULL;
right = NULL;
// The rightThread is set to false.
}
};
``````

The single node representation of a threaded node in Java language is as follows:

``````static class Node
{
int data;
Node left, right;
}
``````

### Inorder Traversal Using the Threads:

Implementation of the in order Traversal in the Threaded Binary Tree in Python.

``````# In a tree rooted with n, there is a utility function to find the leftmost node.

def leftmostNode (nd):

if (nd == None):
return None;

while (nd. left != None):
nd = nd. left;

return nd;

# A threaded binary tree can be traversed in order using python code.

def inOrderTraversal (root):

curNd = leftmostNode (root);
while (curNd != None):
print (curNd. data," ");

# Go to in order successor if this node is one that is a thread node.
curNd = curNd. right;
else: # If not, move on to the child at the right's leftmost subtree.
curNd = leftmostNode (curNd. right);
``````

Implementation of the Inorder Traversal in the Threaded Binary Tree in C language.

``````// In a tree rooted with n, there is a utility function to find the leftmost node.

struct Node * leftMostNode (struct Node * nd)
{
if (nd == NULL)
return NULL;

while (nd -> left != NULL)
nd = nd -> left;

return nd;
}

// A threaded binary tree can be traversed in order using C code.
void inOrderTraversl (struct Node * root)
{
struct Node * curNd = leftMostNode (root);
while (curNd != NULL) {
printf (" %d ", curNd -> data);

// Go to inorder successor if this node is one that is a thread node.
curNd = curNd -> right;
else // If not, move on to the child at the right's leftmost subtree.
curNd = leftmostNode (curNd -> right);
}
}
``````

Implementation of the in order Traversal in the Threaded Binary Tree in Java language.

``````// In a tree rooted with n, there is a utility function to find the leftmost node.

Node leftMostNode (Node nd)
{
if (nd == null)
return null;

while (nd. left != null)
nd = nd. left;

return nd;
}

// A threaded binary tree can be traversed in order using C code.

static void inOrderTraversal (Node root)
{
Node curNd = leftMostNode (root);
while (curNd != null) {
System. out. printf (" %d ", curNd. data);

// Go to inorder successor if this node is one that is a thread node.
curNd = curNd. right;
else // If not, move on to the child at the right's leftmost subtree.
curNd = leftmostNode (curNd. right);
}
}
``````

Implementation of the In order Traversal in the Threaded Binary Tree in Java language.

``````// In a tree rooted with n, there is a utility function to find the leftmost node.

Node * leftMostNode (Node * nd){
if (nd == NULL)
return NULL;

while (nd -> left != NULL)
nd = nd -> left;

return nd;
}

// To traverse a threaded binary tree in order, use the CPP code.

void inOrderTraversal (Node * root){
Node * curNd = leftMostNode (root);
while (curNd != NULL) {
cout << curNd -> data << " ";

// Go to inorder successor if this node is one that is a thread node.

curNd = curNd -> right;
else // If not, move on to the child at the right's leftmost subtree.

curNd = leftmostNode (curNd -> right);
}
}
``````

Implementation of the in order Traversal in the Threaded Binary Tree in C# language.

``````// Find the leftmost node in a tree rooted with n using this handy function
Node leftMostNode (Node nd)
{
if (nd == null)
return null;

while (nd. left != null)
nd = nd .left;

return nd;
}

// To traverse a threaded binary tree in order, use the C code.

static void inOrderTraversal (Node root)
{
Node curNd = leftMostNode (root);
while (curNd != null)
{
Console. Write (" { 0} ", curNd. data);

// Go to inorder successor if this node is one that is a thread node.
curNd = curNd. right;
else // If not, move on to the child at the right's leftmost subtree.

curNd = leftmostNode (curNd. right);
}
}
``````

Implementation of the in order Traversal in the Threaded Binary Tree in Java Script language.

``````// Find the leftmost node in a tree rooted with n using this handy function
function leftMostNode (nd)
{
if (nd == null)
return null;

while (nd. left != null)
nd = nd. left;

return nd;
}

// To traverse a threaded binary tree in order, use the following JavaScript code.
function inOrderTraversal (root)
{
let curNd = leftMostNode (root);
while (curNd != null) {
document. write (curNd. data + " ");

// Go to inorder successor if this node is one that is a thread node.
curNd = curNd. right;
else // If not, move on to the child at the right's leftmost subtree.

curNd = leftmostNode (curNd. right);
}
}
``````