Iterative Search for a key ' x ' in Binary Tree | Iterative level order traversal based method to search in Binary Tree importing Queue ; Helper function that allocates a new node with the given data and None 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
from queue import Queue NEW_LINE class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def iterativeSearch ( root , x ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT q = Queue ( ) NEW_LINE q . put ( root ) NEW_LINE while ( q . empty ( ) == False ) : NEW_LINE INDENT node = q . queue [ 0 ] NEW_LINE if ( node . data == x ) : NEW_LINE INDENT return True NEW_LINE DEDENT q . get ( ) NEW_LINE if ( node . left != None ) : NEW_LINE INDENT q . put ( node . left ) NEW_LINE DEDENT if ( node . right != None ) : NEW_LINE INDENT q . put ( node . right ) NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 2 ) NEW_LINE root . left = newNode ( 7 ) NEW_LINE root . right = newNode ( 5 ) NEW_LINE root . left . right = newNode ( 6 ) NEW_LINE root . left . right . left = newNode ( 1 ) NEW_LINE root . left . right . right = newNode ( 11 ) NEW_LINE root . right . right = newNode ( 9 ) NEW_LINE root . right . right . left = newNode ( 4 ) NEW_LINE if iterativeSearch ( root , 6 ) : NEW_LINE INDENT print ( " Found " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ Found " ) NEW_LINE DEDENT if iterativeSearch ( root , 12 ) : NEW_LINE INDENT print ( " Found " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ Found " ) NEW_LINE DEDENT DEDENT