BST Inorder Predecessor in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the maximum node in the left subtree.

DSA Typescript

function findMaxNode(root: TreeNode | null): TreeNode | null {
  let current = root;
  while (current && current.[1]) {
    current = current.[1];
  }
  return current;
}

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

Aparent

Bleft

Cright

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'left' instead of 'right' will find the minimum, not maximum.

Accessing a non-existent property like 'parent' or 'next'.

To find the maximum node in a BST subtree, we keep moving to the right child until there is no right child.

2fill in blank

medium

Complete the code to move up the tree to find the inorder predecessor when left subtree is absent.

DSA Typescript

function inorderPredecessor(root: TreeNode | null, node: TreeNode): TreeNode | null {
  if (node.left) {
    return findMaxNode(node.[1]);
  }
  let predecessor = null;
  let current = root;
  while (current) {
    if (node.val > current.val) {
      predecessor = current;
      current = current.[2];
    } else if (node.val < current.val) {
      current = current.left;
    } else {
      break;
    }
  }
  return predecessor;
}

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' for the subtree.

Moving left when the value is greater instead of right.

If the node has a left subtree, the predecessor is the max node in that subtree (left child). Otherwise, move right in the tree while searching for a node smaller than the target.

3fill in blank

hard

Fix the error in the code that incorrectly updates the predecessor inside the loop.

DSA Typescript

while (current) {
  if (node.val > current.val) {
    predecessor = current;
    current = current.[1];
  } else {
    current = current.left;
  }
}

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

Aleft

Bnext

Cparent

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'left' instead of 'right' causes incorrect traversal.

Not updating predecessor correctly.

When node.val is greater than current.val, we move to the right child to find a closer predecessor.

4fill in blank

hard

Fill both blanks to complete the function that returns the inorder predecessor of a node in BST.

DSA Typescript

function inorderPredecessor(root: TreeNode | null, node: TreeNode): TreeNode | null {
  if (node.[1]) {
    return findMaxNode(node.[1]);
  }
  let predecessor = null;
  let current = root;
  while (current) {
    if (node.val > current.val) {
      predecessor = current;
      current = current.[2];
    } else {
      current = current.left;
    }
  }
  return predecessor;
}

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' for the subtree.

Moving left instead of right when node value is greater.

If the node has a left child, the predecessor is the max node in that left subtree. Otherwise, move right in the tree to find the closest smaller ancestor.

5fill in blank

hard

Fill all three blanks to complete the code that finds the inorder predecessor using BST properties.

DSA Typescript

function inorderPredecessor(root: TreeNode | null, node: TreeNode): TreeNode | null {
  if (node.[1]) {
    return findMaxNode(node.[1]);
  }
  let predecessor = null;
  let current = root;
  while (current) {
    if (node.val [2] current.val) {
      predecessor = current;
      current = current.[3];
    } else {
      current = current.left;
    }
  }
  return predecessor;
}

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

Aleft

B>

Cright

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the comparison.

Moving left instead of right when node value is greater.

If the node has a left child, find the max in that subtree. Otherwise, move right when node value is greater than current to find the predecessor.