Kth Smallest Element in BST in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Function Call

What is the output of the following JavaScript code that finds the 3rd smallest element in a BST?

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function kthSmallest(root, k) {
  let count = 0;
  let result = null;

  function inorder(node) {
    if (!node || result !== null) return;
    inorder(node.left);
    count++;
    if (count === k) {
      result = node.val;
      return;
    }
    inorder(node.right);
  }

  inorder(root);
  return result;
}

const root = new TreeNode(5,
  new TreeNode(3,
    new TreeNode(2,
      new TreeNode(1), null),
    new TreeNode(4)),
  new TreeNode(6)
);

console.log(kthSmallest(root, 3));

A 2

B 4

C 3

D 5

💡 Hint

Remember that inorder traversal of BST gives sorted order.

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

🧠 Conceptual

intermediate

Understanding Inorder Traversal in BST

Why does inorder traversal help find the kth smallest element in a BST?

A Because inorder traversal visits only leaf nodes.

B Because inorder traversal visits nodes in descending order of their values.

C Because inorder traversal visits nodes randomly.

D Because inorder traversal visits nodes in ascending order of their values.

💡 Hint

Think about the BST property and how inorder traversal works.

In BST, left child < parent < right child. Inorder traversal visits left subtree, then node, then right subtree, producing sorted order.

🔧 Debug

advanced

Identify the Error in Kth Smallest Implementation

What error will occur when running this code to find the kth smallest element?

DSA Javascript

function kthSmallest(root, k) {
  let count = 0;
  let result = null;

  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    if (count === k) {
      result = node.val;
      return;
    }
    count++;
    inorder(node.right);
  }

  inorder(root);
  return result;
}

A It returns null for any k because count is incremented after checking equality.

B It throws a ReferenceError because result is not defined.

C It returns the correct kth smallest element.

D It causes infinite recursion.

💡 Hint

Check the order of count increment and comparison with k.

The count is checked before incrementing, so count never reaches k at the right time, causing result to remain null.

❓ Predict Output

advanced

Output of Kth Smallest with Duplicate Values

What is the output of the code below when finding the 4th smallest element in a BST with duplicates?

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function kthSmallest(root, k) {
  let count = 0;
  let result = null;

  function inorder(node) {
    if (!node || result !== null) return;
    inorder(node.left);
    count++;
    if (count === k) {
      result = node.val;
      return;
    }
    inorder(node.right);
  }

  inorder(root);
  return result;
}

const root = new TreeNode(5,
  new TreeNode(3,
    new TreeNode(3,
      new TreeNode(2), null),
    new TreeNode(4)),
  new TreeNode(6)
);

console.log(kthSmallest(root, 4));

A 4

B 5

C 3

D 2

💡 Hint

Duplicates appear in sorted order during inorder traversal.

Inorder traversal order: 2, 3, 3, 4, 5, 6. The 4th smallest is 4.

🚀 Application

expert

Optimizing Kth Smallest Element Search

Which data structure modification allows finding the kth smallest element in a BST in O(log n) time on average?

A Use a stack to perform iterative inorder traversal each time.

B Augment each node with the count of nodes in its left subtree.

C Store all elements in an array and sort it every time.

D Convert the BST into a linked list.

💡 Hint

Think about how to quickly skip nodes during traversal.

By storing the size of left subtree at each node, we can decide whether to go left, right, or return current node quickly.

Practice

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

easy

A. The element that is the Kth smallest value in the binary search tree

B. The largest element in the binary search tree

C. The height of 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 element which is the Kth smallest in the BST, meaning if you list all elements in ascending order, pick the one at position K.

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

   Since BST stores smaller values on the left and larger on the right, an inorder traversal gives sorted order. The Kth element in this order is the answer.

3. Final Answer:

   The element that is the Kth smallest value in the binary search tree -> Option A

4. Quick Check:

   Kth smallest = element at position K in sorted BST [OK]

Hint: Inorder traversal of BST gives sorted order [OK]

Common Mistakes:

• Confusing Kth smallest with Kth largest
• Thinking it's about tree height
• Counting nodes instead of values

2. Which of the following is the correct way to start an inorder traversal function in JavaScript for a BST node named root?

easy

A. function inorder(root) { while(root) { inorder(root.left); } }

B. function inorder(root) { if (root == null) return root.left; }

C. function inorder(root) { if (!root) return; inorder(root.left); ... }

D. function inorder(root) { root = root.left; inorder(root); }

Solution

1. Step 1: Check base case for recursion

   function inorder(root) { if (!root) return; inorder(root.left); ... } correctly checks if root is null and returns to stop recursion.

2. Step 2: Verify recursive call order

   function inorder(root) { if (!root) return; inorder(root.left); ... } calls inorder(root.left) before processing current node, which is correct for inorder traversal.

3. Final Answer:

   function inorder(root) { if (!root) return; inorder(root.left); ... } -> Option C

4. Quick Check:

   Base case + left recursion = correct inorder start [OK]

Hint: Use base case if null, then recurse left [OK]

Common Mistakes:

• Using while loop instead of recursion
• Returning wrong subtree
• Not checking for null before recursion

3. What will be the output of the following code snippet to find the 3rd smallest element in the BST?

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const 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);

let count = 0;
let result = null;
function kthSmallest(node, k) {
  if (!node) return;
  kthSmallest(node.left, k);
  count++;
  if (count === k) {
    result = node.val;
    return;
  }
  kthSmallest(node.right, k);
}
kthSmallest(root, 3);
console.log(result);

medium

A. 4

B. 3

C. 5

D. 2

Solution

1. Step 1: Perform inorder traversal and count nodes

   The inorder traversal visits nodes in order: 2, 3, 4, 5, 7. Counting visits: 1=2, 2=3, 3=4.

2. Step 2: Identify the 3rd visited node

   The 3rd node visited is 4, so result is set to 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Inorder order: 2,3,4... 3rd is 4 [OK]

Hint: Inorder traversal order gives sorted nodes [OK]

Common Mistakes:

• Counting before left subtree traversal
• Not stopping after finding kth element
• Confusing node values with count

4. The following code is intended to find the Kth smallest element in a BST, but it has a bug. What is the bug?

function kthSmallest(root, k) {
  let count = 0;
  let result = null;
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    count++;
    if (count === k) return node.val;
    inorder(node.right);
  }
  result = inorder(root);
  return result;
}

medium

A. The base case is missing

B. The recursive calls do not return the found value properly

C. The count variable is not incremented

D. The function does not traverse the right subtree

Solution

1. Step 1: Analyze return values in recursion

   The function returns node.val when count matches k, but does not propagate this value back up the recursive calls.

2. Step 2: Identify missing return propagation

   Without returning the found value from left or right recursive calls, the final result will be undefined.

3. Final Answer:

   The recursive calls do not return the found value properly -> Option B

4. Quick Check:

   Return values must propagate up recursion [OK]

Hint: Return found value from all recursive calls [OK]

Common Mistakes:

• Ignoring return values in recursion
• Not incrementing count correctly
• Missing base case check

5. Given a BST with nodes inserted in this order: [6, 2, 8, 0, 4, 7, 9, 3, 5], what is the 5th smallest element?

hard

A. 7

B. 6

C. 4

D. 5

Solution

1. Step 1: Construct BST and list inorder traversal

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

2. Step 2: Identify the 5th element in sorted order

   The 5th element is 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Sorted nodes: 0,2,3,4,5... 5th is 5 [OK]

Hint: Inorder traversal order = sorted nodes [OK]

Common Mistakes:

• Counting nodes incorrectly
• Confusing insertion order with sorted order
• Off-by-one errors in counting