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.

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 node with a key greater than the current node.

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 node [OK]

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

Common Mistakes:

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

2. Which of the following TypeScript function signatures correctly represents a function to find the inorder successor in a BST node?

easy

A. function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null

B. function inorderSuccessor(p: TreeNode): TreeNode

C. function inorderSuccessor(root: TreeNode): void

D. function inorderSuccessor(root: TreeNode, p: TreeNode): number

Solution

1. Step 1: Analyze parameters needed

   To find inorder successor, we need the BST root and the target node p.

2. Step 2: Analyze return type

   The function returns the successor node or null if none exists.

3. Final Answer:

   function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null -> Option A

4. Quick Check:

   Correct params and return type [OK]

Hint: Successor function needs root and target node, returns node or null [OK]

Common Mistakes:

• Missing root parameter
• Wrong return type (void or number)
• Not allowing null root

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

      6
     / \
    2   8
   / \   \
  0   4   9
     / \
    3   5

medium

A. Node with value 8

B. Node with value 6

C. Node with value 4

D. Node with value 9

Solution

1. Step 1: Locate node 5 and check right subtree

   Node 5 has no right child, so successor is one of its ancestors.

2. Step 2: Find lowest ancestor whose left child is ancestor of node 5

   Node 6 is the first ancestor where node 5 is in left subtree, so successor is node 6.

3. Final Answer:

   Node with value 6 -> Option B

4. Quick Check:

   Successor of 5 is 6 [OK]

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

Common Mistakes:

• Choosing right child of root instead of ancestor
• Picking node 8 which is too big
• Confusing predecessor with successor

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

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

What is the bug in this code?

medium

A. It may cause infinite loop if root is null

B. It incorrectly updates the successor when p.val > root.val

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

D. It returns the predecessor instead of successor

Solution

1. Step 1: Understand code logic

   The code moves down the tree to find the smallest node greater than p.val, updating successor accordingly.

2. Step 2: Identify missing case

   If p has a right subtree, the successor is the leftmost node in that subtree, but this code ignores that and only searches from root.

3. Final Answer:

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

4. Quick Check:

   Right subtree check missing [OK]

Hint: Check right subtree first for successor [OK]

Common Mistakes:

• Ignoring right subtree of p
• Assuming successor always in ancestors
• Confusing successor with predecessor

5. You have a BST and want to find the inorder successor of a node p. The node p has a right child. Which of the following is the correct approach to find the inorder successor?

hard

A. Return the root of the BST

B. Return the rightmost node in p's left subtree

C. Return the parent of p

D. Return the leftmost node in p's right subtree

Solution

1. Step 1: Check if p has right subtree

   If p has a right child, the inorder successor is the smallest node in that right subtree.

2. Step 2: Find leftmost node in right subtree

   Traverse left children starting from p's right child until no more left child exists.

3. Final Answer:

   Return the leftmost node in p's right subtree -> Option D

4. Quick Check:

   Successor in right subtree's leftmost node [OK]

Hint: Successor with right child = leftmost node in right subtree [OK]

Common Mistakes:

• Returning parent instead of leftmost right subtree node
• Returning rightmost left subtree node
• Returning root regardless of p