🚀Day 11. 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.

🔍 Example Walkthrough:

Example 1:

Input:

Output:

Explanation:

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

Example 2:

Input:

Output:

-1

Explanation:

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

Example 3:

Input:

Output:

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:

Start from the root node.
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.
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.
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.

📝 Solution Code

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

PreviousDay 10. Check for BST 🧠NextDay 12. Pair Sum in BST 🧠

Last updated 6 months ago

hashtag💡 Problem Description:

hashtag🔍 Example Walkthrough:

hashtagExample 1:

hashtagInput:

hashtagOutput:

hashtagExplanation:

hashtagExample 2:

hashtagInput:

hashtagOutput:

hashtagExplanation:

hashtagExample 3:

hashtagInput:

hashtagOutput:

hashtagExplanation:

hashtagConstraints:

hashtag🎯 My Approach:

hashtagMorris Inorder Traversal (O(1) Space)

hashtagAlgorithm Steps:

hashtag🕒 Time and Auxiliary Space Complexity

hashtag📝 Solution Code

hashtagCode (C)

hashtagCode (C++)

hashtag2️⃣ Recursive Inorder Traversal

hashtag3️⃣ Iterative Inorder Traversal (Using Stack)

hashtagComparison of Approaches

hashtag💡 Best Choice?

hashtagCode (Java)

hashtagCode (Python)

hashtag🎯 Contribution and Support:

hashtag📍Visitor Count

💡 Problem Description:

🔍 Example Walkthrough:

Example 1:

Input:

Output:

Explanation:

Example 2:

Input:

Output:

Explanation:

Example 3:

Input:

Output:

Explanation:

Constraints:

🎯 My Approach:

Morris Inorder Traversal (O(1) Space)

Algorithm Steps:

🕒 Time and Auxiliary Space Complexity

📝 Solution Code

Code (C)

Code (C++)

2️⃣ Recursive Inorder Traversal

3️⃣ Iterative Inorder Traversal (Using Stack)

Comparison of Approaches

💡 Best Choice?

Code (Java)

Code (Python)

🎯 Contribution and Support:

📍Visitor Count