Floor and Ceil in BST in DSA Typescript - Build from Scratch

Floor and Ceil in BST

📖 Scenario: You are working with a phone book application that stores contacts in a Binary Search Tree (BST) by their phone numbers. You want to find the closest phone number less than or equal to a given number (floor) and the closest phone number greater than or equal to that number (ceil).

🎯 Goal: Build a TypeScript program that creates a BST with given phone numbers, then finds the floor and ceil values for a target phone number.

📋 What You'll Learn

Create a BST node class called Node with data, left, and right properties

Create a BST by inserting given phone numbers in order

Create a variable called target with the exact value 65

Write functions floorInBST and ceilInBST that find floor and ceil values for target

Print the floor and ceil values exactly as shown

💡 Why This Matters

🌍 Real World

Finding floor and ceil values in a BST is useful in applications like phone book lookups, price filtering, and range queries where you want the closest available value to a target.

💼 Career

Understanding BST operations and floor/ceil logic is important for software engineers working on search engines, databases, and any system requiring efficient data retrieval.

1

Create BST Node class and insert nodes

Create a class called Node with a constructor that takes a number data and initializes left and right as null. Then create a variable called root and insert these numbers in this order: 50, 30, 70, 20, 40, 60, 80. Use a function called insertNode to insert nodes into the BST.

DSA Typescript

// Create Node class
// Create insertNode function
// Insert nodes 50, 30, 70, 20, 40, 60, 80 into root

Hint

Define the Node class with data, left, and right. Use recursion in insertNode to place nodes correctly.

2

Create target variable

Create a variable called target and set it to the number 65.

DSA Typescript

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

function insertNode(root: Node | null, data: number): Node {
    if (root === null) {
        return new Node(data);
    }
    if (data < root.data) {
        root.left = insertNode(root.left, data);
    } else {
        root.right = insertNode(root.right, data);
    }
    return root;
}

let root: Node | null = null;
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 70);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 60);
root = insertNode(root, 80);

// Create target variable with value 65

Hint

Just create a number variable named target and assign 65.

3

Write floorInBST and ceilInBST functions

Write a function called floorInBST that takes root and target and returns the floor value (largest number less than or equal to target). Also write a function called ceilInBST that returns the ceil value (smallest number greater than or equal to target). Use BST properties to find these values efficiently.

DSA Typescript

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

function insertNode(root: Node | null, data: number): Node {
    if (root === null) {
        return new Node(data);
    }
    if (data < root.data) {
        root.left = insertNode(root.left, data);
    } else {
        root.right = insertNode(root.right, data);
    }
    return root;
}

let root: Node | null = null;
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 70);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 60);
root = insertNode(root, 80);

let target: number = 65;

// Write floorInBST function
// Write ceilInBST function

Hint

Use a loop to traverse the BST. For floor, move left if current data is greater than target, else update floor and move right. For ceil, do the opposite.

4

Print floor and ceil values

Print the floor value by calling floorInBST(root, target) and the ceil value by calling ceilInBST(root, target). Use console.log with these exact messages:
Floor value: <floor_value>
Ceil value: <ceil_value>

DSA Typescript

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

function insertNode(root: Node | null, data: number): Node {
    if (root === null) {
        return new Node(data);
    }
    if (data  target) {
            current = current.left;
        } else {
            floor = current.data;
            current = current.right;
        }
    }
    return floor;
}

function ceilInBST(root: Node | null, target: number): number | null {
    let ceil: number | null = null;
    let current = root;
    while (current !== null) {
        if (current.data === target) {
            return current.data;
        } else if (current.data < target) {
            current = current.right;
        } else {
            ceil = current.data;
            current = current.left;
        }
    }
    return ceil;
}

// Print floor and ceil values

Hint

Call the functions with root and target. Print results with console.log using the exact messages.