BST Inorder Predecessor in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder predecessor of a node in BST

What is the output of the code when finding the inorder predecessor of node with value 15 in the given BST?

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function insert(root, val) {
  if (!root) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

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

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

A 5

B 20

C 10

D 15

💡 Hint

Remember, the inorder predecessor is the largest value smaller than the target node.

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

❓ Predict Output

intermediate

Output of inorder predecessor when node has left subtree

What will be printed when finding the inorder predecessor of node with value 30 in this BST?

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function insert(root, val) {
  if (!root) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function findMax(node) {
  while (node.right) {
    node = node.right;
  }
  return node.val;
}

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

const values = [20, 10, 30, 25, 35];
let root = null;
for (const v of values) {
  root = insert(root, v);
}
const node = { val: 30, left: new Node(25) };
console.log(inorderPredecessor(root, node));

A 20

B 25

C 10

D 35

💡 Hint

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

Since node 30 has a left child 25, the inorder predecessor is the maximum value in the left subtree, which is 25.

🔧 Debug

advanced

Identify the error in inorder predecessor function

What error will this code produce when trying to find the inorder predecessor of node with value 10?

DSA Javascript

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

const root = {
  val: 20,
  left: { val: 10, left: { val: 5, left: null, right: null }, right: { val: 15, left: null, right: null } },
  right: { val: 30, left: null, right: null }
};
const node = { val: 10 };
console.log(inorderPredecessor(root, node));

A 5

B 15

C null

D TypeError

💡 Hint

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

The inorder predecessor of 10 is 5, found as the rightmost node in the left subtree of 10.

🧠 Conceptual

advanced

Understanding inorder predecessor when no left subtree

If a node in a BST has no left child, how is its inorder predecessor found?

A The rightmost ancestor whose left child is also an ancestor of the node

B The leftmost ancestor whose left child is also an ancestor of the node

C The rightmost ancestor whose right child is also an ancestor of the node

D The leftmost ancestor whose right child is also an ancestor of the node

💡 Hint

Think about moving up the tree to find a smaller value than the node.

When no left subtree exists, the inorder predecessor is the closest ancestor for which the node lies in its right subtree, i.e., the leftmost ancestor whose right child is also an ancestor of the node.

🚀 Application

expert

Find inorder predecessor in BST with parent pointers

Given a BST node with parent pointers, which code snippet correctly finds its inorder predecessor?

A

function inorderPredecessor(node) {
  if (node.left) {
    let curr = node.left;
    while (curr.right) curr = curr.right;
    return curr;
  }
  let curr = node;
  while (curr.parent && curr === curr.parent.left) {
    curr = curr.parent;
  }
  return curr.parent;
}

B

function inorderPredecessor(node) {
  if (node.right) {
    let curr = node.right;
    while (curr.left) curr = curr.left;
    return curr;
  }
  let curr = node;
  while (curr.parent && curr === curr.parent.right) {
    curr = curr.parent;
  }
  return curr.parent;
}

C

function inorderPredecessor(node) {
  if (node.left) {
    let curr = node.left;
    while (curr.left) curr = curr.left;
    return curr;
  }
  let curr = node;
  while (curr.parent && curr === curr.parent.right) {
    curr = curr.parent;
  }
  return curr.parent;
}

D

function inorderPredecessor(node) {
  if (node.left) {
    let curr = node.left;
    while (curr.right) curr = curr.right;
    return curr;
  }
  let curr = node;
  while (curr.parent && curr === curr.parent.right) {
    curr = curr.parent;
  }
  return curr.parent;
}

💡 Hint

Remember the inorder predecessor is the max node in left subtree or the first ancestor where node is in right subtree.

Option A correctly finds the max node in left subtree if exists, else climbs up until node is a right child, then returns that parent.