Non Recursive Inorder Traversal For 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 INORDER 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). If the right sub-tree is not there, we check for the threaded link and make the threaded node the current node in consideration. Please, follow the example given below.
Read more about this topic: Threaded Binary Tree
Famous quotes containing the words threaded and/or tree:
“It was a tangled and perplexing thicket, through which we stumbled and threaded our way, and when we had finished a mile of it, our starting-point seemed far away. We were glad that we had not got to walk to Bangor along the banks of this river, which would be a journey of more than a hundred miles. Think of the denseness of the forest, the fallen trees and rocks, the windings of the river, the streams emptying in, and the frequent swamps to be crossed. It made you shudder.”
—Henry David Thoreau (1817–1862)
“Blessed is the man that walketh not in the counsel of the ungodly,
nor standeth in the way of sinners, nor sitteth in the seat of the
scornful.
But his delight is in the law of the Lord; and in his law doth he
meditate day and night.
And he shall be like a tree planted by the rivers of water, that
bringeth forth his fruit in his season; his leaf also shall not wither;
and whatsoever he doeth shall prosper.”
—Bible: Hebrew Psalm I (l. I, 1–3)