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.