Kth Smallest Element in BST in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal for Kth Smallest

What is the output of the inorder traversal of this BST before finding the 3rd smallest element?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(7);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->left = new Node(6);
root->right->right = new Node(8);

void inorder(Node* node, vector<int>& res) {
    if (!node) return;
    inorder(node->left, res);
    res.push_back(node->val);
    inorder(node->right, res);
}

vector<int> result;
inorder(root, result);
for (int v : result) cout << v << " ";

A 2 3 4 5 6 7 8

B 8 7 6 5 4 3 2

C 5 3 2 4 7 6 8

D 3 2 4 5 7 6 8

💡 Hint

Inorder traversal of BST visits nodes in ascending order.

Inorder traversal visits left subtree, then node, then right subtree. For BST, this gives sorted order.

❓ Predict Output

intermediate

Output of Kth Smallest Element Function

What is the output of the function that finds the 4th smallest element in the BST below?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

int count = 0;
int kthSmallest = -1;

void inorderKth(Node* node, int k) {
    if (!node || count >= k) return;
    inorderKth(node->left, k);
    count++;
    if (count == k) {
        kthSmallest = node->val;
        return;
    }
    inorderKth(node->right, k);
}

Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(7);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->left = new Node(6);
root->right->right = new Node(8);

inorderKth(root, 4);
cout << kthSmallest;

A 3

B 5

C 6

D 4

💡 Hint

Count nodes visited in ascending order until reaching k.

The 4th smallest element in sorted order [2,3,4,5,6,7,8] is 5.

🔧 Debug

advanced

Identify the Bug in Kth Smallest Element Code

What error will this code produce when trying to find the 2nd smallest element?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

int count = 0;
int kthSmallest = -1;

void inorderKth(Node* node, int k) {
    if (!node) return;
    inorderKth(node->left, k);
    count++;
    if (count == k) {
        kthSmallest = node->val;
    }
    inorderKth(node->right, k);
}

Node* root = new Node(3);
root->left = new Node(1);
root->right = new Node(4);
root->left->right = new Node(2);

inorderKth(root, 2);
cout << kthSmallest;

A Runs infinitely

B Outputs 2 correctly

C Outputs -1 (default value)

D Outputs 3 instead of 2

💡 Hint

Check if traversal stops after finding kth element.

The code does not stop traversal after finding kth element, so kthSmallest gets overwritten by later nodes.

🧠 Conceptual

advanced

Time Complexity of Kth Smallest Element in BST

What is the average time complexity to find the kth smallest element in a balanced BST using inorder traversal?

A O(k)

B O(n)

C O(log n)

D O(k log n)

💡 Hint

Inorder traversal visits nodes in ascending order until kth is found.

We only need to visit k nodes in inorder traversal, so average time is O(k).

🚀 Application

expert

Result of Kth Smallest Element After Tree Modification

Given the BST below, after inserting a new node with value 1, what is the 3rd smallest element?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(7);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->left = new Node(6);
root->right->right = new Node(8);

// Insert new node with value 1
root->left->left->left = new Node(1);

int count = 0;
int kthSmallest = -1;

void inorderKth(Node* node, int k) {
    if (!node || count >= k) return;
    inorderKth(node->left, k);
    count++;
    if (count == k) {
        kthSmallest = node->val;
        return;
    }
    inorderKth(node->right, k);
}

inorderKth(root, 3);
cout << kthSmallest;

A 1

B 3

C 2

D 4

💡 Hint

Remember to include the new node in the sorted order.

After insertion, inorder traversal is [1,2,3,4,5,6,7,8]. The 3rd smallest is 2.

Practice

1. What does the Kth Smallest Element in BST problem ask you to find?

easy

A. The height of the Binary Search Tree

B. The element that is the Kth smallest value in the Binary Search Tree

C. The largest element in the Binary Search Tree

D. The sum of all elements in the Binary Search Tree

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the element that is the Kth smallest in the BST, meaning the element that would appear in position K if the BST elements were sorted.

2. Step 2: Clarify what Kth smallest means in BST context

   Since BST stores elements in sorted order when traversed in-order, the Kth smallest element is the Kth element visited in an in-order traversal.

3. Final Answer:

   The element that is the Kth smallest value in the Binary Search Tree -> Option B

4. Quick Check:

   Kth smallest element = Kth element in in-order traversal [OK]

Hint: Think in-order traversal gives sorted order [OK]

Common Mistakes:

• Confusing Kth smallest with Kth largest
• Thinking it's about tree height
• Summing elements instead of finding one

2. Which of the following C++ function signatures is correct for a function that finds the Kth smallest element in a BST node structure defined as struct TreeNode { int val; TreeNode* left; TreeNode* right; };?

easy

A. int kthSmallest(TreeNode* root, int k);

B. void kthSmallest(TreeNode root, int k);

C. int kthSmallest(TreeNode root, int* k);

D. int kthSmallest(TreeNode* root);

Solution

1. Step 1: Check parameter types for BST traversal

   The function should receive a pointer to the root node to traverse the BST properly, so TreeNode* root is correct.

2. Step 2: Check parameters for K value

   K is an integer input, so passing it as int k is correct. The function returns the Kth smallest value as an integer.

3. Final Answer:

   int kthSmallest(TreeNode* root, int k); -> Option A

4. Quick Check:

   Pointer to root + int k parameter = correct signature [OK]

Hint: Use pointer for tree root, int for K [OK]

Common Mistakes:

• Passing root by value instead of pointer
• Missing K parameter
• Wrong return type or missing return

3. Consider the following BST and code snippet. What will be the output?

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int count = 0;
int result = -1;

void inorder(TreeNode* root, int k) {
  if (!root) return;
  inorder(root->left, k);
  count++;
  if (count == k) {
    result = root->val;
    return;
  }
  inorder(root->right, k);
}

int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(1);
  root->right = new TreeNode(4);
  root->left->right = new TreeNode(2);
  inorder(root, 2);
  std::cout << result << std::endl;
  return 0;
}

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Perform in-order traversal on the BST

   The BST elements in in-order are visited as: 1, 2, 3, 4.

2. Step 2: Identify the 2nd element visited

   The 1st element visited is 1, the 2nd is 2, so result will be set to 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   In-order 2nd element = 2 [OK]

Hint: In-order traversal visits nodes in sorted order [OK]

Common Mistakes:

• Confusing pre-order or post-order traversal
• Off-by-one error in counting
• Not stopping traversal after finding Kth element

4. The following code attempts to find the Kth smallest element in a BST but does not work correctly. What is the main issue?

int count = 0;
int result = -1;

void inorder(TreeNode* root, int k) {
  if (!root) return;
  inorder(root->left, k);
  if (count == k) {
    result = root->val;
    return;
  }
  count++;
  inorder(root->right, k);
}

medium

A. The function uses global variables which is not allowed

B. The function does not handle null root correctly

C. The result variable is not updated inside the function

D. The check for count == k is before incrementing count, so it misses the Kth element

Solution

1. Step 1: Analyze the order of count checks and increments

   The code checks if count == k before incrementing count, so it skips setting result when count reaches k.

2. Step 2: Understand impact on finding Kth element

   Because count is checked before increment, the Kth element is never assigned to result, causing incorrect behavior.

3. Final Answer:

   The check for count == k is before incrementing count, so it misses the Kth element -> Option D

4. Quick Check:

   Check count after increment, not before [OK]

Hint: Increment count before checking if equals K [OK]

Common Mistakes:

• Checking count before incrementing
• Ignoring early return after finding Kth element
• Assuming global variables cause error

5. You want to find the Kth smallest element in a BST efficiently without using extra space for storing all elements. Which approach is best and why? A) Perform an in-order traversal and store all elements in a vector, then return the Kth element. B) Use a recursive in-order traversal with a counter to stop once the Kth element is found. C) Convert the BST to a sorted array using any traversal and then binary search for the Kth element. D) Use a breadth-first traversal and count nodes until K is reached.

hard

A. Store all elements then pick Kth; uses extra space

B. Convert to array then binary search; unnecessary overhead

C. Recursive in-order traversal with counter; stops early

D. Breadth-first traversal; does not guarantee sorted order

Solution

1. Step 1: Evaluate space and time efficiency of each approach

   Store all elements then pick Kth; uses extra space to store all elements, which is not efficient. Convert to array then binary search; unnecessary overhead also uses extra space and unnecessary binary search. Breadth-first traversal; does not guarantee sorted order, so it won't find the Kth smallest correctly.

2. Step 2: Identify the best approach

   Recursive in-order traversal with counter; stops early uses recursive in-order traversal which visits nodes in sorted order and stops once the Kth element is found, saving time and space.

3. Final Answer:

   Recursive in-order traversal with counter; stops early -> Option C

4. Quick Check:

   In-order traversal + early stop = efficient Kth smallest [OK]

Hint: Use in-order traversal with counter and stop early [OK]

Common Mistakes:

• Using extra space unnecessarily
• Using traversal that doesn't preserve order
• Not stopping traversal after finding Kth element