Iterative Preorder Traversal | C ++ program to implement iterative preorder traversal ; A binary tree node has data , left child and right child ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; An iterative process to print preorder traversal of Binary tree ; Base Case ; Create an empty stack and push root to it ; Pop all items one by one . Do following for every popped item a ) print it b ) push its right child c ) push its left child Note that right child is pushed first so that left is processed first ; Pop the top item from stack and print it ; Push right and left children of the popped node to stack ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { int data ; struct node * left ; struct node * right ; } ; struct node * newNode ( int data ) { struct node * node = new struct node ; node -> data = data ; node -> left = NULL ; node -> right = NULL ; return ( node ) ; } void iterativePreorder ( node * root ) { if ( root == NULL ) return ; stack < node * > nodeStack ; nodeStack . push ( root ) ; while ( nodeStack . empty ( ) == false ) { struct node * node = nodeStack . top ( ) ; printf ( " % d ▁ " , node -> data ) ; nodeStack . pop ( ) ; if ( node -> right ) nodeStack . push ( node -> right ) ; if ( node -> left ) nodeStack . push ( node -> left ) ; } } int main ( ) { struct node * root = newNode ( 10 ) ; root -> left = newNode ( 8 ) ; root -> right = newNode ( 2 ) ; root -> left -> left = newNode ( 3 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 2 ) ; iterativePreorder ( root ) ; return 0 ; }