BST Inorder Predecessor in DSA Typescript - Build from Scratch

BST Inorder Predecessor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the inorder predecessor of a given node. The inorder predecessor is the node with the largest value smaller than the given node's value.Think of the BST as a family tree sorted by age, and you want to find the closest older sibling who is younger than a specific person.

🎯 Goal: Build a TypeScript program that creates a BST, sets a target value, finds the inorder predecessor of that value in the BST, and prints the predecessor's value or null if none exists.

📋 What You'll Learn

Create a BST with the exact nodes: 20, 10, 30, 5, 15, 25, 35

Create a variable targetValue set to 15

Write a function findInorderPredecessor that finds the inorder predecessor of targetValue in the BST

Print the predecessor's value or null if no predecessor exists

💡 Why This Matters

🌍 Real World

Finding inorder predecessors is useful in database indexing and navigation systems where you need to find the closest smaller value to a given key.

💼 Career

Understanding BST traversal and predecessor/successor logic is important for software engineers working on search algorithms, data indexing, and optimization problems.

1

Create the BST nodes

Create a class called TreeNode with val, left, and right properties. Then create the BST with nodes having values 20, 10, 30, 5, 15, 25, and 35 arranged correctly as a BST.

DSA Typescript

// Define TreeNode class and create BST nodes
// Your code here

Hint

Define a TreeNode class with val, left, and right. Then create nodes and link them to form the BST.

2

Set the target value

Create a variable called targetValue and set it to 15.

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);
root.left = new TreeNode(10);
root.right = new TreeNode(30);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(15);
root.right.left = new TreeNode(25);
root.right.right = new TreeNode(35);

// Create targetValue variable and set it to 15
// Your code here

Hint

Just create a constant named targetValue and assign it the number 15.

3

Write the function to find the inorder predecessor

Write a function called findInorderPredecessor that takes root of type TreeNode | null and target of type number. It should return the inorder predecessor node or null if none exists. Use BST properties to find the predecessor efficiently.

DSA Typescript

function findInorderPredecessor(root: TreeNode | null, target: number): TreeNode | null {
    let predecessor: TreeNode | null = null;
    let current = root;
    while (current !== null) {
        if (target <= current.val) {
            current = current.left;
        } else {
            predecessor = current;
            current = current.right;
        }
    return predecessor;
// Print the predecessor value or null

Hint

Use a loop to traverse the BST. Move left if target is less or equal to current node's value. Otherwise, update predecessor and move right.

4

Print the inorder predecessor value

Call findInorderPredecessor with root and targetValue. Print the predecessor's val if it exists, otherwise print null.

DSA Typescript

Hint

Call the function and print the predecessor's value if found, else print null.