Threaded Binary Tree

Threaded Binary Tree

A tree can be represented by using

• Array Representation 

OR

• Linked List Representation

Using Array Representation

In array representation to represent the Binary tree we take One Dimensional Array.

Maximum size of array = 2n+1.

Using Linked List Representation

If any node is not having a child we use a null pointer. These special pointers are threaded and the binary tree having such pointer is called a Threaded Binary Tree.

A thread in binary tree is represented by a dotted line. 

There are a number of a null pointer than actual pointer. 

These null pointer does not play any role except indicating there is no child .

There are 3 ways to thread a binary tree.

1. In order traversal when the write null pointer of each leaf node can be replaced by a threat to the successor of that node. Then, it is called a right thread, neckline and the resultant tree called a right threaded tree or right threaded binary tree.
2. When the last null pointer of each note can be replaced by a thread to the predecessor of that node under in order traversal, it called Left Thread and the Resultant Tree will call a left threaded tree.
3. In order traversal the left and right null pointer can be used to point predecessor and successor of that node respectively. Then the resultant tree is called a Full Threaded Tree.

In the  threaded binary tree there is only one thread is used then it is called as One Way Threaded Tree. And when both the thread are used then it is called Two Way Threaded Tree.

The pointer points to the root node when there is no inorder predecessors and successor.