do level order traversal until we find an empty place , i . e . either left child or right child of some node is pointing to NULL .
queue < Node * > q ; q . push ( root ) ; while ( ! q . empty ( ) ) { Node * temp = q . front ( ) ; q . pop ( ) ; if ( temp -> left != NULL ) q . push ( temp -> left ) ; else { temp -> left = CreateNode ( data ) ; return root ; } if ( temp -> right != NULL ) q . push ( temp -> right ) ; else { temp -> right = CreateNode ( data ) ; return root ; } } }