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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Function

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

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val===undefined ? 0 : val);
    this.left = (left===undefined ? null : left);
    this.right = (right===undefined ? null : right);
  }
}

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let result = -1;

  function inorder(node: TreeNode | null) {
    if (!node || result !== -1) 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 3

B 2

C 4

D 5

💡 Hint

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

The inorder traversal visits nodes in sorted 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 nodes in ascending order of their values.

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

C Because inorder traversal visits nodes randomly.

D Because inorder traversal visits only leaf nodes.

💡 Hint

Think about how BST stores smaller values on the left and larger on the right.

In BST, left subtree has smaller values, right subtree has larger values. Inorder visits left, root, right, so it visits nodes 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 1st smallest element?

DSA Typescript

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let result = -1;

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

  inorder(root);
  return result;
}

A Infinite recursion

B Throws a runtime error

C Returns -1 (incorrect result)

D Returns the correct kth smallest element

💡 Hint

Check when count is incremented and when result is assigned.

The count is incremented after checking if count === k, so the condition is never true at the right time. Result stays -1.

❓ Predict Output

advanced

Output of Kth Smallest Element with Duplicate Values

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

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val===undefined ? 0 : val);
    this.left = (left===undefined ? null : left);
    this.right = (right===undefined ? null : right);
  }
}

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

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

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let result = -1;

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

  inorder(root);
  return result;
}

A 2

B 4

C 3

D 1

💡 Hint

Count nodes in inorder: 1, 2, 3, 4, 4

Inorder traversal visits nodes in order: 1, 2, 3, 4, 4. The 4th smallest is the first 4.

🚀 Application

expert

Optimizing Kth Smallest Element Search with Node Counts

Given a BST where each node stores the count of nodes in its left subtree, how can you find the kth smallest element efficiently?

A Perform a breadth-first search and count nodes until k is reached.

B Always traverse the entire tree inorder and count nodes until k is reached.

C Use a stack to store all nodes and pop k times to get kth smallest.

D Compare k with left subtree count + 1 to decide to go left, right, or return current node.

💡 Hint

Use the stored counts to skip entire subtrees.

If k equals left subtree count + 1, current node is kth smallest. If k is smaller, go left. If larger, go right adjusting k accordingly.