Kth Smallest in a Binary Search Tree - Amazon Top Interview Questions

                        Solution in C++ :

int ans = 0;

void helper(Tree* root, int& k) {
    if (root) {
        helper(root->left, k);
        if (k == 0) ans = root->val;
        k--;
        helper(root->right, k);
    }
}

int solve(Tree* root, int k) {
    helper(root, k);
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    public int solve(Tree root, int k) {
        ArrayList<Integer> al = new ArrayList<>();
        helper(root, al);

        return al.get(k);
    }
    public void helper(Tree node, ArrayList<Integer> al) {
        if (node == null)
            return;
        helper(node.left, al);
        al.add(node.val);
        helper(node.right, al);
    }
}
                    

                        Solution in Python : 
                            
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


def inorder(self):
    if self.left:
        for node in inorder(self.left):
            yield node
    yield self
    if self.right:
        for node in inorder(self.right):
            yield node


setattr(Tree, "inorder", inorder)


class Solution:
    def solve(self, root, k):
        for node in root.inorder():
            if k == 0:
                return node.val
            k -= 1