Threaded Binary Tree

In Binary tree representation using linked list, if there are 2N number of reference fields, then N+1 number of reference fields are filled with NULL. This NULL pointer has no role except indicating no link(no child).

To solve this problem, A.J. Perlis and C. Thornton have suggested replacing all the Null links by pointers, called threads. A tree with a thread is called a threaded binary tree (TBT).

Threaded Binary tree is a binary tree in which all the left child pointers that are NULL points to its in-order predecessor, and all right child pointers that are NULL points to its in-order successor. If there is no in-order predecessor or in-order successor, then it points to Root node.

Threads utilize the NULL pointers waste space to improve the processing efficiency.

Consider the following binary tree:

To convert the above example binary tree into a threaded binary tree, first find the in-order traversal of that tree.

In-order traversal of above binary tree is H - D - I - B - E - A - F - J - C - G

In the binary tree, nodes H, I, E, F, J and G left child pointers are NULL. This NULL is replaced by address of its in-order predecessor respectively. This NULL is replaced by address of its in-order predecessor (I to D, E to B, F to A, J to F, G to C). Here node H does not have its in-order predecessor, so it points to the root node A.

Nodes H, I, E, J and G right child pointers are NULL. These NULL pointers are replaced by address of its in-order successor respectively (H to D, I to B, E to A, and J to C), but here the node G does not have its in-order successor, so it points to the root node A.

The converted threaded binary tree is

Advantages and disadvantages over a non-threaded binary tree:

1. The traversal for a TBT is straightforward. No recursion or stack is needed.

2. At any node, the node’s successor and predecessor can be located. In case of nonthreaded binary tree, this task is time consuming and difficult. In addition, stack is needed for the same.

3. In a threaded tree, traversal can be done in either direction, and the nodes are in fact circularly linked. Hence, any node can be reached from any other node.

4. Insertions into and deletions from a threaded tree are time consuming as the link and thread are to be manipulated.

Binary Tree and Binary search Tree

1. A BST is a special case of the binary tree. Both of them are trees with degree two, that is, each node has utmost two children.

2. The BST is a binary tree with the property that the value in a node is greater than any value in a node’s left subtree and less than any value in a node’s right subtree.

3. The BST guarantees fast search time provided the tree is relatively balanced, whereas for a binary tree, the search is relatively slow.

Given a binary tree with no duplicates, we can construct a BST from a binary tree. The process is easy; one can traverse the binary tree and construct a BST for it by inserting each node in an initially empty BST.