BST Inorder Predecessor in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder predecessor of a node in BST

What is the output of the following TypeScript code that finds the inorder predecessor of a node with value 15 in the BST?

DSA Typescript

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

function insert(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

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

const values = [20, 10, 30, 5, 15, 25, 35];
let root: TreeNode | null = null;
for (const v of values) {
  root = insert(root, v);
}
const pred = inorderPredecessor(root, 15);
console.log(pred ? pred.val : null);

A 5

B 10

C 15

D null

💡 Hint

Remember, the inorder predecessor is the largest value smaller than the given key in BST.

The inorder predecessor of 15 is 10 because 10 is the largest node value less than 15 in the BST.

❓ Predict Output

intermediate

Inorder predecessor when node has left subtree

What will be printed by this TypeScript code that finds the inorder predecessor of node with value 30 in the BST?

DSA Typescript

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

function insert(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function findMax(node: TreeNode | null): TreeNode | null {
  while (node && node.right) {
    node = node.right;
  }
  return node;
}

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

const values = [20, 10, 30, 5, 15, 25, 35];
let root: TreeNode | null = null;
for (const v of values) {
  root = insert(root, v);
}
const pred = inorderPredecessor(root, 30);
console.log(pred ? pred.val : null);

A 15

B 20

C 25

D null

💡 Hint

If the node has a left subtree, the predecessor is the maximum node in that subtree.

Node 30 has a left child 25, which has no right child, so 25 is the inorder predecessor.

🔧 Debug

advanced

Identify the error in inorder predecessor function

What error will this TypeScript code produce when trying to find the inorder predecessor of 20?

DSA Typescript

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

function insert(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function inorderPredecessor(root: TreeNode | null, key: number): TreeNode | null {
  let predecessor: TreeNode | null = null;
  let current = root;
  while (current) {
    if (key < current.val) {
      current = current.left;
    } else if (key > current.val) {
      predecessor = current;
      current = current.right;
    } else {
      if (current.left) {
        let temp = current.left;
        while (temp.right) {
          temp = temp.right;
        }
        return temp;
      }
      break;
    }
  }
  return predecessor;
}

const values = [20, 10, 30, 5, 15, 25, 35];
let root: TreeNode | null = null;
for (const v of values) {
  root = insert(root, v);
}
const pred = inorderPredecessor(root, 20);
console.log(pred ? pred.val : null);

A Returns 5 instead of 15

B TypeError: Cannot read property 'left' of null

C Returns null always

D SyntaxError due to missing colon

💡 Hint

Check how the code finds the max node in the left subtree.

The code incorrectly finds the leftmost node in the left subtree instead of the rightmost, so it returns 5 instead of 15.

❓ Predict Output

advanced

Output of inorder predecessor when node is minimum

What will be the output of this TypeScript code when finding the inorder predecessor of the smallest node (5) in the BST?

DSA Typescript

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

function insert(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

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

const values = [20, 10, 30, 5, 15, 25, 35];
let root: TreeNode | null = null;
for (const v of values) {
  root = insert(root, v);
}
const pred = inorderPredecessor(root, 5);
console.log(pred ? pred.val : null);

A 20

B 5

C 10

D null

💡 Hint

The smallest node has no smaller node in BST.

Since 5 is the smallest node, it has no inorder predecessor, so the function returns null.

🧠 Conceptual

expert

Inorder predecessor concept in BST with duplicates

In a BST that allows duplicate values where duplicates are inserted to the right subtree, what is the inorder predecessor of a node with value 15 if the BST contains nodes with values [20, 10, 15, 15, 30]?

A The node with value 10 is the predecessor

B The first 15 inserted (left duplicate) is the predecessor

C The node with value 15 in the right subtree is the predecessor

D There is no predecessor because duplicates are on the right

💡 Hint

Inorder predecessor is the largest value smaller than the node's value.

Duplicates inserted to the right do not affect the predecessor. The largest value smaller than 15 is 10, so 10 is the inorder 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