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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Function Call

What is the output of the following C# code that finds the 3rd smallest element in the given BST?

DSA C#

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    private int count = 0;
    private int result = -1;

    public int KthSmallest(TreeNode root, int k) {
        InOrder(root, k);
        return result;
    }

    private void InOrder(TreeNode node, int k) {
        if (node == null) return;
        InOrder(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        InOrder(node.right, k);
    }
}

// BST structure:
//       5
//      / \
//     3   6
//    / \
//   2   4
//  /
// 1

TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.left.left.left = new TreeNode(1);

Solution sol = new Solution();
int output = sol.KthSmallest(root, 3);
System.Console.WriteLine(output);

A 4

B 2

C 3

D 5

💡 Hint

Remember that an inorder traversal of a BST visits nodes in ascending order.

The inorder traversal visits nodes in this order: 1, 2, 3, 4, 5, 6. The 3rd smallest element is 3.

🧠 Conceptual

intermediate

Understanding Inorder Traversal in BST

Why does an inorder traversal of a Binary Search Tree (BST) return nodes in ascending order?

A Because inorder traversal visits left subtree, then node, then right subtree, which respects BST ordering.

B Because inorder traversal visits nodes level by level from top to bottom.

C Because inorder traversal visits right subtree first, then node, then left subtree.

D Because inorder traversal visits nodes randomly but BST stores nodes sorted internally.

💡 Hint

Think about how BST property relates to left and right children values.

In a BST, left children are smaller and right children are larger. Inorder traversal visits left subtree first, then node, then right subtree, so nodes are visited in ascending order.

🔧 Debug

advanced

Identify the Bug in Kth Smallest Element Code

What error will the following code produce when trying to find the 2nd smallest element in the BST?

DSA C#

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    private int count = 0;
    private int result = -1;

    public int KthSmallest(TreeNode root, int k) {
        InOrder(root, k);
        return result;
    }

    private void InOrder(TreeNode node, int k) {
        if (node == null) return;
        InOrder(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
        }
        InOrder(node.right, k);
    }
}

// BST: 2 nodes only
TreeNode root = new TreeNode(1);
root.right = new TreeNode(2);

Solution sol = new Solution();
int output = sol.KthSmallest(root, 2);
System.Console.WriteLine(output);

A Prints 2 correctly

B Prints 2 but continues traversal unnecessarily

C Prints -1 because result is never updated

D Throws NullReferenceException

💡 Hint

Check if traversal stops after finding kth element.

The code sets result when count == k but does not stop traversal, so it continues visiting nodes unnecessarily. It still prints correct value 2.

❓ Predict Output

advanced

Output of Iterative Kth Smallest Element Code

What is the output of the following iterative C# code to find the 4th smallest element in the BST?

DSA C#

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        int count = 0;

        while (current != null || stack.Count > 0) {
            while (current != null) {
                stack.Push(current);
                current = current.left;
            }
            current = stack.Pop();
            count++;
            if (count == k) return current.val;
            current = current.right;
        }
        return -1;
    }
}

// BST:
//       7
//      / \
//     3   15
//        /  \
//       9    20

TreeNode root = new TreeNode(7);
root.left = new TreeNode(3);
root.right = new TreeNode(15);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(20);

Solution sol = new Solution();
int output = sol.KthSmallest(root, 4);
System.Console.WriteLine(output);

A 15

B 20

C 9

D 7

💡 Hint

Trace the inorder traversal order using the stack.

Inorder traversal order is 3, 7, 9, 15, 20. The 4th smallest element is 15.

🚀 Application

expert

Number of Nodes Visited to Find Kth Smallest

Given a balanced BST with 15 nodes, what is the minimum number of nodes visited during an inorder traversal to find the 7th smallest element using the recursive method that stops traversal after finding the kth element?

A 7

B 10

C 15

D 8

💡 Hint

Consider that inorder traversal visits nodes in ascending order and stops immediately after the kth node.

To find the 7th smallest element, the traversal visits nodes in ascending order until the 7th node. However, due to recursion and tree structure, it may visit one extra node before stopping. So minimum nodes visited is 8.

Practice

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

easy

A. The largest element in the Binary Search Tree

B. The height of the Binary Search Tree

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

D. The number of nodes in the Binary Search Tree

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Recognize BST property

   In a BST, an inorder traversal visits nodes in ascending order, so the Kth visited node is the Kth smallest.

3. Final Answer:

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

4. Quick Check:

   Kth smallest = Kth visited in inorder traversal [OK]

Hint: Inorder traversal gives sorted order; pick Kth node [OK]

Common Mistakes:

• Confusing Kth smallest with Kth largest
• Ignoring BST property and sorting separately
• Using preorder or postorder traversal instead of inorder

2. Which of the following C# method signatures correctly represents a function to find the Kth smallest element in a BST node class named TreeNode?

easy

A. public int KthSmallest(TreeNode root, int k)

B. public void KthSmallest(int root, int k)

C. public int KthSmallest(TreeNode root)

D. public int KthSmallest(int k)

Solution

1. Step 1: Identify correct parameter types

   The method needs the root node of type TreeNode and an integer k to find the Kth smallest element.

2. Step 2: Check return type and parameters

   The method returns an int (the value of the Kth smallest node) and takes TreeNode root and int k as parameters.

3. Final Answer:

   public int KthSmallest(TreeNode root, int k) -> Option A

4. Quick Check:

   Correct signature includes root node and k as parameters [OK]

Hint: Method needs root node and k as inputs, returns int [OK]

Common Mistakes:

• Using void return type instead of int
• Missing root node parameter
• Using wrong parameter types

3. Given the BST below and k = 3, what will the following C# code print?

class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int v) { val = v; }
}

// BST structure:
//       5
//      / \
//     3   7
//    / \   \
//   2   4   8

int KthSmallest(TreeNode root, int k) {
  List<int> vals = new List<int>();
  void Inorder(TreeNode node) {
    if (node == null) return;
    Inorder(node.left);
    vals.Add(node.val);
    Inorder(node.right);
  }
  Inorder(root);
  return vals[k - 1];
}

TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(7);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(8);

Console.WriteLine(KthSmallest(root, 3));

medium

A. 4

B. 3

C. 5

D. 7

Solution

1. Step 1: Perform inorder traversal of BST

   Inorder traversal visits nodes in ascending order: 2, 3, 4, 5, 7, 8.

2. Step 2: Find the 3rd element in the sorted list

   The 3rd element (index 2) is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Inorder sorted list = [2,3,4,5,7,8], 3rd element = 4 [OK]

Hint: Inorder traversal sorts BST; pick element at index k-1 [OK]

Common Mistakes:

• Using preorder or postorder traversal order
• Off-by-one error in indexing k-1
• Confusing left and right subtree values

4. The following code attempts to find the Kth smallest element in a BST but fails to stop the traversal early after finding the Kth element. What is the main issue?

int KthSmallest(TreeNode root, int k) {
  int count = 0;
  int result = -1;
  void Inorder(TreeNode node) {
    if (node == null) return;
    Inorder(node.left);
    count++;
    if (count == k) {
      result = node.val;
      return;
    }
    Inorder(node.right);
  }
  Inorder(root);
  return result;
}

medium

A. The function does not handle empty trees

B. The variable count is not incremented correctly

C. The result variable is not initialized

D. The return inside Inorder does not stop the entire traversal

Solution

1. Step 1: Analyze the recursive Inorder function

   The return statement inside Inorder only exits the current call, not the entire traversal, so traversal continues after finding the Kth element.

2. Step 2: Understand why this is problematic

   Continuing traversal after setting result wastes time and space; no mechanism to stop recursion early.

3. Final Answer:

   The return inside Inorder does not stop the entire traversal -> Option D

4. Quick Check:

   Return in recursion stops only current call, not whole traversal [OK]

Hint: Return in recursion stops only one call, not full traversal [OK]

Common Mistakes:

• Assuming return stops all recursion
• Not using a flag to stop traversal after finding element
• Ignoring null root case

5. You want to find the Kth smallest element in a BST but the tree is very large and you want to optimize for time and space. Which approach is best?

Options:
A) Use an iterative inorder traversal with a stack and stop when the Kth element is found.
B) Perform a full inorder traversal and store all elements in a list, then return the Kth element.
C) Convert the BST to a sorted array by any method, then binary search for the Kth element.
D) Use preorder traversal and count nodes until K is reached.

hard

A. Perform full inorder traversal and store all elements

B. Use iterative inorder traversal with stack, stop at Kth element

C. Convert BST to sorted array then binary search for Kth element

D. Use preorder traversal and count nodes until K is reached

Solution

1. Step 1: Evaluate full inorder traversal approach

   Storing all elements uses extra space and time, not efficient for large trees.

2. Step 2: Consider iterative inorder traversal with early stop

   This approach uses a stack to traverse nodes in order and stops immediately after finding the Kth smallest, saving time and space.

3. Step 3: Analyze other options

   Binary search requires sorted array, which needs full traversal first; preorder traversal does not guarantee sorted order.

4. Final Answer:

   Use iterative inorder traversal with stack, stop at Kth element -> Option B

5. Quick Check:

   Iterative inorder + early stop = efficient Kth smallest search [OK]

Hint: Iterative inorder with stack stops early, saves time and space [OK]

Common Mistakes:

• Using full traversal wasting memory
• Using preorder which is unsorted
• Trying binary search without sorted array