BST Inorder Successor in DSA Typescript

Mental Model

The inorder successor of a node in a BST is the next node in sorted order. It is the smallest node larger 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: 4 ↑
Inorder successor: 5

Dry Run Walkthrough

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

Goal: Find the node with the smallest value greater than 4 in the BST

Step 1: Check if node 4 has a right child

Node 4 has no right child

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

Step 2: Start from root (5) to find successor candidate

Current node: 5, candidate successor: null

Why: We look for a node greater than 4 to update candidate

Step 3: Since 4 < 5, update candidate to 5 and move left

Candidate successor: 5, move to node 3

Why: We want the smallest node greater than 4, so keep 5 and check left subtree

Step 4: Since 4 > 3, move right without updating candidate

Candidate successor: 5, move to node 4

Why: 4 is greater than 3, so successor must be in right subtree or above

Step 5: Reached node 4, stop traversal

Candidate successor: 5

Why: We found the node, candidate holds the inorder successor

Result:

5 -> 7 -> 8 -> null
Inorder successor of 4 is 5

Annotated Code

DSA Typescript

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

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
  if (p.right !== null) {
    // successor is leftmost node in right subtree
    let curr = p.right;
    while (curr.left !== null) {
      curr = curr.left; // move left to find smallest node
    }
    return curr;
  }

  let successor: TreeNode | null = null;
  let curr = root;
  while (curr !== null) {
    if (p.val < curr.val) {
      successor = curr; // update candidate
      curr = curr.left; // move left to find smaller candidate
    } else {
      curr = curr.right; // move right to find larger nodes
    }
  }
  return successor;
}

// Driver code
const root = new TreeNode(5,
  new TreeNode(3,
    new TreeNode(2),
    new TreeNode(4)
  ),
  new TreeNode(7,
    null,
    new TreeNode(8)
  )
);
const p = root.left.right; // node with value 4
const successor = inorderSuccessor(root, p);
if (successor !== null) {
  console.log(successor.val + " -> " + (successor.right ? successor.right.val : "null") + " -> null");
} else {
  console.log("null");
}

if (p.right !== null) {

check if node has right subtree to find successor

while (curr.left !== null) {

find leftmost node in right subtree

if (p.val < curr.val) {

update successor candidate when current node is greater

curr = curr.left;

move left to find smaller successor candidate

curr = curr.right;

move right when current node is less or equal to p

Output

5 -> 7 -> null

Complexity Analysis

Time: O(h) because we traverse from root down to leaf where h is tree height

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

vs Alternative: Naive approach does inorder traversal O(n) and stores nodes, which uses O(n) time and space; this method is more efficient by using BST properties

Edge Cases

Node has right subtree

Successor is leftmost node in right subtree

DSA Typescript

if (p.right !== null) {

Node has no right subtree and successor is ancestor

Traverse from root to find smallest ancestor greater than node

DSA Typescript

if (p.val < curr.val) {

Node is the largest in BST (no successor)

Function returns null

DSA Typescript

return successor;

When to Use This Pattern

When asked to find the next larger node in a BST, use inorder successor pattern leveraging BST properties to avoid full traversal.

Common Mistakes

Mistake: Not checking if node has right subtree first
Fix: Always check right subtree first to find successor quickly if it exists

Mistake: Not updating successor candidate correctly when moving left
Fix: Update successor candidate only when current node value is greater than target 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 given node in BST.

If node has right child, successor is leftmost node there; else, successor is smallest ancestor greater than node.