BST Inorder Successor in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder successor of a node with right subtree

Given the BST and the node with value 15, what is the value of its inorder successor?

DSA Typescript

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

// BST structure:
//       20
//      /  \
//    10    30
//      \     \
//      15    40

const root = new TreeNode(20);
root.left = new TreeNode(10);
root.right = new TreeNode(30);
root.left.right = new TreeNode(15);
root.right.right = new TreeNode(40);

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
  if (!root) return null;
  if (p.right) {
    let curr = p.right;
    while (curr.left) curr = curr.left;
    return curr;
  }
  let successor: TreeNode | null = null;
  let curr = root;
  while (curr) {
    if (p.val < curr.val) {
      successor = curr;
      curr = curr.left;
    } else if (p.val > curr.val) {
      curr = curr.right;
    } else {
      break;
    }
  }
  return successor;
}

const node = root.left.right; // Node with value 15
const successor = inorderSuccessor(root, node);
console.log(successor ? successor.val : null);

A 20

B 30

C 15

D null

💡 Hint

If the node has a right child, the successor is the leftmost node in the right subtree.

The node 15 has no right child, so we look up the tree for the lowest ancestor whose left child is also an ancestor of 15. That node is 20.

❓ Predict Output

intermediate

Inorder successor of a node without right subtree

What is the inorder successor of the node with value 10 in the given 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;
  }
}

// BST structure:
//       20
//      /  \
//    10    30
//      \     \
//      15    40

const root = new TreeNode(20);
root.left = new TreeNode(10);
root.right = new TreeNode(30);
root.left.right = new TreeNode(15);
root.right.right = new TreeNode(40);

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
  if (!root) return null;
  if (p.right) {
    let curr = p.right;
    while (curr.left) curr = curr.left;
    return curr;
  }
  let successor: TreeNode | null = null;
  let curr = root;
  while (curr) {
    if (p.val < curr.val) {
      successor = curr;
      curr = curr.left;
    } else if (p.val > curr.val) {
      curr = curr.right;
    } else {
      break;
    }
  }
  return successor;
}

const node = root.left; // Node with value 10
const successor = inorderSuccessor(root, node);
console.log(successor ? successor.val : null);

A 15

B 20

C 10

D null

💡 Hint

If the node has a right child, the successor is the leftmost node in the right subtree.

Node 10 has a right child 15, so the inorder successor is the leftmost node in the right subtree, which is 15.

🔧 Debug

advanced

Identify the error in inorder successor function

What error will this code produce when trying to find the inorder successor of node 30?

DSA Typescript

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

const root = new TreeNode(20);
root.left = new TreeNode(10);
root.right = new TreeNode(30);
root.left.right = new TreeNode(15);
root.right.right = new TreeNode(40);

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
  if (!root) return null;
  if (p.right) {
    let curr = p.right;
    while (curr.left) curr = curr.left;
    return curr;
  }
  let successor: TreeNode | null = null;
  let curr = root;
  while (curr) {
    if (p.val < curr.val) {
      successor = curr;
      curr = curr.left;
    } else if (p.val > curr.val) {
      curr = curr.right;
    } else {
      break;
    }
  }
  return successor;
}

const node = root.right; // Node with value 30
const successor = inorderSuccessor(root, node);
console.log(successor ? successor.val : null);

A SyntaxError

B null

C TypeError

D 40

💡 Hint

Check if the node has a right subtree and find the leftmost node there.

Node 30 has a right child 40, so the inorder successor is 40. No error occurs.

❓ Predict Output

advanced

Inorder successor of the maximum node in BST

What is the inorder successor of the node with value 40 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;
  }
}

// BST structure:
//       20
//      /  \
//    10    30
//      \     \
//      15    40

const root = new TreeNode(20);
root.left = new TreeNode(10);
root.right = new TreeNode(30);
root.left.right = new TreeNode(15);
root.right.right = new TreeNode(40);

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
  if (!root) return null;
  if (p.right) {
    let curr = p.right;
    while (curr.left) curr = curr.left;
    return curr;
  }
  let successor: TreeNode | null = null;
  let curr = root;
  while (curr) {
    if (p.val < curr.val) {
      successor = curr;
      curr = curr.left;
    } else if (p.val > curr.val) {
      curr = curr.right;
    } else {
      break;
    }
  }
  return successor;
}

const node = root.right.right; // Node with value 40
const successor = inorderSuccessor(root, node);
console.log(successor ? successor.val : null);

A 30

B 40

C null

D 20

💡 Hint

The maximum node in BST has no inorder successor.

Node 40 is the maximum node and has no right subtree, so no inorder successor exists.

🧠 Conceptual

expert

Inorder successor when node is root with no right subtree

In a BST, if the root node has no right subtree, what determines its inorder successor?

A The leftmost node in the left subtree

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

C The rightmost node in the left subtree

D There is no inorder successor

💡 Hint

Think about how inorder traversal visits nodes in ascending order.

If the node has no right subtree, the inorder successor is the lowest ancestor for which the node lies in its left subtree.