Floor and Ceil in BST in DSA Javascript - 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 existing phone number that is less than or equal to a given number (floor), and the closest existing phone number that is greater than or equal to a given number (ceil).

🎯 Goal: Build functions to find the floor and ceil values for a given number in a BST of phone numbers.

📋 What You'll Learn

Create a BST with given phone numbers

Add a variable for the target phone number to search floor and ceil for

Write functions to find floor and ceil values in the BST

Print the floor and ceil values for the target number

💡 Why This Matters

🌍 Real World

Finding floor and ceil values in BSTs is useful in phone book lookups, database indexing, and range queries where you want closest matches.

💼 Career

Understanding BST operations and floor/ceil logic is important for software engineers working with search algorithms, databases, and performance optimization.

1

Create the BST with phone numbers

Create a class called Node with value, left, and right properties. Then create a BST by creating nodes with these exact phone numbers: 50, 30, 70, 20, 40, 60, 80. Link them to form a valid BST.

DSA Javascript

// Create Node class and BST nodes with values 50, 30, 70, 20, 40, 60, 80
// Link nodes to form BST

Hint

Define a Node class with value, left, and right. Then create nodes and assign left and right to build the BST.

2

Add the target number variable

Create a variable called target and set it to 65. This is the number you will find floor and ceil for in the BST.

DSA Javascript

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

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

// Create target variable with value 65

Hint

Just create a constant variable named target and assign 65.

3

Write functions to find floor and ceil in BST

Write two functions: findFloor(root, target) and findCeil(root, target). Each function takes the BST root and the target number. findFloor returns the greatest value in BST less than or equal to target or null if none. findCeil returns the smallest value in BST greater than or equal to target or null if none.

DSA Javascript

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

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

const target = 65;

// Write findFloor and findCeil functions below

Hint

Use a loop starting at root. For floor, go left if current value > target, else update floor and go right. For ceil, go right if current value < target, else update ceil and go left.

4

Print the floor and ceil values

Use console.log to print the floor and ceil values for target using findFloor(root, target) and findCeil(root, target). Print exactly like this: Floor: 60 and Ceil: 70.

DSA Javascript

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

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

const target = 65;

function findFloor(root, target) {
  let floor = null;
  let current = root;
  while (current) {
    if (current.value === target) {
      return current.value;
    } else if (current.value > target) {
      current = current.left;
    } else {
      floor = current.value;
      current = current.right;
    }
  }
  return floor;
}

function findCeil(root, target) {
  let ceil = null;
  let current = root;
  while (current) {
    if (current.value === target) {
      return current.value;
    } else if (current.value < target) {
      current = current.right;
    } else {
      ceil = current.value;
      current = current.left;
    }
  }
  return ceil;
}

// Print floor and ceil for target

Hint

Use console.log to print floor and ceil with the exact format: Floor: value and Ceil: value.

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 floor concept in BST

   The floor of a value is the largest value in the BST 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 the ceil, not the floor. Options C and D are unrelated to floor.

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 is the correct JavaScript function signature to find the ceil of a value in a BST?

easy

A. function ceilFind(value, root) {}

B. function findFloor(value) {}

C. function findCeil(root, value) {}

D. function ceil(root) {}

Solution

1. Step 1: Identify correct parameter order and naming

   The function to find ceil should take the BST root and the target value as parameters, typically as (root, value).

2. Step 2: Check options for correct signature

   function findCeil(root, value) {} matches this pattern. function ceilFind(value, root) {} reverses parameters, C is for floor and missing root, D misses value parameter.

3. Final Answer:

   function findCeil(root, value) {} -> Option C

4. Quick Check:

   Correct params: root, value [OK]

Hint: Function needs root and value parameters [OK]

Common Mistakes:

• Swapping parameter order
• Missing root or value parameter
• Using wrong function name

3. Given the BST below and value = 14, what is the floor of 14?

       15
      /  \
     10  20
    /  \   \
   8   12  25

medium

A. 15

B. 10

C. 14

D. 12

Solution

1. Step 1: Locate floor value in BST for 14

   Floor is greatest value ≤ 14. Values ≤ 14 are 8, 10, 12. 12 is the greatest among these.

2. Step 2: Confirm no value closer to 14 exists

   15 is greater than 14, so not floor. 14 is not in BST.

3. Final Answer:

   12 -> Option D

4. Quick Check:

   Floor(14) = 12 [OK]

Hint: Floor ≤ value, pick largest such node [OK]

Common Mistakes:

• Choosing 15 which is > 14
• Assuming floor must be exact value
• Picking smaller values like 10 instead of 12

4. Consider this buggy JavaScript code to find ceil in BST:

function findCeil(root, value) {
  if (!root) return -1;
  if (root.val === value) return root.val;
  if (root.val < value) return findCeil(root.right, value);
  let ceil = findCeil(root.left, value);
  return (ceil >= value) ? ceil : root.val;
}

What is the main error?

medium

A. It searches left subtree when root.val < value instead of right

B. It returns -1 when root is null instead of null

C. It compares ceil with value incorrectly

D. It does not handle root.val === value case

Solution

1. Step 1: Analyze subtree traversal logic

   If root.val < value, ceil must be in right subtree, but code wrongly searches left subtree.

2. Step 2: Check other parts

   Return -1 is acceptable as sentinel. Comparison and equality check are correct.

3. Final Answer:

   It searches left subtree when root.val < value instead of right -> Option A

4. Quick Check:

   Wrong subtree chosen for root.val < value [OK]

Hint: Go right if root.val < value for ceil [OK]

Common Mistakes:

• Searching wrong subtree
• Ignoring base case
• Incorrect comparison logic

5. You want to find both floor and ceil of value 17 in this BST:

       16
      /  \
     10  20
    /  \   \
   8   12  25

Which pair is correct?

hard

A. [16, 17]

B. [16, 20]

C. [17, 20]

D. [15, 20]

Solution

1. Step 1: Find floor of 17

   Floor is greatest value ≤ 17. Values ≤ 17 are 8, 10, 12, 16. Largest is 16.

2. Step 2: Find ceil of 17

   Ceil is smallest value ≥ 17. Values ≥ 17 are 20, 25. Smallest is 20.

3. Final Answer:

   [16, 20] -> Option B

4. Quick Check:

   Floor=16, Ceil=20 [OK]

Hint: Floor ≤ value, ceil ≥ value, pick closest [OK]

Common Mistakes:

• Assuming floor or ceil equals value if not present
• Choosing wrong subtree values
• Mixing floor and ceil values