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.

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 BST property

   A Binary Search Tree (BST) stores values so that left child nodes are smaller and right child nodes are larger than the parent.

2. Step 2: Define the Kth smallest element

   The Kth smallest element is the element that would appear in position K if all elements were sorted in ascending order.

3. Final Answer:

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

4. Quick Check:

   Kth smallest means sorted order position K [OK]

Hint: Remember BST in-order traversal gives sorted order [OK]

Common Mistakes:

• Confusing Kth smallest with largest element
• Thinking it means tree height
• Counting nodes instead of values

2. Which TypeScript function signature correctly represents a function to find the Kth smallest element in a BST node structure?

easy

A. function kthSmallest(k: number, root: TreeNode): void

B. function kthSmallest(root: TreeNode | null, k: number): number

C. function kthSmallest(root: TreeNode, k: string): string

D. function kthSmallest(root: TreeNode, k: number): TreeNode

Solution

1. Step 1: Check parameter types and order

   The function should take the root node (which can be null) and a number k representing the position.

2. Step 2: Check return type

   The function returns the value (number) of the Kth smallest element, not a node or void.

3. Final Answer:

   function kthSmallest(root: TreeNode | null, k: number): number -> Option B

4. Quick Check:

   Correct parameter types and return number [OK]

Hint: Root node first, k as number, return value number [OK]

Common Mistakes:

• Swapping parameter order
• Using wrong return type
• Using string instead of number for k

3. Given the BST below and k = 3, what is the output of the function kthSmallest(root, 3)?

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

medium

A. 3

B. 5

C. 4

D. 7

Solution

1. Step 1: Perform in-order traversal

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

2. Step 2: Identify the 3rd element

   The 3rd element in this order is 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   In-order 3rd element = 4 [OK]

Hint: In-order traversal gives sorted nodes; pick Kth [OK]

Common Mistakes:

• Counting root as first without traversal
• Confusing left and right subtree order
• Picking value by node depth

4. Consider this TypeScript code snippet to find the Kth smallest element in a BST:

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);
    count++;
    if (count === k) {
      result = node.val;
      return;
    }
    inorder(node.right);
  }
  inorder(root);
  return result;
}

What is the main problem with this code?

medium

A. The function does not stop traversal after finding the Kth element

B. The count variable is not incremented correctly

C. The result variable is initialized incorrectly

D. The function does not handle null root

Solution

1. Step 1: Analyze traversal stopping condition

   The code sets result when count equals k but does not stop further recursion, so it continues traversing unnecessarily.

2. Step 2: Understand impact of not stopping traversal

   Without stopping, the function wastes time and may overwrite result if not careful.

3. Final Answer:

   The function does not stop traversal after finding the Kth element -> Option A

4. Quick Check:

   Traversal must stop after Kth element found [OK]

Hint: Stop recursion immediately after finding Kth element [OK]

Common Mistakes:

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

5. You want to find the Kth smallest element in a BST but the tree is very large and you need to optimize for multiple queries with different K values. Which approach is best?

hard

A. Perform in-order traversal each time for every K query

B. Use breadth-first search to find the Kth smallest element

C. Randomly pick nodes until Kth smallest is found

D. Store the in-order traversal result in an array once, then answer queries by indexing

Solution

1. Step 1: Consider repeated queries

   Performing in-order traversal each time is costly for large trees and many queries.

2. Step 2: Use pre-processing for efficiency

   Storing the sorted elements from one in-order traversal allows O(1) access for each Kth smallest query.

3. Step 3: Evaluate other options

   Breadth-first search does not give sorted order; random picking is inefficient and unreliable.

4. Final Answer:

   Store the in-order traversal result in an array once, then answer queries by indexing -> Option D

5. Quick Check:

   Precompute once, query fast [OK]

Hint: Precompute sorted list once for fast multiple queries [OK]

Common Mistakes:

• Recomputing traversal for each query
• Using BFS which is unsorted
• Random selection guessing