# What is a Threaded Binary Tree?

When we consider those binary trees that are interlinked with each other, we do come across the fact that the fields present in there do consist of NULL values that ultimately lead to the damage and wastage of the storage space that we use for the tree. If we have a binary tree that comprises n number of nodes, then the n+1 link fields would definitely have the NULL values.

In order to save and manage the wastage of this storage space, a new convention was introduced by two people named Perlis and Thornton. In this particular method, the links which were previously filled with NULL are significantly replaced by threads. So, the binary trees that contains threads as a replacement, those binary trees are termed threaded binary trees. Each and every node in a threaded binary tree either contain a link to their child node or thread to various other nodes present in the tree.

## Types of threaded binary tree

There are majorly two types of the threaded binary trees. They are given below: -

Now, we will explain each of these trees one by one in the given section.

In this type of threaded binary tree, the thread usually occurs either at the left or right link of the field of a given node. If, for example, say the link pops up at the right link of the field, then it will ultimately lead and point to the next adjacent node that will appear and perform the inorder traversal operation on the tree.

Such types of trees are vividly known as the Right threaded binary trees. Whereas on the other hand, if suppose the link pops out at the left link of a given node, then it will ultimately lead and point to the next adjacent node that will appear and perform the inorder predecessor operation on the tree. Such types of trees are known as the left threaded binary trees. In such kind of threaded binary trees, the right link of the last node and the left link of the first node generally occupies a NULL value.

A question arises here how do we distinguish links from threads so the answer to the same question is that threads are generally denoted by dotted lines and are pretty visible to human eyes as well.

The above picture depicts that the inorder traversal and exploration of the threaded binary tree turns out to be vivid with the nodes D, B, E, A, C, and F. When this given tree is represented as the right threaded binary tree, the right link present on the tree placed on the leaf node D that also contains NULL value is generally exchanged with a thread which is represented by a dotted line. This node directly heads out and points to node B, which is the successor of node D. Likewise, in the same way, all the other trees are allotted threads.