Skip to content
site-logo
  • Home
  • Blog
  • JavaScript
  • Machine Learning
  • Numerical Techniques C++
  • Data Structures C++
  • Typing Guide
site-logo
Home / Data Structures C++ / Threaded Binary Tree | Single & Double Threaded

Threaded Binary Tree | Single & Double Threaded

ByLonz Updated onAugust 28, 2021
Data Structures C++
threaded binary tree
Ad
Table of contents
  1. What is threaded binary tree?
    1. How to create a threaded binary tree
    2. Why threads
  2. Types of Threaded Binary Tree
    1. Single-Threaded Binary Tree:
    2. Double Threaded Binary Tree:
    3. Threaded binary tree Structure
    4. Use of Boolean Variables
    5. What happens with righmost and leftmost null nodes?
  3. Operations in Threaded Binary Tree
  4. Advantages of Threaded Binary Tree
    1. Disadvantages
  5. Time and Space Complexity
  6. C Program
  7. FAQ

What is threaded binary tree?

The Threaded Binary Tree is a linked list representation of a Binary Tree, in which the NULL pointers of the leaf nodes contain the address of their predecessor and successor nodes in the inorder traversal.

It makes use of the null pointers in an efficient way to make operations faster and to save some space.

Ad
threaded binary tree impl

In the above binary tree, there is a total of 12 pointers, of which there are 7 null pointers and only 5 actual pointers.

In general, for any binary tree with n nodes, there will be n+1 null pointers and 2n total pointers. The objective here is to make effective use of these n+1 pointers.

A.J.Perlis and C. Thornton jointly proposed this idea to replace all the null pointers with the appropriate pointer values called Threads.

How to create a threaded binary tree

If in a given binary tree, the left link ( lchild ) of a node p is normally equal to NULL, then this link is replaced by a pointer to the node which immediately precedes node p in the in-order traversal.

And similarly, if the right link ( rchild ) of a node p is equal to NULL, then this link is replaced by a pointer to its inorder successor node.

Why threads

The main reason to use threaded binary trees is to make the operations faster as compared to binary trees and binary search trees.

Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers. We can use these pointers to help us in inorder traversals.

The null pointers of leaf nodes are set to their predecessor and successor nodes in order to avoid the usage of other data structures such as stacks.

Threaded trees are symmetric: there are left threads for moving to node predecessors and right threads for a move to node successors, But traversals are not symmetric.

Types of Threaded Binary Tree

There are two types of threaded binary trees:

Ad
  1. Single Threaded Binary Tree
  2. Double Threaded Binary Tree

Single-Threaded Binary Tree:

 In a single-threaded binary tree, only the right NULL pointer is pointed to in order successor.

single threaded
// single threaded binary tree
struct Node{
    int data;
    Node *left;
    Node *right;
    bool rightThread;
}
Code language: C++ (cpp)

Double Threaded Binary Tree:

In a double-threaded binary tree, both the right and left NULL pointers are pointed to in order successor and predecessor respectively.

double threaded binary tree
//double threaded binary tree

struct Node{
    int data ;
    Node *left ;
    Node *right ;
    bool leftThread ;
    bool rightThread ;
 }
Code language: JavaScript (javascript)

Threaded binary tree Structure

The structure of a node in this type of binary tree has two additional attributes. Both right thread and LeftThread attributes are of type Boolean ( true or false ).

  • rightThread
  • leftThread

Following is the node structure in a Single-threaded binary tree and Double threaded binary tree:

  // single threaded

struct Node{
   int data ;
   Node *left ;
   Node *right ;
   bool rightThread ;
}

  // double threaded

struct Node{
   int data ;
   Node *left ;
   Node *right ;
   bool leftThread ;
   bool rightThread ;
}
Code language: JavaScript (javascript)

Use of Boolean Variables

The use of bool variables in a threaded binary tree is to differentiate between the links to the child nodes and parent nodes.

  • If the bool variable is set to true that means pointer is pointing to child node
  • If the bool is set to false that means that pointer is pointing to its parent node.

What happens with righmost and leftmost null nodes?

In this tree, the left most and right most pointers do not have in order predecessor or in order successor so they are made to point to a dummy node.

Operations in Threaded Binary Tree

The following operations are performed in a threaded binary tree.

  1. Insertion
  2. Deletion
  3. Search

Advantages of Threaded Binary Tree

  • Faster Traversal
  • By using threads, we neglect the recursive method of traversing a Tree
  • It does not use stack, thus saves time & space.
  • Optimal memory usage
  • Backward traversal
  • No need for stacks or recursion
  • Better efficiency

Disadvantages

  • Complicated insertion and deletion
  • Extra memory usage
  • Difficult to code

Time and Space Complexity

The Time complexity for different operations in a threaded binary tree is as follows:

  • Time complexity for insertion is log(n)
  • Time complexity for deletion is log(n)
  • Time complexity for searching is log(n)

The Space complexity of the threaded binary tree for insertion is O(1), and for deletion and searching, we do not require any extra space.

C Program

#include <bits/stdc++.h>
using namespace std;

struct Node {
   struct Node *left, *right;
   int info;

   // True if left pointer points to predecessor
   // in Inorder Traversal
   bool lthread;

   // True if right pointer points to predecessor
   // in Inorder Traversal
   bool rthread;
};

struct Node *search( struct Node *root , int key ){

    Node *ptr = root ;

    

    while( ptr != nullptr  ){

        if( ptr->info == key ){
            // indicating that the element is found then
            return ptr ;
        }else if( ptr->info < key ){
            // moving to inorder predecessor of the current node 
            ptr = ptr->right ;
        }else{
            // moving to inorder successor of the current node
           ptr = ptr->left ;
        }

    }

    // if element is not found then we can return nullptr indicating element not 
    // found in the given binary search tree
    return nullptr ;

} 

// Insert a Node in Binary Threaded Tree
struct Node* insert(struct Node* root, int ikey)
{
   // Searching for a Node with given value
   Node* ptr = root;
   Node* par = NULL; // Parent of key to be inserted
   while (ptr != NULL) {
       // If key already exists, return
       if (ikey == (ptr->info)) {
           printf("Duplicate Key !\n");
           return root;
       }

       par = ptr; // Update parent pointer

       // Moving on left subtree.
       if (ikey < ptr->info) {
           if (ptr->lthread == false)
               ptr = ptr->left;
           else
               break;
       }

       // Moving on right subtree.
       else {
           if (ptr->rthread == false)
               ptr = ptr->right;
           else
               break;
       }
   }

   // Create a new Node
   Node* tmp = new Node;
   tmp->info = ikey;
   tmp->lthread = true;
   tmp->rthread = true;

   if (par == NULL) {
       root = tmp;
       tmp->left = NULL;
       tmp->right = NULL;
   }
   else if (ikey < (par->info)) {
       tmp->left = par->left;
       tmp->right = par;
       par->lthread = false;
       par->left = tmp;
   }
   else {
       tmp->left = par;
       tmp->right = par->right;
       par->rthread = false;
       par->right = tmp;
   }

   return root;
}

// Returns inorder successor using left
// and right children (Used in deletion)
struct Node* inSucc(struct Node* ptr)
{
   if (ptr->rthread == true)
       return ptr->right;

   ptr = ptr->right;
   while (ptr->lthread == false)
       ptr = ptr->left;

   return ptr;
}

// Returns inorder successor using rthread
// (Used in inorder)
struct Node* inorderSuccessor(struct Node* ptr)
{
   // If rthread is set, we can quickly find
   if (ptr->rthread == true)
       return ptr->right;

   // Else return leftmost child of right subtree
   ptr = ptr->right;
   while (ptr->lthread == false)
       ptr = ptr->left;
   return ptr;
}

// Printing the threaded tree
void inorder(struct Node* root)
{
   if (root == NULL)
       printf("Tree is empty");

   // Reach leftmost Node
   struct Node* ptr = root;
   while (ptr->lthread == false)
       ptr = ptr->left;

   // One by one print successors
   while (ptr != NULL) {
       printf("%d ", ptr->info);
       ptr = inorderSuccessor(ptr);
   }
}

struct Node* inPred(struct Node* ptr)
{
   if (ptr->lthread == true)
       return ptr->left;

   ptr = ptr->left;
   while (ptr->rthread == false)
       ptr = ptr->right;
   return ptr;
}

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* case1(struct Node* root, struct Node* par,
                  struct Node* ptr)
{
   // If Node to be deleted is root
   if (par == NULL)
       root = NULL;

   // If Node to be deleted is left
   // of its parent
   else if (ptr == par->left) {
       par->lthread = true;
       par->left = ptr->left;
   }
   else {
       par->rthread = true;
       par->right = ptr->right;
   }

   // Free memory and return new root
   free(ptr);
   return root;
}

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* case2(struct Node* root, struct Node* par,
                  struct Node* ptr)
{
   struct Node* child;

   // Initialize child Node to be deleted has
   // left child.
   if (ptr->lthread == false)
       child = ptr->left;

   // Node to be deleted has right child.
   else
       child = ptr->right;

   // Node to be deleted is root Node.
   if (par == NULL)
       root = child;

   // Node is left child of its parent.
   else if (ptr == par->left)
       par->left = child;
   else
       par->right = child;

   // Find successor and predecessor
   Node* s = inSucc(ptr);
   Node* p = inPred(ptr);

   // If ptr has left subtree.
   if (ptr->lthread == false)
       p->right = s;

   // If ptr has right subtree.
   else {
       if (ptr->rthread == false)
           s->left = p;
   }

   free(ptr);
   return root;
}

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* case3(struct Node* root, struct Node* par,
                  struct Node* ptr)
{
   // Find inorder successor and its parent.
   struct Node* parsucc = ptr;
   struct Node* succ = ptr->right;

   // Find leftmost child of successor
   while (succ->lthread==false) {
       parsucc = succ;
       succ = succ->left;
   }

   ptr->info = succ->info;

   if (succ->lthread == true && succ->rthread == true)
       root = case1(root, parsucc, succ);
   else
       root = case2(root, parsucc, succ);

   return root;
}

// Deletes a key from threaded BST with given root and
// returns new root of BST.
struct Node* deleteFromThreadedBst(struct Node* root, int target)
{
   // Initialize parent as NULL and
   // Node as root.
   struct Node *par = NULL, *ptr = root;

   // Set true if key is found
   int found = 0;

   // Search key in BST : find Node and its
   // parent.
   while (ptr != NULL) {
       if (target == ptr->info) {
           found = 1;
           break;
       }
       par = ptr;
       if (target < ptr->info) {
           if (ptr->lthread == false)
               ptr = ptr->left;
           else
               break;
       }
       else {
           if (ptr->rthread == false)
               ptr = ptr->right;
           else
               break;
       }
   }

   if (found == 0)
       printf("target not present in tree\n");

   // Two Children
   else if (ptr->lthread == false && ptr->rthread == false)
       root = case3(root, par, ptr);

   // Only Left Child
   else if (ptr->lthread == false)
       root = case2(root, par, ptr);

   // Only Right Child
   else if (ptr->rthread == false)
       root = case2(root, par, ptr);

   // No child
   else
       root = case1(root, par, ptr);

   return root;
}

// Driver Program
int main()
{
   struct Node* root = NULL , *temp = NULL;

   root = insert(root, 1);
   root = insert(root, 3);
   root = insert(root, 5);
   root = insert(root, 7);
   root = insert(root, 12);
   root = insert(root, 2);
   root = insert(root, 10);
   root = insert(root, 6);
   
   temp = search(root , 5) ;

   if( temp ) cout<<"Element with value 5 found\n" ;
   else cout<<"element doesn't exist in the given binary threaded tree\n" ;

   root = deleteFromThreadedBst(root, 6);
   inorder(root);

   return 0;
}
Code language: PHP (php)

FAQ

What is a fully threaded binary tree?

A double-threaded binary tree is also called a fully threaded binary tree.

What are the types of threaded binary trees?

1. Single-threaded binary tree
2. Double-threaded binary tree

Post navigation

Previous Previous
Binary Search Tree | BST Operations Insertion, Deletion, Search
NextContinue
What is Graph Data Structure | Graph Types & Traversal C++
Search

Ad

Categories

  • C++ Programing
  • C++ Programs
  • Computer Graphics
  • Data Structures C++
  • JavaScript
  • Machine Learning
  • Numerical Techniques C++
  • Processor
  • Tech Updates
  • Typing Guide
  • Un Categorised

Recent Posts

  • NetSuite Cloud ERP Features
  • Is i7 Better Than i5
  • setTimeout vs setInterval JavaScript Methods
  • String Formatting In JavaScript

Ad


  • Home
  • Blog
  • Privacy Policy
  • Disclaimer
  • Sitemap

Copyright © 2023 Tech In Detail

  • Home
  • Blog
  • JavaScript
  • Machine Learning
  • Numerical Techniques C++
  • Data Structures C++
  • Typing Guide
Search