12. k-th Smallest in BST

The problem can be found at the following link: Question Link

Problem Description

Given a Binary Search Tree (BST) and an integer k, the task is to find the k-th smallest element in the BST. If there is no k-th smallest element present, return -1.

Examples

Example 1:

Input:

        2
       / \
      1   3
k = 2

Output:

2

Explanation:

The elements in ascending order are [1, 2, 3]. The 2nd smallest element is 2.

Example 2:

Input:

        2
       / \
      1   3
k = 5

Output:

-1

Explanation:

The BST contains only 3 elements. Hence, there is no 5th smallest element.

Example 3:

Input:

            20
           /  \
          8    22
         / \
        4   12
           /  \
         10   14
k = 3

Output:

10

Explanation:

The in-order traversal of the BST is [4, 8, 10, 12, 14, 20, 22]. The 3rd smallest element is 10.

Constraints:

• 1 ≤ number of nodes, k ≤ $10^5$

• 1 ≤ node->data ≤ $10^5$

My Approach

Morris Inorder Traversal (O(1) Space)

• Morris Traversal allows in-order traversal without using a stack or recursion, thus achieving O(1) space complexity.

• It temporarily modifies the tree structure but restores it before completion.

Algorithm Steps:

1. Start from the root node.

2. If the left child is NULL:

   • Visit the current node (decrement k).

   • If k == 0, return the current node's value.

   • Move to the right child.

3. If the left child exists:

   • Find the rightmost node in the left subtree (inorder predecessor).

   • If the rightmost node's right is NULL:

     • Make the current node its right child (create a temporary thread).

     • Move to the left child.

   • If the rightmost node’s right is the current node (thread exists):

     • Remove the thread (restore the original tree).

     • Visit the current node (decrement k).

     • If k == 0, return the current node's value.

     • Move to the right child.

4. If the traversal completes without finding the k-th smallest, return -1.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N) We visit each node exactly twice (once to create a thread and once to remove it), which is linear with respect to the number of nodes.

• Expected Auxiliary Space Complexity: O(1) No additional stack or recursion is used. Only a few pointers are manipulated.

Code (C)

int kthSmallest(struct Node* root, int k) {
    while (root) {
        if (!root->left) {
            if (--k == 0) return root->data;
            root = root->right;
        } else {
            struct Node *pre = root->left;
            while (pre->right && pre->right != root) pre = pre->right;
            if (!pre->right) {
                pre->right = root;
                root = root->left;
            } else {
                pre->right = NULL;
                if (--k == 0) return root->data;
                root = root->right;
            }
        }
    }
    return -1;
}

Code (C++)

class Solution {
  public:
    int kthSmallest(Node* root, int k) {
        while (root) {
            if (!root->left) {
                if (--k == 0) return root->data;
                root = root->right;
            } else {
                Node* pre = root->left;
                while (pre->right && pre->right != root) pre = pre->right;
                if (!pre->right) {
                    pre->right = root;
                    root = root->left;
                } else {
                    pre->right = NULL;
                    if (--k == 0) return root->data;
                    root = root->right;
                }
            }
        }
        return -1;
    }
};

🌲 Alternative Approaches

2️⃣ Recursive Inorder Traversal

class Solution {
public:
    int kthSmallest(Node* root, int &k) {
        if (!root) return -1;
        int left = kthSmallest(root->left, k);
        if (k == 0) return left;
        if (--k == 0) return root->data;
        return kthSmallest(root->right, k);
    }
};

🔹 Optimized by using k as a reference, reducing redundant calculations.

3️⃣ Iterative Inorder Traversal (Using Stack)

class Solution {
public:
    int kthSmallest(Node* root, int k) {
        if (!root) return -1;
        stack<Node*> st;
        while (true) {
            while (root) {
                st.push(root);
                root = root->left;
            }
            if (st.empty()) return -1;
            root = st.top(); st.pop();
            if (--k == 0) return root->data;
            root = root->right;
        }
    }
};

🔹 Handles larger trees efficiently without recursion depth issues.

Comparison of Approaches

Approaches	⏱️ Time Complexity	🗂️ Space Complexity	⚡ Method	✅ Pros	⚠️ Cons
Morris Traversal (Optimized)	🟢 O(N)	🟢 O(1)	No extra space	No extra space used	Modifies tree temporarily
Recursive Inorder	🟢 O(N)	🟡 O(H)	Recursion	Simple and concise	Stack space for recursion
Iterative Inorder (Stack)	🟢 O(H + K)	🟡 O(H)	Stack-based	Avoids recursion depth issues	Uses extra memory for stack

💡 Best Choice?

• For space efficiency: ✅ Morris Traversal (O(1) space).

• For simplicity: ✅ Recursive Inorder Traversal is intuitive.

• For large/deep trees: ✅ Iterative Inorder Traversal (Stack) avoids recursion depth issues.

Code (Java)

class Solution {
    public int kthSmallest(Node root, int k) {
        while (root != null) {
            if (root.left == null) {
                if (--k == 0) return root.data;
                root = root.right;
            } else {
                Node pre = root.left;
                while (pre.right != null && pre.right != root) pre = pre.right;
                if (pre.right == null) {
                    pre.right = root;
                    root = root.left;
                } else {
                    pre.right = null;
                    if (--k == 0) return root.data;
                    root = root.right;
                }
            }
        }
        return -1;
    }
}

Code (Python)

class Solution:
    def kthSmallest(self, root, k):
        while root:
            if not root.left:
                k -= 1
                if k == 0:
                    return root.data
                root = root.right
            else:
                pre = root.left
                while pre.right and pre.right != root:
                    pre = pre.right
                if not pre.right:
                    pre.right = root
                    root = root.left
                else:
                    pre.right = None
                    k -= 1
                    if k == 0:
                        return root.data
                    root = root.right
        return -1

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count