BST Inorder Predecessor in DSA Javascript - 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 of a node is the node with the next smaller value in the BST.Think of the BST as a family tree sorted by age, and you want to find the person who is just older than a given person but younger than everyone else older than them.

🎯 Goal: Build a program that creates a BST, sets a target node value, finds the inorder predecessor of that node, 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 called targetValue set to 15

Write a function called findInorderPredecessor that finds the inorder predecessor of the node with value targetValue

Print the value of the inorder predecessor or null if it does not exist

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding BST operations like inorder predecessor is important for software engineers working with search algorithms, data retrieval, and optimization.

1

Create the BST nodes and build the tree

Create a class called Node with a constructor that takes value and sets left and right to null. Then create the nodes with values 20, 10, 30, 5, 15, 25, and 35. Connect them to form the BST exactly as follows: 20 is root, 10 is left child of 20, 30 is right child of 20, 5 is left child of 10, 15 is right child of 10, 25 is left child of 30, and 35 is right child of 30.

DSA Javascript

// Create Node class and nodes
// Connect nodes to form the BST
// Your code here

Hint

Start by defining the Node class with value, left, and right. Then create each node and connect them as described.

2

Set the target node value

Create a variable called targetValue and set it to 15.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(20);
root.left = new Node(10);
root.right = new Node(30);
root.left.left = new Node(5);
root.left.right = new Node(15);
root.right.left = new Node(25);
root.right.right = new Node(35);

// Set the target node value
// 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 and targetValue as parameters. It should find the node with targetValue in the BST and return the value of its inorder predecessor node. If the node has a left subtree, the predecessor is the rightmost node in that left subtree. Otherwise, the predecessor is the last node for which the target node is in the right subtree. Return null if no predecessor exists.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(20);
root.left = new Node(10);
root.right = new Node(30);
root.left.left = new Node(5);
root.left.right = new Node(15);
root.right.left = new Node(25);
root.right.right = new Node(35);

const targetValue = 15;

// Write function findInorderPredecessor(root, targetValue) below
// Your code here

Hint

Use a loop to find the target node. Track the last node smaller than target as predecessor. If the target has a left child, find the rightmost node in that left subtree. Otherwise, return the tracked predecessor.

4

Print the inorder predecessor value

Print the result of calling findInorderPredecessor(root, targetValue). It should print the predecessor's value or null if none exists.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(20);
root.left = new Node(10);
root.right = new Node(30);
root.left.left = new Node(5);
root.left.right = new Node(15);
root.right.left = new Node(25);
root.right.right = new Node(35);

const targetValue = 15;

function findInorderPredecessor(root, targetValue) {
    let predecessor = null;
    let current = root;

    // Find the target node
    while (current !== null) {
        if (targetValue > current.value) {
            predecessor = current; // potential predecessor
            current = current.right;
        } else if (targetValue < current.value) {
            current = current.left;
        } else {
            // Node found
            break;
        }
    }

    if (current === null) {
        return null; // target not found
    }

    // If left subtree exists, find rightmost node there
    if (current.left !== null) {
        let temp = current.left;
        while (temp.right !== null) {
            temp = temp.right;
        }
        return temp.value;
    }

    // Otherwise, predecessor is the last node for which current is in right subtree
    return predecessor ? predecessor.value : null;
}

// Print the inorder predecessor value
// Your code here

Hint

Call findInorderPredecessor(root, targetValue) and print the result using console.log.