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;
    bool rightThread; 
}

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;
    bool rightThread;
};
 
// Utilizing "class" to create user-define data types is method two.


class Node {
public:
    int data;
    Node * left;
    Node * right;
    bool rightThread;
    // 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.
        rightThread = false;
    }
};

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

static class Node
{
    int data;
    Node left, right;
    boolean rightThread; 
}

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.
        if (curNd. rightThread):
            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.
        if (curNd -> rightThread)
            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.
        if (curNd. rightThread)
            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.


        if (curNd -> rightThread)
            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.
    if (curNd. rightThread)
      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.
        if (curNd. rightThread)
            curNd = curNd. right;
        else // If not, move on to the child at the right's leftmost subtree.


            curNd = leftmostNode (curNd. right);
        }
}

Threaded Binary Tree Advantages:

1. A linear traversal of the items in this Tree is possible.
2. Since it does a linear traversal instead of using a stack, memory is conserved.
3. Allows for the automatic use of the parent pointer without explicitly doing so.
4. The nodes of a threaded tree can be traversed both forward and backward in an orderly method.
5. Pointers to the previous and successor nodes are contained in nodes.
6. We can quickly locate the predecessor and successor nodes for a given node. As a result, searching is significantly simpler.

Threaded Binary Tree Disadvantages:

1. Each node in a threaded binary tree requires additional data (extra memory) to show whether its left or right node indicated its children, or whether it was the predecessor or successor in the order of the nodes. The node requires more RAM for implementation.
2. Insertion and deletion are much harder and take much longer than they do for regular links because threads and regular links both need to be maintained.