Threaded Binary Tree

       Inorder traversal of a Binary tree can either be done using recursion or with the use of a auxiliary stack. The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion. A binary tree is made threaded by making all right child pointers that would normally be NULL point to the inorder successor of the node (if it exists).

In memory representation of threaded binary tree node is represented by

LThread

Data

RThread

Each node of any binary tree stores the three fields. The left field stores the left thread value and the right field stores the right thread value. The middle field contains the actual value of the node i.e.., data.

There are two types of threaded binary trees.

Single Threaded: Where a NULL right pointers is made to point to the inorder successor (if successor exists)

        In one way inorder threading the right child of the node would point to the next node in the sequence of the inorder traversal, such a threading tree is called “Right in threaded binary tree”. Also, the left child of the node would point to the previous node in the sequence of inorder traversal, this type of tree is called as “Left in threaded binary tree”. In case both the children of the nodes point to other nodes then such a tree is called “Fully threaded binary tree”.

         Figure(1) describes the working of right in threaded binary tree in which one can see that the right child of the node points to the node in the sequence of the inorder traversal method.

Example:

        The inorder traversal shown in fig(1) will be as D B H E A F C G. Two dangling pointers are shown to point a header node as

Rchild of D is made to point to B

Rchild of E is made to point to A

Rchild of F is made to point to C
Rchild of H is made to point to E

Fig (2) describes the working of “left in threaded binary tree”.

In this case the left child of node points to the previous node in the sequence of inorder traversal. As shown in fig (2), thread of E points to B. Here B is the predecessor of E in inorder traversal. Hence, the pointer points to B. In this type of tree the pointers pointing to other nodes are as follows.

Lchild of H is made to point to B

Lchild of F is made to point to A
Lchild of G is made to point to C

Double Threaded: Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and postorder traversal.

Fig illustrates the operation of fully threaded binary tree

Right and left children are used for pointing to the nodes in inorder traversal method.

Rchild of A is made to point to C

Lchild of A is made to point to B

Rchild of B is made to point to A

Lchild of B is made to point to D

Rchild of D is made to point to B

Lchild of D is made to point to DUMMY NODE

Lchild of C is made to point to A

Rchild of C is made to point to E

Rchild of E is made to point to DUMMY NODE

Lchild of E is made to point to C