preorder traversal without recursion code example
Example 1: preorder without recursion
void iterativePreorder(node *root)
{
// Base Case
if (root == NULL)
return;
// Create an empty stack and push root to it
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false)
{
// Pop the top item from stack and print it
struct node *node = nodeStack.top();
printf ("%d ", node->data);
nodeStack.pop();
// Push right and left children of the popped node to stack
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
}
Example 2: inorder traversal recursion
void printInorder(struct Node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout << node->data << " ";
/* now recur on right child */
printInorder(node->right);
}
Example 3: postorder traversal without recursion
1.1 Create an empty stack
2.1 Do following while root is not NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
Example 4: preorder traversal
#include <iostream>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int d){
data = d;
left = NULL;
right = NULL;
}
};
node* buildTree(){
int d;
cin>>d;
if(d==-1){
return NULL; //to attach a NULL pointer[in case of no child] enter -1
}
node * root = new node(d);
root->left = buildTree();
root->right = buildTree();
return root;
}
//REQUIRED FUNCTION: Inorder Traversal
void printIn(node*root){
if(root==NULL){
return;
}
//Otherwise Left Root Right
printIn(root->left);
cout<<root->data<<" ";
printIn(root->right);
}
int main(){
node* root = buildTree();
printIn(root);
return 0;
}
//SAMPLE INPUT TO RUN THE CODE ON ANY ONLINE IDE:
//8 10 1 -1 -1 6 9 -1 -1 7 -1 -1 3 -1 14 13 -1 -1 -1