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.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The greatest value in the BST less than or equal to the given value

B. The smallest value in the BST greater than or equal to the given value

C. The root value of the BST

D. The average of all values in the BST

Solution

1. Step 1: Understand the definition of floor in BST

   The floor of a value in BST is the greatest value that is less than or equal to the given value.

2. Step 2: Compare with other options

   The smallest value in the BST greater than or equal to the given value describes ceil, not floor. Options C and D are unrelated to floor concept.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option A

4. Quick Check:

   Floor = greatest ≤ value [OK]

Hint: Floor is largest value ≤ target in BST [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is the smallest value
• Assuming floor is always the root

2. Which of the following TypeScript function signatures correctly represents a function to find the ceil in a BST?

easy

A. function findCeil(key: number, root: TreeNode): number

B. function findCeil(root: TreeNode | null, key: number): number | null

C. function findCeil(root: TreeNode, key: string): number

D. function findCeil(root: TreeNode | null): number

Solution

1. Step 1: Check parameter order and types

   Function should accept root node (possibly null) and a key number to find ceil for.

2. Step 2: Validate return type

   Return type should be number or null if no ceil found. function findCeil(root: TreeNode | null, key: number): number | null matches this.

3. Final Answer:

   function findCeil(root: TreeNode | null, key: number): number | null -> Option B

4. Quick Check:

   Correct params and return type [OK]

Hint: Root first, key second, return number or null [OK]

Common Mistakes:

• Swapping parameter order
• Using wrong parameter types
• Missing null in root type

3. Given the BST below and key = 14, what is the ceil value?

       10
      /  \
     5    15
         /  \
        12   20

medium

A. 12

B. 20

C. 15

D. null

Solution

1. Step 1: Locate key 14 in BST or nearest nodes

   14 is not in BST. Check nodes greater than or equal to 14: 15 and 20.

2. Step 2: Find smallest node ≥ 14

   Between 15 and 20, 15 is smaller and ≥ 14, so ceil is 15.

3. Final Answer:

   15 -> Option C

4. Quick Check:

   Ceil = smallest ≥ 14 is 15 [OK]

Hint: Ceil is smallest value ≥ key in BST [OK]

Common Mistakes:

• Choosing 12 which is less than 14
• Choosing 20 which is larger but not smallest ≥ 14
• Returning null when ceil exists

4. Consider this TypeScript function to find floor in BST:

function findFloor(root: TreeNode | null, key: number): number | null {
  if (!root) return null;
  if (root.val === key) return root.val;
  const floorRight = findFloor(root.right, key);
  return floorRight !== null ? floorRight : root.val;
}

What is the bug in this code?

medium

A. It returns root.val even if floorRight is null and root.val > key

B. It does not check for null root

C. It returns key instead of floor value

D. It incorrectly calls findFloor on root.left when root.val < key

Solution

1. Step 1: Identify missing logic for root.val > key

   The code does not recurse into the left subtree when root.val > key. Instead, it always computes floorRight from the right subtree.

2. Step 2: Trace buggy return

   When root.val > key and right subtree yields null for floorRight (common case), it returns root.val which exceeds key, violating floor definition.

3. Final Answer:

   It returns root.val even if floorRight is null and root.val > key -> Option A

4. Quick Check:

   Missing left recursion on root.val > key [OK]

Hint: Check return when right subtree floor is null [OK]

Common Mistakes:

• Ignoring null checks
• Confusing left and right subtree calls
• Assuming root.val always valid floor

5. You have a BST with values [8, 4, 12, 2, 6, 10, 14]. You want to find the floor and ceil of 5. Which pair is correct?

medium

A. Floor = 2, Ceil = 8

B. Floor = 6, Ceil = 4

C. Floor = 5, Ceil = 5

D. Floor = 4, Ceil = 6

Solution

1. Step 1: Identify floor of 5 in BST

   Floor is greatest value ≤ 5. Values ≤ 5 are 2 and 4. Greatest is 4.

2. Step 2: Identify ceil of 5 in BST

   Ceil is smallest value ≥ 5. Values ≥ 5 are 6, 8, 10, 12, 14. Smallest is 6.

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option D

4. Quick Check:

   Floor ≤ 5 = 4, Ceil ≥ 5 = 6 [OK]

Hint: Floor ≤ key, Ceil ≥ key; pick closest values [OK]

Common Mistakes:

• Swapping floor and ceil values
• Assuming floor or ceil equals key if not present
• Choosing values not in BST