A `binary tree`

is a data structure where every node can have up to two children. There are different ways of traversing through the tree, one of them is in-order traversal. In `inorder traversal`

, you visit the nodes “in order”, which means if the binary tree were a binary search tree, an inorder traversal would give us the elements in an increasing order

However, to perform this traversal, we need to make use of recursion. If not recursion we need to use a stack to mimic the recursion. A `Threaded Binary Tree`

lets us perform `inorder traversal`

without the use of recursion or stack.

## Takeaways

Unlike binary trees, `threaded binary trees`

do not require a stack or recursion for their traversal.

## What Is a Threaded Binary Tree?

In a `threaded binary tree`

, either of the `NULL`

pointers of leaf nodes is made to point to their successor or predecessor nodes

## What is the need for a Threaded Binary Tree?

In a `regular tree`

, the space complexity for insertion/ deletion can range from logarithmic to linear time. We get log time in a balanced binary tree and linear time is the worst case in an unbalanced tree.

In applications where we have a constraint of space, or even when there is a use case of storing large trees in memory, we might need to save up on the extra space invested in the recursion depth. A threaded binary tree is advantageous in such scenarios where space usage is critical

## Types of Threaded Binary Trees

Following are Types of Threaded Binary Trees:

**Single Threaded**

`Diagramatic Representation`

of `Single Threaded Binary Tree`

As we can see from the diagram, only the right pointer which is NULL point to the successor node in a single-threaded binary tree

**Double Threaded**

`Diagramatic Representation`

of `Double Threaded Binary Tree`

In a double threaded Binary tree, the left pointer also points to its predecessor node

## Node Structure in a 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 ;
}
```

## What Is the Significance of a Bool Variable in a Structure?

Consider a `single threaded binary tree`

. Any node in the binary tree can have its right pointer either to a child or the next successor node (which might not be the child node).

Hence we need a boolean variable that tells us whether the right pointer is pointing to a child or the next successor node

## Inorder Traversal Using Threads

Let us see how `inorder traversal`

actually works in a `single threaded binary tree`

now

The following steps take place in the diagram above:

- We go to the left most
`node 1`

`Node 1`

has boolean rightThread as true, hence next we visit its inOrder successor`node 2`

`Node 2`

has a right child, so we visit`Node 3`

next`Node 3`

does not have a right child, ie the rightThread boolean is true, so we visit`Node 4`

next`Node 4`

has a right child so we visit`Node 5`

and finish traversal

We will write a function which will give us the **inOrder successor of a node**:

```
struct Node* findSuccesor(Node* node) {
if(node -> rightTread == true){
return node --> right; //straightaway return the parent node if present
}
if(root -> right != NULL){
while(root -> left != NULL) { //if left child is present return the leftmost node
root = root -> left;
}
return root;
}
return NULL; //if no children are present then this is the last node
```

**The following code prints the node inOrder:**

```
void printInOrder() {
while(root -> left != NULL){
root = root -> left;
while(root != NULL){
print(root->val);
root = findSuccesor(root);
}
}
```

## The Operations in a Threaded Binary Tree

Let us now discuss how to `insert`

/ `search`

/ `delete`

in a `double threaded binary tree`

. We will be considering a binary search tree while discussing these example

### 1. Insert

To `insert`

a key, we first need to find the to-be parent of the new key. In order to find the parent, we need to follow these steps:

- If the node we wish to
`insert`

is greater than the current node, then we need to move right - If the node we wish to
`insert`

is lesser than the current node, then we need to move left - In a usual
`BST`

, we might encounter a node that has its left or right child`NULL`

, however, this is not possible in a double threaded`BST`

. In such cases, we have to break out of the loop of these 3 steps, as that node will be the parent

**Code:**

```
void insert(Node* root, int key) {
Node* curr = root;
Node* parent = NULL; //to keep track of the to-be parent
while(curr != NULL) {
if(curr->val == key){
print("Node is already present in the tree");
break;
}
parent = curr;
if(key > curr->val){
if(curr->rightThread == false)
curr = curr->right;
else //means there is no right child of curr
break;
}
else{
if(curr->leftThread == true)
curr = curr->left;
else
break;
}
}
Node* newNode = new Node;
newNode->val = key;
newNode->leftThread = true;
newNode->rightThread = false;
if(parent == NULL){
root = temp;
root->left = NULL;
root->right = NULL;
}
else if(key < parent.val){
newNode->left = parent->left;
newNode->right = parent;
newNode->leftThread = false;
parent->left = newNode;
}
else{
newNode->right = parent->right;
newNode->left = parent;
newNode->rightThread = false;
parent->right = newNode;
}
}
```

### 2. Search

`Searching`

a node in a `double threaded binary tree`

is very easy due to its structure. We traverse through as follows:

- If the key we are searching for is lesser than the value of the
`currentNode`

, we move left - If the key is greater than the value of the current node, we move right

**Code:**

```
Node* search(Node* root, int key){
Node* curr = root;
while(curr != NULL){
if(curr.val == key){
return curr;
}
if(key < curr.val){
curr = curr->left;
}
else{
curr = curr->right;
}
}
return NULL;
}
```

### 3. Delete

`Deletion`

of a node involves a lot of cases, hence we will discuss the approach and write the pseudo code only. In all these cases, it is assumed that you have searched for the node to be deleted in the `BST`

**Case 1: Deleting a leaf node**

If the leaf node to be `deleted`

is the left child of a parent node, we need to update the predecessor node of the parent node.

```
if(nodeToBeDeleted->rightThread == true){
parentNode = nodeToBeDeleted->right;
parentNode->left = nodeToBeDeleted->left;
}
```

If the leaf node to be `deleted`

is the right child of a parent node, we need to update the successor node of the parent node.

```
if(nodeToBeDeleted->leftThread == true){
parentNode = nodeToBeDeleted->left;
parentNode->right = nodeToBeDeleted->right;
}
```

**Case 2: Deleting a node that has one child**

If the node that is to be `deleted`

has a left child, the inOrder successor of the child node has to be updated

If the node that is to be `deleted`

has a right child, the inOrder predecessor of the child node has to be updated

**Case 3: Deleting a node that has two children**

In such a case, we need to replace the node to be `deleted`

with its inOrder successor:

- The inOrder successor of the node to be
`deleted`

is found out - Then we find the leftmost child of the successor node, which is a replacement for the node to be
`deleted`

- We copy the information of the leftmost child in the node to be
`deleted`

, and then delete the leftmost child using either case 1 or case 2

## Time and Space Complexity of Operations

The time complexity for `insertion`

, `deletion`

, and `searching`

in a threaded binary tree is the same as that of a `BST`

, as we need to perform operations maximum up to the depth of the tree. The depth of a `threaded BST`

is also `log(n)`

where `n`

is the total number of nodes in the tree

Hence all operations take up `O(log(n))`

time complexity

However, since we do not use any extra space for any of the operations, the auxilliary space complexity is `O(1)`

## Conclusion

- A
`threaded binary tree`

is a tree that maintains the predecessor and successor node of every node in the tree - If the right child of a node is
`NULL`

, the right pointer of that node points to the inOrder successor of the node - If the left child of a node is
`NULL`

, the left pointer of that node points to the inOrder predecessor of the node - Accordingly, if a tree maintains just the right successor information with its nodes, it is a single threaded binary tree
- If the tree maintains both the successor and predecessor information, it is a double threaded binary tree
- In the node structure, we maintain a boolean field that tells whether the left or right pointer is pointing to a child node or a parent node
- A threaded binary tree lets us perform traversal, insertion, deletion and search operations without using any extra space
- The time complexity of these operations however remains
`O(log(n))`