Do level order traversal to find deepest node ( temp ) and node to be deleted ( key_node )
while ( ! q . empty ( ) ) { temp = q . front ( ) ; q . pop ( ) ; if ( temp -> key == key ) key_node = temp ; if ( temp -> left ) q . push ( temp -> left ) ; if ( temp -> right ) q . push ( temp -> right ) ; } if ( key_node != NULL ) { int x = temp -> key ; deletDeepest ( root , temp ) ; key_node -> key = x ; } return root ; }