iterative inorder traversal
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, left child and right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the given data and
NULL left and right pointers.*/
struct node* newNode(int data)
{
struct node* node = new struct node;
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// An iterative process to print preorder traversal of Binary tree
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);
/* 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 */
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);
}
}
// Driver program to test above functions
int main()
{
/* Constructed binary tree is
10
/ \
8 2
/ \ /
3 5 2
*/
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;
}
// C program for different tree traversals
#include <iostream>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node
{
int data;
struct Node* left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct Node* node)
{
if (node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
cout << node->data << " ";
}
/* Given a binary tree, print its nodes in inorder*/
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);
}
/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
/* first print data of node */
cout << node->data << " ";
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
/* Driver program to test above functions*/
int main()
{
struct Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "\nPreorder traversal of binary tree is \n";
printPreorder(root);
cout << "\nInorder traversal of binary tree is \n";
printInorder(root);
cout << "\nPostorder traversal of binary tree is \n";
printPostorder(root);
return 0;
}
// C++ program to print inorder traversal
// using stack.
#include<bits/stdc++.h>
using namespace std;
/* A binary tree Node has data, pointer to left child
and a pointer to right child */
struct Node
{
int data;
struct Node* left;
struct Node* right;
Node (int data)
{
this->data = data;
left = right = NULL;
}
};
/* Iterative function for inorder tree
traversal */
void inOrder(struct Node *root)
{
stack<Node *> s;
Node *curr = root;
while (curr != NULL || s.empty() == false)
{
/* Reach the left most Node of the
curr Node */
while (curr != NULL)
{
/* place pointer to a tree node on
the stack before traversing
the node's left subtree */
s.push(curr);
curr = curr->left;
}
/* Current must be NULL at this point */
curr = s.top();
s.pop();
cout << curr->data << " ";
/* we have visited the node and its
left subtree. Now, it's right
subtree's turn */
curr = curr->right;
} /* end of while */
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
inOrder(root);
return 0;
}