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.