BST Inorder Successor in DSA Javascript

Mental Model

The inorder successor of a node in a BST is the next node in sorted order. It is the smallest node greater than the given node.

Analogy: Imagine a line of people sorted by height. The inorder successor of a person is the next taller person standing right after them.

      5
     / \
    3   7
   / \   \
  2   4   8

Node: 3 ↑
Inorder successor: 4

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find inorder successor of node 3

Goal: Find the node that comes immediately after 3 in sorted order, which is 4

Step 1: Check if node 3 has a right child

Node 3 -> right child 4
BST structure unchanged

Why: If right child exists, successor is the leftmost node in right subtree

Step 2: Go to right child 4 and check if it has left child

Node 4 -> no left child
BST structure unchanged

Why: Leftmost node in right subtree is 4 itself

Step 3: Return node 4 as inorder successor

Successor found: 4

Why: 4 is the smallest node greater than 3

Result:

4

Annotated Code

DSA Javascript

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

function inorderSuccessor(root, p) {
  // Case 1: If p has right child, go deep left from right child
  if (p.right) {
    let curr = p.right;
    while (curr.left) {
      curr = curr.left; // advance curr to left child to find smallest
    }
    return curr;
  }

  // Case 2: No right child, find lowest ancestor where p is in left subtree
  let successor = null;
  let curr = root;
  while (curr) {
    if (p.val < curr.val) {
      successor = curr; // potential successor
      curr = curr.left; // go left to find smaller successor
    } else {
      curr = curr.right; // go right to find p
    }
  }
  return successor;
}

// Driver code
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(7);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(8);

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

if (p.right) {

Check if node p has a right subtree to find successor there

while (curr.left) {

Traverse left to find smallest node in right subtree

let successor = null;

Initialize successor as null for ancestor search

while (curr) {

Traverse from root to find lowest ancestor greater than p

if (p.val < curr.val) {

If current node is greater than p, update successor and go left

else { curr = curr.right; }

If current node is less or equal, go right to find p

Output

4

Complexity Analysis

Time: O(h) because we traverse down the tree height h once to find successor

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Naive approach does inorder traversal O(n) and then finds successor, which is slower than this O(h) method

Edge Cases

Node p has no right child and is the largest node

Successor is null because no node is greater than p

DSA Javascript

return successor;

Node p has right child with no left subtree

Successor is the right child itself

DSA Javascript

if (p.right) { let curr = p.right; while (curr.left) { curr = curr.left; } return curr; }

Node p is root with right subtree

Successor found in right subtree as smallest node

DSA Javascript

if (p.right) { ... }

When to Use This Pattern

When asked to find the next bigger node in a BST, use the inorder successor pattern by checking right subtree or ancestors.

Common Mistakes

Mistake: Only checking right subtree and ignoring ancestor search when no right child
Fix: Add ancestor traversal from root to find lowest ancestor greater than p

Mistake: Returning the right child directly without going to its leftmost node
Fix: Traverse left children from right child to find smallest node

Summary

Finds the next node in sorted order after a given node in a BST.

Use when you need the immediate larger value than a node in BST.

If right subtree exists, successor is leftmost node there; else, it's the lowest ancestor greater than the node.

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