Inorder Tree Traversal without Recursion | C ++ program to print inorder traversal using stack . ; A binary tree Node has data , pointer to left child and a pointer to right child ; Iterative function for inorder tree traversal ; traverse the tree ; Reach the left most Node of the curr Node ; place pointer to a tree node on the stack before traversing the node 's left subtree  ; Current must be NULL at this point ; we have visited the node and its left subtree . Now , it ' s ▁ right ▁ ▁ subtree ' s turn ; Driver program to test above functions ; Constructed binary tree is 1 / \ 2 3 / \ 4 5
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left ; struct Node * right ; Node ( int data ) { this -> data = data ; left = right = NULL ; } } ; void inOrder ( struct Node * root ) { stack < Node * > s ; Node * curr = root ; while ( curr != NULL || s . empty ( ) == false ) { while ( curr != NULL ) { s . push ( curr ) ; curr = curr -> left ; } curr = s . top ( ) ; s . pop ( ) ; cout << curr -> data << " ▁ " ; curr = curr -> right ; } } 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 ) ; inOrder ( root ) ; return 0 ; }