Programming Methodology & Data Structure

Class :B.Sc (Computer Science ) & BCA I year 

Topic : Threaded Binary Tree

Faculty : Asst Prof Sonika Mourya

Threaded Binary Tree

A threaded binary tree is a type of binary tree data structure where the empty left and right child pointers in a binary tree are replaced with threads that link nodes directly to their in-order predecessor or successor.

Threaded Binary Tree is also a binary tree in which all left child pointers that are NULL (in Linked list representation) points to its in-order predecessor, and all right child pointers that are NULL (in Linked list representation) points to its in-order successor.

Types of Threaded Binary Trees

Threaded binary trees are generally classified into two main types based on which null pointers are replaced: 

·         Single-Threaded Binary Tree: In this type, only one direction of null pointers is used for threading. Commonly, if a node's right pointer is null, it points to its in-order successor.

·         Double-Threaded (Fully Threaded) Binary Tree: Both left and right null pointers are utilized. The left null pointer of a node points to its in-order predecessor, and the right null pointer points to its in-order successor. This allows for both forward and backward in-order traversal. 

Consider the following binary tree...

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...

H - D - I - B - E - A - F - J - C - G

When we represent the above binary tree using linked list representation, 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 (I to D, E to B, F to A, J to F and G to C), but here the node H does not have its in-order predecessor, so it points to the root node A.

And 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.

Above example binary tree is converted into threaded binary tree as follows.