Rekurencyjny spacer w kolejności z licznikiem
Time Complexity: O( N ), N is the number of nodes
Space Complexity: O( 1 ), excluding the function call stack
Pomysł jest podobny do rozwiązania @prasadvk, ale ma pewne wady (patrz uwagi poniżej), więc zamieszczam to jako osobną odpowiedź.
// Private Helper Macro
#define testAndReturn( k, counter, result ) \
do { if( (counter == k) && (result == -1) ) { \
result = pn->key_; \
return; \
} } while( 0 )
// Private Helper Function
static void findKthSmallest(
BstNode const * pn, int const k, int & counter, int & result ) {
if( ! pn ) return;
findKthSmallest( pn->left_, k, counter, result );
testAndReturn( k, counter, result );
counter += 1;
testAndReturn( k, counter, result );
findKthSmallest( pn->right_, k, counter, result );
testAndReturn( k, counter, result );
}
// Public API function
void findKthSmallest( Bst const * pt, int const k ) {
int counter = 0;
int result = -1; // -1 := not found
findKthSmallest( pt->root_, k, counter, result );
printf("%d-th element: element = %d\n", k, result );
}
Uwagi (i różnice w stosunku do rozwiązania @ prasadvk):
if( counter == k )
test jest wymagany w trzech miejscach: (a) za lewym poddrzewem, (b) za korzeniem i (c) po prawym poddrzewie. Ma to na celu zapewnienie, że k-ty element zostanie wykryty we wszystkich lokalizacjach , tj. Niezależnie od poddrzewa, w którym się znajduje.
if( result == -1 )
wymagany jest test, aby upewnić się, że drukowany jest tylko element wynikowy , w przeciwnym razie drukowane są wszystkie elementy, począwszy od k-tego najmniejszego do korzenia.