Do level order traversal until we find key and last node .
while ( ! q . isEmpty ( ) ) { temp = q . peek ( ) ; q . remove ( ) ; if ( temp . key == key ) keyNode = temp ; if ( temp . left != null ) q . add ( temp . left ) ; if ( temp . right != null ) q . add ( temp . right ) ; } if ( keyNode != null ) { int x = temp . key ; deleteDeepest ( root , temp ) ; keyNode . key = x ; } }