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.

Practice

1. What is the inorder successor of a node in a Binary Search Tree (BST)?

easy

A. The node with the smallest key greater than the given node's key

B. The node with the largest key smaller than the given node's key

C. The root node of the BST

D. The left child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order of their keys in a BST.

2. Step 2: Define inorder successor

   The inorder successor of a node is the next node visited after it in inorder traversal, which is the smallest key greater than the node's key.

3. Final Answer:

   The node with the smallest key greater than the given node's key -> Option A

4. Quick Check:

   Inorder successor = next bigger key [OK]

Hint: Inorder successor is next bigger node in sorted order [OK]

Common Mistakes:

• Confusing successor with predecessor
• Thinking successor is always the right child
• Assuming successor is the root node

2. Which of the following is the correct JavaScript function signature to find the inorder successor of a node in a BST?

easy

A. function inorderSuccessor(node) {}

B. function inorderSuccessor(root, node) {}

C. function findSuccessor(root) {}

D. function successor(node, root) {}

Solution

1. Step 1: Identify required inputs

   To find the inorder successor, we need the BST root to traverse and the target node to find its successor.

2. Step 2: Match function signature

   function inorderSuccessor(root, node) {} correctly takes both root and node as parameters, enabling traversal and comparison.

3. Final Answer:

   function inorderSuccessor(root, node) {} -> Option B

4. Quick Check:

   Function needs root and node [OK]

Hint: Successor function needs both root and target node [OK]

Common Mistakes:

• Using only node without root
• Wrong parameter order
• Incorrect function naming

3. Given the BST below and the node with value 15, what is the inorder successor?

      20
     /  \
   10    30
     
     15

medium

A. 10

B. 30

C. 20

D. 15

Solution

1. Step 1: Locate node 15 and its right subtree

   Node 15 has no right child, so successor is an ancestor.

2. Step 2: Find the lowest ancestor whose left child is also ancestor of 15

   Node 20 is the first ancestor where 15 is in left subtree, so successor is 20.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Successor of 15 is 20 [OK]

Hint: If no right child, go up to first bigger ancestor [OK]

Common Mistakes:

• Choosing right child when none exists
• Picking the node itself as successor
• Confusing successor with predecessor

4. Consider this buggy JavaScript code to find the inorder successor of a node in a BST:

function inorderSuccessor(root, node) {
  if (!root) return null;
  if (node.val >= root.val) {
    return inorderSuccessor(root.right, node);
  } else {
    let left = inorderSuccessor(root.left, node);
    return left ? left : root;
  }
}

What is the main issue with this code?

medium

A. It does not handle the case when node has a right subtree

B. It incorrectly compares node.val with root.val

C. It returns the node itself instead of successor

D. It causes infinite recursion

Solution

1. Step 1: Analyze code logic

   The code only traverses the tree comparing values but never checks if node has a right subtree.

2. Step 2: Identify missing right subtree check

   If node has a right child, successor is the leftmost node in right subtree, which this code ignores.

3. Final Answer:

   It does not handle the case when node has a right subtree -> Option A

4. Quick Check:

   Missing right subtree check causes wrong successor [OK]

Hint: Check right subtree first for successor [OK]

Common Mistakes:

• Ignoring right subtree
• Wrong base case
• Returning node instead of successor

5. You have a BST and want to find the inorder successor of node 25. The BST structure is:

        20
       /  \
     10    30
           /  \
         25    40

What is the inorder successor of node 25 and why?

hard

A. 40, because 40 is the right child of 30

B. 20, because it is the root

C. None, because 25 is the largest node in its subtree

D. 30, because 25 has no right child and 30 is the next bigger ancestor

Solution

1. Step 1: Check if node 25 has right subtree

   Node 25 has no right child, so successor is an ancestor.

2. Step 2: Find the lowest ancestor whose left subtree contains node 25

   Node 30 is the parent of 25 and is the next bigger node, so successor is 30.

3. Final Answer:

   30, because 25 has no right child and 30 is the next bigger ancestor -> Option D

4. Quick Check:

   Successor of 25 is 30 [OK]

Hint: If no right child, successor is nearest bigger ancestor [OK]

Common Mistakes:

• Choosing right child of parent instead of parent
• Assuming no successor if no right child
• Confusing root as successor