We know that every node in a binary tree contains both its data value and the address pointers for its left and right children. A null pointer is used to indicate the lack of a child node in a binary tree when a node is a leaf node or does not have any left or right children.

A binary tree is a type of tree data structure consisting of left and right nodes, or nodes, where each node has at most two descendants. The root node (the first node in the tree) is the starting point for everything.

The following are contained in each node of the tree:

• Information pointing to the left child
• Pointer to the appropriate kid
• The left and right child pointers in the case of a leaf node point to null.

## A Threaded Binary tree: What is it?

Instead of putting NULL in the left and right child pointers in a Threaded Binary Tree, the nodes will store the predecessor and successor in order.

In a threaded binary tree, the in-order successor of a node is stored for nodes whose right pointer is null (if-exists), and the in-order predecessor of a node is stored for nodes whose left pointer is null (if-exists).

As their in-order predecessor and successor do not exist, the leftmost and the rightmost child pointers of a tree always point to null.

A threaded binary tree is a variation of the normal binary tree. A threaded binary tree stores the ordered ancestor (if any) if the node's left pointer is NULL, and stores the ordered successor (if any) if the node's right pointer is NULL.

### There are two types of threaded binary trees:

With this type, if a node has a right null pointer, that right pointer is threaded to the node's successors (if any) in order.
In this type, a null pointer to the left of a node points to its in-order, predecessor, and a null pointer to its right to its in-order successor.
The node structure of a double-stranded binary tree:
A binary tree with a binary chain uses two boolean variables:

• No stack or recursion needed:
Unlike binary trees, threaded binary trees do not require stacks or recursion for traversal.
• Optimal memory usage:
Another benefit of the thread binary tree data structure is reduced memory waste. In a normal binary tree, memory is wasted if the left and right pointers of a node are NULL. But threaded binaries overcome this problem by storing predecessors/successors in order.
• Time complexity:
Traversing in-order in a threaded binary tree is faster because it gets the next node in O(1) time than a regular binary tree that takes O(height). However, insert and delete operations take longer in threaded binary trees.
• Reverse pass:
Double-stranded threaded binary trees even allow backward traversal.
• These trees allow linear traversal of elements.
• You can find the parent node without explicitly using the parent pointer
• Threaded tree allows traversing nodes back and forth sequentially
• A node contains pointers to its ordered ancestors and descendants
• For a given node, you can easily find the predecessor and successor nodes in order. So searching is much easier.

Let's discuss some drawbacks that may cause problems for programmers using it.

• Complex inserts and deletes:
Preserving the predecessor/successor order of nodes with null left/right pointers makes inserting and removing nodes a slower and much more complicated process.