BST Inorder Successor in DSA Typescript - Build from Scratch

BST Inorder Successor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the next bigger number after a given number in the tree. This is called the inorder successor.Think of the BST as a sorted list of numbers arranged in a tree shape. Finding the inorder successor means finding the number that comes right after a given number when you look at the numbers in order.

🎯 Goal: Build a TypeScript program that creates a BST, sets a target node, and finds the inorder successor of that node.

📋 What You'll Learn

Create a BST node class with val, left, and right properties

Manually build a BST with specific values

Set a target node to find its inorder successor

Write a function to find the inorder successor of the target node

Print the value of the inorder successor or null if none exists

💡 Why This Matters

🌍 Real World

Finding the inorder successor is useful in database indexing and navigation systems where you need to find the next item in sorted order quickly.

💼 Career

Understanding BST operations like inorder successor is important for software engineers working on search algorithms, data storage, and optimization problems.

1

Create BST Node Class and Build Tree

Create a class called TreeNode with a constructor that takes a number val and sets left and right to null. Then create the following BST nodes and connect them to form this tree:

20
/ \
10 30
/ \ \
5 15 40

Use variables named root, node10, node30, node5, node15, and node40 for the nodes.

DSA Typescript

// Create TreeNode class and build the BST
// Your code here

Hint

Start by defining the TreeNode class with the constructor. Then create each node with the exact values and connect them as shown.

2

Set Target Node

Create a variable called target and set it to the node with value 10 (use the variable node10).

DSA Typescript

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

const root = new TreeNode(20);
const node10 = new TreeNode(10);
const node30 = new TreeNode(30);
const node5 = new TreeNode(5);
const node15 = new TreeNode(15);
const node40 = new TreeNode(40);

root.left = node10;
root.right = node30;
node10.left = node5;
node10.right = node15;
node30.right = node40;

// Set target node to node10
// Your code here

Hint

Simply assign the variable target to the existing node10 variable.

3

Write Function to Find Inorder Successor

Write a function called inorderSuccessor that takes root: TreeNode | null and p: TreeNode as parameters and returns the inorder successor node or null if none exists.

Use the BST property to find the successor:
- If p.val is less than root.val, the successor could be root or in the left subtree.
- If p.val is greater or equal, search in the right subtree.

Return the node that is the next bigger value after p.val.

DSA Typescript

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

const root = new TreeNode(20);
const node10 = new TreeNode(10);
const node30 = new TreeNode(30);
const node5 = new TreeNode(5);
const node15 = new TreeNode(15);
const node40 = new TreeNode(40);

root.left = node10;
root.right = node30;
node10.left = node5;
node10.right = node15;
node30.right = node40;

const target = node10;

// Write inorderSuccessor function below
// Your code here

Hint

Use recursion and compare p.val with root.val. If smaller, check left subtree and keep current root as possible successor. If greater or equal, go right.

4

Print the Inorder Successor Value

Call inorderSuccessor with root and target. Print the value of the returned node if it exists, otherwise print null.

DSA Typescript

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

const root = new TreeNode(20);
const node10 = new TreeNode(10);
const node30 = new TreeNode(30);
const node5 = new TreeNode(5);
const node15 = new TreeNode(15);
const node40 = new TreeNode(40);

root.left = node10;
root.right = node30;
node10.left = node5;
node10.right = node15;
node30.right = node40;

const target = node10;

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
    if (root === null) return null;
    if (p.val < root.val) {
        const left = inorderSuccessor(root.left, p);
        return left !== null ? left : root;
    } else {
        return inorderSuccessor(root.right, p);
    }
}

// Print the value of the inorder successor or null
// Your code here

Hint

Call the function and print the successor's value if it exists, else print null.

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