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.