Kth Smallest Element in BST in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform an inorder traversal on the BST.

DSA Javascript

function inorder(node, result) {
  if (node === null) return;
  inorder(node.left, result);
  result.push([1]);
  inorder(node.right, result);
}

Drag options to blanks, or click blank then click option'

Anode.val

Bnode.key

Cnode.data

Dnode.value

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.key or node.data which may not exist in this BST node structure.

Pushing node instead of node.value.

In a BST node, the value is typically stored in 'value'. We push node.value to the result during inorder traversal.

2fill in blank

medium

Complete the code to return the kth smallest element after inorder traversal.

DSA Javascript

function kthSmallest(root, k) {
  const result = [];
  inorder(root, result);
  return result[[1]];
}

Drag options to blanks, or click blank then click option'

Ak + 1

Bk

Ck - 1

Dk * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using k directly as index causing off-by-one errors.

Using k + 1 or k * 2 which are incorrect indices.

Array indices start at 0, so the kth smallest element is at index k - 1.

3fill in blank

hard

Fix the error in the recursive inorder traversal to avoid infinite recursion.

DSA Javascript

function inorder(node, result) {
  if (node === [1]) return;
  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);
}

Drag options to blanks, or click blank then click option'

Anull

Bundefined

Cfalse

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for undefined instead of null.

Using false or 0 which are not valid node values.

The base case for recursion in a BST traversal is when the node is null.

4fill in blank

hard

Fill both blanks to implement an iterative inorder traversal using a stack.

DSA Javascript

function kthSmallestIterative(root, k) {
  const stack = [];
  let current = root;
  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.[1];
    }
    current = stack.pop();
    k--;
    if (k === 0) return current.value;
    current = current.[2];
  }
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'right' instead of 'left' in the inner while loop.

Using 'parent' or 'next' which are not standard BST node properties.

In inorder traversal, we go left as far as possible, then visit node, then go right.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps nodes to their depths during traversal.

DSA Javascript

function mapDepths(root) {
  const depths = {};
  function dfs(node, depth) {
    if (node === null) return;
    depths[[1]] = depth;
    dfs(node.[2], depth + 1);
    dfs(node.[3], depth + 1);
  }
  dfs(root, 0);
  return depths;
}

Drag options to blanks, or click blank then click option'

Anode.value

Bleft

Cright

Dnode.key

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.key which may not exist.

Mixing up left and right child properties.

We use node.value as key, and recurse on left and right children.