Iterative Search for a key ' x ' in Binary Tree | An iterative method to search an item in Binary Tree ; 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 . ; iterative process to search an element x in a given binary tree ; Base Case ; Create an empty stack and push root to it ; Do iterative preorder traversal to search x ; See the top item from stack and check if it is same as x ; Push right and left children of the popped node to stack ; Driver program
#include <iostream> NEW_LINE #include <stack> NEW_LINE using namespace std ; struct node { int data ; struct node * left , * right ; } ; struct node * newNode ( int data ) { struct node * node = new struct node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } bool iterativeSearch ( node * root , int x ) { if ( root == NULL ) return false ; stack < node * > nodeStack ; nodeStack . push ( root ) ; while ( nodeStack . empty ( ) == false ) { struct node * node = nodeStack . top ( ) ; if ( node -> data == x ) return true ; nodeStack . pop ( ) ; if ( node -> right ) nodeStack . push ( node -> right ) ; if ( node -> left ) nodeStack . push ( node -> left ) ; } return false ; } int main ( void ) { struct node * NewRoot = NULL ; struct node * root = newNode ( 2 ) ; root -> left = newNode ( 7 ) ; root -> right = newNode ( 5 ) ; root -> left -> right = newNode ( 6 ) ; root -> left -> right -> left = newNode ( 1 ) ; root -> left -> right -> right = newNode ( 11 ) ; root -> right -> right = newNode ( 9 ) ; root -> right -> right -> left = newNode ( 4 ) ; iterativeSearch ( root , 6 ) ? cout << " Found STRNEWLINE " : cout << " Not ▁ Found STRNEWLINE " ; iterativeSearch ( root , 12 ) ? cout << " Found STRNEWLINE " : cout << " Not ▁ Found STRNEWLINE " ; return 0 ; }