Iterative Search for a key ' x ' in Binary Tree | Iterative level order traversal based method to search in Binary Tree ; A binary tree node has data , left child and right child ; Constructor that allocates a new node with the given data and NULL left and right pointers . ; An iterative process to search an element x in a given binary tree ; Base Case ; Create an empty queue for level order traversal ; Enqueue Root and initialize height ; Queue based level order traversal ; See if current node is same as x ; Remove current node and enqueue its children ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : int data ; node * left ; node * right ; node ( int data ) { this -> data = data ; this -> left = NULL ; this -> right = NULL ; } } ; bool iterativeSearch ( node * root , int x ) { if ( root == NULL ) return false ; queue < node * > q ; q . push ( root ) ; while ( q . empty ( ) == false ) { node * node = q . front ( ) ; if ( node -> data == x ) return true ; q . pop ( ) ; if ( node -> left != NULL ) q . push ( node -> left ) ; if ( node -> right != NULL ) q . push ( node -> right ) ; } return false ; } int main ( ) { node * NewRoot = NULL ; node * root = new node ( 2 ) ; root -> left = new node ( 7 ) ; root -> right = new node ( 5 ) ; root -> left -> right = new node ( 6 ) ; root -> left -> right -> left = new node ( 1 ) ; root -> left -> right -> right = new node ( 11 ) ; root -> right -> right = new node ( 9 ) ; root -> right -> right -> left = new node ( 4 ) ; iterativeSearch ( root , 6 ) ? cout << " Found STRNEWLINE " : cout << " Not ▁ Found STRNEWLINE " ; iterativeSearch ( root , 12 ) ? cout << " Found STRNEWLINE " : cout << " Not ▁ Found STRNEWLINE " ; return 0 ; }