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.