Inorder traversal, but count the number of the nodes you visted, because the visiting order will just be increasing,so O(lgn) time to find the smallest node and O(1) space to store counter.

int k = 0; node* kthLastNodeBST(node *root) { if (root == NULL) return NULL; node *temp = kthLastNodeBST(root->left); if(temp) return temp; k--; if(kright); if(temp) return temp; return NULL; } k =3; node *temp = kthLastNodeBST(root);

Add an integer variable to the Tree Node - numNodesLeft to keep a count of number of nodes in the left subtree of current node. This is O(lg(n)) public KBSTNode kthSmallest(KBSTNode root, int k) { if(root==null || k=k) { return kthSmallest(root.left,k); } return kthSmallest(root.right,k-root.numNodesLeft-1); }

A brute force approach would be to put all the left children in an array and then look for kth element of this array.