Inorder Non | C ++ program to print inorder traversal of a Binary Search Tree ( BST ) without recursion and stack ; BST Node ; A utility function to create a new BST node ; A utility function to insert a new node with given key in BST ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; Function to print inorder traversal using parent pointer ; Start traversal from root ; If left child is not traversed , find the leftmost child ; Print root 's data ; Mark left as done ; If right child exists ; If right child doesn 't exist, move to parent ; If this node is right child of its parent , visit parent 's parent first ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { Node * left , * right , * parent ; int key ; } ; Node * newNode ( int item ) { Node * temp = new Node ; temp -> key = item ; temp -> parent = temp -> left = temp -> right = NULL ; return temp ; } Node * insert ( Node * node , int key ) { if ( node == NULL ) return newNode ( key ) ; if ( key < node -> key ) { node -> left = insert ( node -> left , key ) ; node -> left -> parent = node ; } else if ( key > node -> key ) { node -> right = insert ( node -> right , key ) ; node -> right -> parent = node ; } return node ; } void inorder ( Node * root ) { bool leftdone = false ; while ( root ) { if ( ! leftdone ) { while ( root -> left ) root = root -> left ; } printf ( " % d ▁ " , root -> key ) ; leftdone = true ; if ( root -> right ) { leftdone = false ; root = root -> right ; } else if ( root -> parent ) { while ( root -> parent && root == root -> parent -> right ) root = root -> parent ; if ( ! root -> parent ) break ; root = root -> parent ; } else break ; } } int main ( void ) { Node * root = NULL ; root = insert ( root , 24 ) ; root = insert ( root , 27 ) ; root = insert ( root , 29 ) ; root = insert ( root , 34 ) ; root = insert ( root , 14 ) ; root = insert ( root , 4 ) ; root = insert ( root , 10 ) ; root = insert ( root , 22 ) ; root = insert ( root , 13 ) ; root = insert ( root , 3 ) ; root = insert ( root , 2 ) ; root = insert ( root , 6 ) ; printf ( " Inorder ▁ traversal ▁ is ▁ STRNEWLINE " ) ; inorder ( root ) ; return 0 ; }