[This page is auto-generated; please prefer to read the article’s PDF Form.]
The Preorder, Inorder and Postorder traversals of Binary Trees are very simple to implement in their recursive form. In fact, their recursive methods very closely resemble their very definitions. In this article, we will be creating iterative variants of these methods, which use no recursive calls.
All methods shown below will be written in C language. A node of a binary tree will be represented by a structure called node, having members lc∕rc which are pointers to the left/right child of the node. It can have other members also depending upon the application’s needs. We assume that the node has no pointer to its parent node.
When the nodes have no pointer to their parents, these traversals will need to remember the parent nodes somehow, as the child and descendant nodes are traversed. In the recursive methods, this remembering automatically happens due to the use of program-stack. But in our iterative methods, we will use our own stack to track the nodes in various stages of their traversal. The stack will not only serve as a collection of nodes’ pointers to get back to them later, but also to maintain them in a specific order by virtue of its Last-In-First-Out ordering.
[Next]
Copyright © 2020 Nitin Verma. All rights reserved.