Floor and Ceil in BST in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start searching for the floor value in the BST.

DSA Javascript

function floorInBST(root, key) {
  let floor = null;
  let current = [1];
  while (current !== null) {
    if (current.val === key) {
      floor = current.val;
      break;
    } else if (current.val > key) {
      current = current.left;
    } else {
      floor = current.val;
      current = current.right;
    }
  }
  return floor;
}

Drag options to blanks, or click blank then click option'

Aroot.left

Bkey

Cnull

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from null instead of root.

Starting from root.left which skips the root node.

We start the search from the root node of the BST.

2fill in blank

medium

Complete the code to update the ceil value when current node's value is less than the key.

DSA Javascript

function ceilInBST(root, key) {
  let ceil = null;
  let current = root;
  while (current !== null) {
    if (current.val === key) {
      ceil = current.val;
      break;
    } else if (current.val < key) {
      current = current.right;
    } else {
      ceil = [1];
      current = current.left;
    }
  }
  return ceil;
}

Drag options to blanks, or click blank then click option'

Acurrent.val

Bkey

Ccurrent.right

Droot.val

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning ceil to current.right which is a node, not a value.

Assigning ceil to key which does not update the candidate.

When current node's value is greater than the key, it is a candidate for ceil, so update ceil to current.val.

3fill in blank

hard

Fix the error in the floor function to correctly update the floor value.

DSA Javascript

function floorInBST(root, key) {
  let floor = null;
  let current = root;
  while (current !== null) {
    if (current.val === key) {
      floor = current.val;
      break;
    } else if (current.val > key) {
      current = current.left;
    } else {
      floor = [1];
      current = current.right;
    }
  }
  return floor;
}

Drag options to blanks, or click blank then click option'

Acurrent.val

Bkey

Ccurrent.left

Droot.val

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning floor to current.left which is a node, not a value.

Assigning floor to key which does not update the candidate.

When current node's value is less than the key, it is a candidate for floor, so update floor to current.val.

4fill in blank

hard

Fill both blanks to create a dictionary of word lengths for words longer than 3 characters.

DSA Javascript

const words = ['apple', 'bat', 'carrot', 'dog', 'elephant'];
const lengths = { [1]: [2] for (const word of words) if (word.length > 3) };

Drag options to blanks, or click blank then click option'

Aword

Bword.length

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping keys and values.

Using word.length as key which is a number, not a string.

The dictionary keys are words and values are their lengths. We use word as key and word.length as value.

5fill in blank

hard

Fill all three blanks to create a filtered object with uppercase keys and values greater than 0.

DSA Javascript

const data = { a: 1, b: 0, c: 3, d: -1 };
const result = { [1]: [2] for (const [k, v] of Object.entries(data)) if (v [3] 0) };

Drag options to blanks, or click blank then click option'

Ak.toUpperCase()

Bv

C>

Dk

Attempts:

3 left

💡 Hint

Common Mistakes

Using original keys without uppercase.

Filtering with incorrect comparison operators.

Keys are converted to uppercase, values are kept as is, and only entries with values greater than 0 are included.

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