1 void Traverse(Node* current, int* num) { 2 Traverse(current->left, num); 3 *num += 1; 4 if (*num == k) { 5 print current->data; 6 } 7 Traverse(current->right, num); 8 } 9 10 int n = 0; 11 Traverse(root, &n);

Two solutions along with code are demonstrated here: http://www.geeksforgeeks.org/archives/10379

public Integer kthSmallestNode(Node root, int k){ if(k list = new ArrayList(); doInOrderTraverse(this.root, k, list); if(list.size() >= k){ return list.get(k-1); } return null; } private void doInOrderTraverse(Node n, int max, ArrayList list){ if(n == null || list.size() >= max) return; doInOrderTraverse(n.left, max, list); if(list.isEmpty() || n.data != list.get(list.size() - 1)){ list.add(new Integer(n.data)); } doInOrderTraverse(n.right, max, list); }

Aren't the above algorithms O(lg (n) + k) runtime since it takes lg n time to get to the smallest element, then you build up the in order search until the size of the list is k?

I like Anonymous's solution. However, I think the recursive function can be made more efficient and complete as follows: void InorderWalk(Node *node, int& num, int k) { if (node != NULL) { InorderWalk(node->left, num, k); if (num right, num, k); } }

DFS. int find_kth_bst(bst_node* b, int cnt, int k) { if(b == NULL || cnt >= k) return cnt; int left = find_kth_bst(b->lft, cnt, k), right = 0; if(left+1 == k) { cout val rt, left+1, k); return right; }