Threaded Binary Tree | Single & Double Threaded

threaded binary tree

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.

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.

Ad

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.

Ad

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:

  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:

Ad
// 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

Ad