Skip to content

Latest commit

 

History

History
306 lines (240 loc) · 8.38 KB

12(Feb) k-th Smallest in BST.md

File metadata and controls

306 lines (240 loc) · 8.38 KB

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