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 Code
import java . util . * ; class GFG { static class node { int data ; node left , right ; } ; static node newNode ( int data ) { node node = new node ( ) ; node . data = data ; node . left = node . right = null ; return ( node ) ; } static boolean iterativeSearch ( node root , int x ) { if ( root == null ) return false ; Stack < node > nodeStack = new Stack < node > ( ) ; nodeStack . push ( root ) ; while ( nodeStack . empty ( ) == false ) { node node = nodeStack . peek ( ) ; if ( node . data == x ) return true ; nodeStack . pop ( ) ; if ( node . right != null ) nodeStack . push ( node . right ) ; if ( node . left != null ) nodeStack . push ( node . left ) ; } return false ; } public static void main ( String [ ] args ) { node NewRoot = null ; 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 ) ; if ( iterativeSearch ( root , 6 ) ) System . out . println ( " Found " ) ; else System . out . println ( " Not ▁ Found " ) ; if ( iterativeSearch ( root , 12 ) ) System . out . println ( " Found " ) ; else System . out . println ( " Not ▁ Found " ) ; } }