Do level order traversal until last node
struct Node * temp ; while ( ! q . empty ( ) ) { temp = q . front ( ) ; q . pop ( ) ; if ( temp == d_node ) { temp = NULL ; delete ( d_node ) ; return ; } if ( temp -> right ) { if ( temp -> right == d_node ) { temp -> right = NULL ; delete ( d_node ) ; return ; } else q . push ( temp -> right ) ; } if ( temp -> left ) { if ( temp -> left == d_node ) { temp -> left = NULL ; delete ( d_node ) ; return ; } else q . push ( temp -> left ) ; } } }