In this Leetcode Kth Smallest Element in a BST problem solution you are given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

Leetcode Kth Smallest Element in a BST problem solution


Problem solution in Python.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder(node, arr):
            if node is None:
                return arr
            arr = inorder(node.left, arr)
            arr.append(node.val)
            arr = inorder(node.right, arr)
            return arr
        
        arr = inorder(root, [])
        return arr[k-1]



Problem solution in Java.

class Solution {
    int count;
    int res;
    
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        res = 0;
        helper(root);
        return res;
    }
    
    private void helper(TreeNode root) {
        if (root == null) return;
        helper(root.left);
        count--;
        if (count == 0) res = root.val;
        helper(root.right);
    }
}


Problem solution in C++.

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        // traverse in-order until k-th item is reached
        std::stack<TreeNode*> st;
        while (root || !st.empty())
        {
            while (root)
            {
                st.push(root);
                root = root->left;
            }
            root = st.top();
            if (--k == 0)
                return root->val;
            st.pop();
            root = root->right;
        }
        return -1;
    }
};


Problem solution in C.

int count;
int inorder(struct TreeNode* root);
int kthSmallest(struct TreeNode* root, int k){
    count=k;
    return inorder(root);
    //return 4;
}
int inorder(struct TreeNode* root){
    if(root==NULL){
        return 0;
    }
    int temp1=inorder(root->left);
    if(temp1!=0)
        return temp1;
    count-=1;
    if(count==0){
        return root->val;
    }
    int temp2=inorder(root->right);
    return temp2;
}