algorithm - How can i maintain state between recursion calls -

here question trying solve: find kth smallest integer in binary search tree:

my algorithm: inorder traversal of bst. each time visit node, decrement k 1 , when k=0, should in kth smallest node.

here implementation:

void findkthsmallest(struct treenode* root, int k) {   if (root == null) return;   if (k== 0) return;   findkthsmallest (root->left, k);   k--;   if (k == 0)   {     cout << root->data;     return;   }   findkthsmallest (root->right, k); } 

however above implementation, see state of k can't maintained between recursive calls.

i think state of k need maintained in 2 scenarios: recursive call returns between child , parent , recursive calls between parent child - struggling. there way maintain state in such scenario ?

in implementation, using variable k pass 2 different piece of information:

1. the remaining number of nodes before target node found.
2. if target node has been found.

what's missing 2. can achieve :

i) passing k reference instead of value.

ii) assign meaning of 2.) above value 0 of k.

the result like:

void findkthsmallest(struct treenode* root, int& k) {   if (root == null) return;   if (k == 0) return; // k==0 means target node has been found   findkthsmallest (root->left, k);    if (k > 0) // k==0 means target node has been found   {     k--;     if (k == 0) { // target node current node       cout << root->data;       return;     } else {       findkthsmallest (root->right, k);     }   } } 

also please note above implementation o(k). bst can achieve better performance looking k-th smallest integer.