L42. Floor in a Binary Search Tree | BST

This comprehensive study note explores the problem of finding the Floor in a Binary Search Tree (BST), detailing the mathematical definition, core mental models, step-by-step tree traversals, production-ready code implementations in C++ and Java, and practical complexity analysis.

1. Why Do We Need This? (Problem Statement & Status Quo)

In many applications involving ordered data—such as database indexing, range queries, or streaming analytics—we often need to find specific elements relative to a target value. One such fundamental query is locating the Floor of a given key in a Binary Search Tree.

• Definition of Floor: Given a target key, the floor of that key is defined as the greatest value in the BST that is smaller than or equal to the given key ($\text{val} \le \text{key}$).
• Status Quo / Naive Approach: In an ordinary Binary Tree (without ordering properties), finding a floor requires visiting every single node ($\mathcal{O}(N)$ time complexity) because there is no inherent sorting guarantee.
• The BST Advantage: Because a Binary Search Tree maintains a strict left-child < parent < right-child ordering invariant, we can optimize this search drastically, matching the efficiency of binary search ($\mathcal{O}(\log N)$ time complexity).

2. Core Mental Model & Intuition

To understand how to find the floor efficiently, let us establish a mental model based on narrowing down candidates while traversing from the root downwards.

Real-Life Analogy: Price Matching in a Catalog

Imagine browsing a catalog of sorted prices arranged in a binary decision tree. You want to buy an item whose price is as close as possible to your budget of $7$, but without exceeding it.

1. You look at an item costing **$10**. It exceeds your budget ($10 > 7$), so it is disqualified. To find cheaper items, you must look to the left branch.
2. You find an item costing **$5**. It is within budget ($5 \le 7$), so it becomes your current best option (floor = 5). However, you want to spend as much of your budget as possible to get the best value, so you check if there are slightly more expensive items available by exploring the right branch.
3. You move right and find an item costing **$8**. Since$8 > 7$, it exceeds your budget and is disqualified.
4. You check its right child, which is empty (null). You stop, keeping $5$ as your final valid floor.

3. Step-by-Step Tree Traversal Workflow

Let us trace an explicit traversal example where the BST contains the values [2, 5, 8, 10, 12, 20] and our target key = 9.

          10
         /  \
        5    20
       / \
      2   8
          /
         9  (hypothetical or intermediate node position)

(Assume nodes 5 and 8 exist; let's trace root = 10, key = 9)

1. Start at Root (10):

   • Compare root value 10 with target key = 9.
   • Since 10 > 9, 10 cannot be our floor (it is strictly greater than the key).
   • We need a smaller value, so we move left.

2. At Node (5):

   • Compare 5 with 9.
   • Since 5 <= 9, 5 is a valid candidate! We update our floor = 5.
   • Can we find a greater valid value that is still $\le 9$? Since right subtree elements are larger than 5, we move right.

3. At Node (8):

   • Compare 8 with 9.
   • Since 8 <= 9, 8 is a valid candidate! We update our floor = 8.
   • We want an even closer value, so we try to move right.

4. Reaching null:

   • Moving right from 8 leads to null. Traversal terminates.
   • Final Answer: 8 is stored as the floor.

4. Algorithmic Logic & Edge Cases

When designing the traversal algorithm, we track a floor variable initialized to -1 (or a sentinel/null value if no floor exists).

Decision Matrix for Each Node

• Let the current node value be root.val and the target be key.

5. Production-Ready Code Implementations

Below are the clean, decoupled, production-grade implementations in C++ and Java, matching the exact logic discussed in the lecture.

C++ Implementation

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int findFloor(TreeNode* root, int key) {
        int floor = -1; // Initialize floor to -1 if no smaller/equal value exists
        
        while (root != nullptr) {
            // If we found an exact match, it is the optimal floor
            if (root->val == key) {
                floor = root->val;
                return floor;
            }
            
            // If current value is greater than key, we must go left to find smaller values
            if (root->val > key) {
                root = root->left;
            } 
            // If current value is smaller than key, it's a valid candidate. 
            // Store it and search the right subtree for a closer (larger) value.
            else {
                floor = root->val;
                root = root->right;
            }
        }
        
        return floor;
    }
};

Java Implementation

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int findFloor(TreeNode root, int key) {
        int floor = -1; // Initialize floor to -1 if no valid floor exists
        
        while (root != null) {
            // Exact match is the maximum possible floor
            if (root.val == key) {
                floor = root.val;
                return floor;
            }
            
            // If node value exceeds key, move left to decrease value
            if (root.val > key) {
                root = root.left;
            } 
            // If node value is less than key, save as candidate and move right to increase value
            else {
                floor = root.val;
                root = root.right;
            }
        }
        
        return floor;
    }
}

6. Complexity Analysis

7. Summary and Key Takeaways

• Definition Mastery: The floor of a key in a BST is the greatest value less than or equal to the target key ($\text{val} \le \text{key}$).
• Leveraging BST Properties: Unlike standard binary trees, the ordering property allows us to discard half the tree at every decision step.
• Traversal Strategy:
  • If root.val > key, move left without updating the floor.
  • If root.val < key, update the floor candidate and move right to find a closer, larger value.
  • If root.val == key, store the value and return immediately.
• Optimal Implementation: An iterative approach guarantees $\mathcal{O}(1)$ auxiliary space complexity, avoiding stack overflow risks associated with deep recursion.
• Edge Case Resilience: Initializing the floor variable to -1 safely handles cases where all elements in the BST are strictly greater than the search key.