BST Inorder Successor in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder successor of node 15 in this BST

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

BST structure:

       20
      /  \
    10    30
      \     \
      15    40

DSA Javascript

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

// BST creation
const root = new Node(20);
root.left = new Node(10);
root.right = new Node(30);
root.left.right = new Node(15);
root.right.right = new Node(40);

function inorderSuccessor(root, p) {
  let successor = null;
  while (root) {
    if (p.val < root.val) {
      successor = root;
      root = root.left;
    } else {
      root = root.right;
    }
  }
  return successor ? successor.val : null;
}

console.log(inorderSuccessor(root, root.left.right));

A 20

B 30

C 15

D null

💡 Hint

Inorder successor is the next bigger value in BST.

The inorder successor of 15 is 20 because 20 is the smallest node greater than 15.

❓ Predict Output

intermediate

Output of inorder successor for node 70 in BST

What is the output of the inorder successor function when called with node 70 in the BST below?

       25
      /  \
    15    50
   /  \     \
 10   22    70

DSA Javascript

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

const root = new Node(25);
root.left = new Node(15);
root.right = new Node(50);
root.left.left = new Node(10);
root.left.right = new Node(22);
root.right.right = new Node(70);

function inorderSuccessor(root, p) {
  let successor = null;
  while (root) {
    if (p.val < root.val) {
      successor = root;
      root = root.left;
    } else {
      root = root.right;
    }
  }
  return successor ? successor.val : null;
}

console.log(inorderSuccessor(root, root.right.right));

A 50

B null

C 70

D 25

💡 Hint

Check if node 70 has any bigger node in BST.

Node 70 is the largest node in the BST, so it has no inorder successor.

🔧 Debug

advanced

Identify the error in inorder successor code

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

DSA Javascript

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

// BST setup
const root = { val: 20, left: { val: 10, right: { val: 15 } }, right: { val: 30 } };
console.log(inorderSuccessor(root, root.left));

A 15

B ReferenceError: successor is not defined

C undefined

D TypeError: Cannot read property 'val' of null

💡 Hint

Check what happens if successor is null at return.

If successor remains null, accessing successor.val causes a TypeError.

🧠 Conceptual

advanced

Inorder successor when node has right subtree

In a BST, if a node has a right child, what is the inorder successor of that node?

A The leftmost node in the right subtree

B The parent node

C The right child itself

D The rightmost node in the left subtree

💡 Hint

Think about inorder traversal order.

The inorder successor is the smallest node greater than the current node, which is the leftmost node in its right subtree.

❓ Predict Output

expert

Output of inorder successor for node 22 in complex BST

What is the output of the inorder successor function for node 22 in this BST?

          50
         /  \
       30    70
      /  \   / \
    20   40 60  80
      
       22

DSA Javascript

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

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);
root.left.left.right = new Node(22);

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

console.log(inorderSuccessor(root, root.left.left.right));

A 50

B 40

C 30

D 22

💡 Hint

Check if node 22 has right child, else find closest ancestor.

Node 22 has no right child, so successor is the lowest ancestor whose left child is also ancestor of 22, which is 30.