Page 209 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes The INORDER traversal for the above tree is — D B A E C. So, the respective Threaded Binary
tree will be:

Figure 12.9: Threaded Binary Tree created from Normal Binary Tree

B has no right child and its inorder successor is A and so a thread has been made in between
them. Similarly, for D and E. C has no right child but it has no in-order successor even, so it has
a hanging thread.

12.3.2 Non-recursive Traversal using a Threaded Binary Tree

As this is a non-recursive method for traversal, it has to be an iterative procedure; meaning, all
the steps for the traversal of a node have to be under a loop so that the same can be applied to all
the nodes in the tree.

We will consider the IN-ORDER traversal again. Here, for every node, we’ll visit the left sub-
tree (if it exists) first (if and only if we haven’t visited it earlier); then we visit (i.e. print its value,
in our case) the node itself and then the right sub-tree (if it exists).

Did u know? If the right sub-tree is not there, we check for the threaded link and make the
threaded node the current node in consideration.

Example:

Figure 12.10: Right Sub-tree Missing

202 LOVELY PROFESSIONAL UNIVERSITY