# C++ concise 3 approaches : Recursive, Iterative and Binary Search

• Recursive Solution:
Return INT_MAX if k > no of nodes in the subproblem.
'''

``````int kthSmallest(TreeNode* root, int k) {
int cntr = k;
return kthHelper(root,cntr);
}
int kthHelper(TreeNode * node, int &cntr){
if(node == NULL) return INT_MAX;
int t;
t = kthHelper(node->left, cntr);
if(t != INT_MAX) return t;
cntr--;
if(cntr == 0) return node->val;
t = kthHelper(node->right, cntr);
if(t != INT_MAX) return t;
return INT_MAX;
}
``````

'''

Iterative Solution:
Similar to iterative approach for in-order traversal, return INT_MAX if invalid k

'''

``````int kthSmallest(TreeNode* root, int k) {
stack<TreeNode *> nodeStack;
nodeStack.push(root);
TreeNode * node = root;
while(node->left){
node = node->left;
nodeStack.push(node);
}
int cntr = k;
while(! nodeStack.empty()){
node = nodeStack.top();
cntr--;
if(cntr == 0) return node->val;
nodeStack.pop();
if(node->right) {
node = node->right;
nodeStack.push(node);
while(node->left){
node = node->left;
nodeStack.push(node);
}
}
}
return INT_MAX;
}
``````

'''

Binary Search Solution

'''
private:

``````int countNodes(TreeNode * node){
if(node == NULL) return 0;
return 1 + countNodes(node->left) + countNodes(node->right);
}
``````

public:

``````int kthSmallest(TreeNode* root, int k) {
int no_left = countNodes(root->left);
if(no_left == k-1) return root->val;
else if(no_left > k-1) return kthSmallest(root->left, k);
else return kthSmallest(root->right, k-no_left-1);
}
``````

'''

• Maybe you can use a map to cache the counts in the "Binary Search Solution", otherwise it would recalculate subtrees.

• What's your time complexity of the binary search solution? What about using memorization?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.