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.

Practice

1. What is the inorder predecessor of a node in a Binary Search Tree (BST)?

easy

A. The right child of the given node

B. The node with the largest value smaller than the given node

C. The left child of the given node

D. The node with the smallest value larger than the given node

Solution

1. Step 1: Understand inorder traversal in BST

   Inorder traversal visits nodes in ascending order of their values.

2. Step 2: Define inorder predecessor

   The inorder predecessor of a node is the node visited just before it in inorder traversal, which means it has the largest value smaller than the given node.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option B

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is just before in sorted order [OK]

Common Mistakes:

• Confusing predecessor with successor
• Thinking predecessor is always left child
• Assuming predecessor is the parent node

2. Which TypeScript function signature correctly represents a method to find the inorder predecessor of a BST node?

easy

A. function findInorderPredecessor(root: TreeNode): void

B. function findInorderPredecessor(node: TreeNode): number

C. function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null

D. function findInorderPredecessor(): boolean

Solution

1. Step 1: Identify required inputs and outputs

   To find the inorder predecessor, we need the BST root and the target node, and we return the predecessor node or null if none.

2. Step 2: Match function signature

   function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null matches this: it takes root and node, returns TreeNode or null.

3. Final Answer:

   function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null -> Option C

4. Quick Check:

   Correct inputs and output type [OK]

Hint: Function needs root, node, returns node or null [OK]

Common Mistakes:

• Missing root parameter
• Returning wrong type like number or boolean
• No parameters or void return type

3. Given the BST below and the node with value 15, what is the inorder predecessor?

       20
      /  \
    10    30
      \
      15

medium

A. 10

B. 15

C. 20

D. 30

Solution

1. Step 1: Perform inorder traversal around node 15

   Inorder traversal visits nodes in order: 10, 15, 20, 30.

2. Step 2: Find node before 15 in traversal

   The node before 15 is 10, so 10 is the inorder predecessor.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Predecessor of 15 = 10 [OK]

Hint: Predecessor is previous in sorted order [OK]

Common Mistakes:

• Choosing the node itself as predecessor
• Choosing parent node incorrectly
• Confusing predecessor with successor

4. Consider this TypeScript code snippet to find the inorder predecessor of a node in a BST:

function inorderPredecessor(root: TreeNode | null, node: TreeNode): TreeNode | null {
  let predecessor: TreeNode | null = null;
  while (root) {
    if (node.val <= root.val) {
      root = root.left;
    } else {
      predecessor = root;
      root = root.right;
    }
  }
  return predecessor;
}

What is the bug in this code?

medium

A. It does not handle the case when node has a left subtree

B. It incorrectly updates predecessor when node.val > root.val

C. It returns the successor instead of predecessor

D. It causes infinite loop when root is null

Solution

1. Step 1: Understand inorder predecessor logic

   If node has a left subtree, predecessor is the rightmost node in that subtree, which this code does not check.

2. Step 2: Analyze code behavior

   The code only moves down from root to find predecessor by comparing values, missing the left subtree check for node.

3. Final Answer:

   It does not handle the case when node has a left subtree -> Option A

4. Quick Check:

   Left subtree check missing for predecessor [OK]

Hint: Check left subtree for predecessor first [OK]

Common Mistakes:

• Ignoring left subtree of node
• Assuming predecessor is always ancestor
• Confusing predecessor with successor logic

5. You want to find the inorder predecessor of a node with value 25 in this BST:

        40
       /  \
     20    60
    /  \  /  \
  10  30 50  70
       /
     25

Which steps correctly find the inorder predecessor of 25?

hard

A. Check left subtree of 25 (none), then move up to ancestors; predecessor is 50

B. Check left subtree of 25 (none), then move up to ancestors; predecessor is 30

C. Check left subtree of 25 (none), then move up to ancestors; predecessor is 10

D. Check left subtree of 25 (none), then move up to ancestors; predecessor is 20

Solution

1. Step 1: Check left subtree of node 25

   Node 25 has no left child, so no predecessor in left subtree.

2. Step 2: Move up to ancestors to find predecessor

   Ancestor nodes smaller than 25 are candidates; 20 is the closest smaller ancestor.

3. Final Answer:

   Check left subtree of 25 (none), then move up to ancestors; predecessor is 20 -> Option D

4. Quick Check:

   Predecessor found by ancestor smaller than node [OK]

Hint: If no left child, predecessor is nearest smaller ancestor [OK]

Common Mistakes:

• Choosing successor instead of predecessor
• Ignoring ancestors when left subtree is empty
• Picking wrong ancestor value