L41. Ceil in a Binary Search Tree (BST)

Finding the Ceil of a given key in a Binary Search Tree (BST) is a fundamental logarithmic-time search operation. This chapter explores the formal definition of a ceil, analyzes why standard BST properties make finding it efficient, and covers both the optimal iterative approach and complete production-ready implementations in C++ and Java.

1. What is a Ceil in a Binary Search Tree?

Before writing any code or searching through tree nodes, we must establish a rigorous mathematical definition of what a "Ceil" value represents in the context of a Binary Search Tree.

Definition: The Ceil of a given target key $X$ in a BST is defined as the smallest value in the BST that is greater than or equal to ($\ge$) $X$.

Concrete Numeric Example

Imagine we are given a BST containing the following node values: [8, 4, 12, 2, 6, 10, 14]

Let's evaluate what the ceil would be for various target keys ($X$):

• If $X = 5$: The values in the tree greater than or equal to $5$ are [6, 8, 10, 12, 14]. The smallest among these is $6$. Therefore, the ceil of $5$ is $6$.
• If $X = 8$: The value $8$ exists in the tree. Since ceil permits values equal to $X$, the ceil of $8$ is $8$.
• If $X = 15$: There are no values in the tree greater than or equal to $15$. Therefore, the ceil does not exist, and our function should return -1 (or null/inf depending on conventions).

2. The Core Mental Model & Binary Search Property

To solve this efficiently, we leverage the fundamental invariant of a Binary Search Tree:

• For any given node:
  • All values in its left subtree are strictly smaller than the node's value.
  • All values in its right subtree are strictly greater than the node's value.

Real-Life Analogy: The Price Range Selector

Think of finding a ceil value like searching for a flight ticket or laptop price on an e-commerce website where items are sorted from cheapest to most expensive:

• You need a laptop that costs at least $850$ ($X = 850$).
• You look at a candidate option priced at $1,000$. It satisfies your condition ($1000 \ge 850$), so it becomes a valid candidate. However, can you find a tighter (smaller) valid price that still meets your requirement? Since cheaper items are to the left, you step left to check if an item like $900$ or $850$ exists.
• If you look at a candidate priced at $700$, it is too cheap ($700 < 850$). It can never satisfy your requirement. Discarding it entirely, you step right to find more expensive options.

3. Naive Approach vs. Optimal BST Traversal

The Brute-Force Approach

A naive approach would perform a complete traversal of the BST (such as Inorder, Preorder, or Postorder traversal), visit every single node, store or check all node values that are $\ge X$, and finally find the minimum among them.

• Time Complexity: $O(N)$ because we visit every node in the tree.
• Space Complexity: $O(H)$ for the recursion stack during traversal, where $H$ is the height of the tree.

Why the Naive Approach Fails to Leverage BST Properties

The brute-force approach completely ignores the sorted nature of a BST. If we have a balanced BST with $1,000,000$ nodes, scanning every node takes $O(N)$ time. By utilizing the BST property, we can bypass entire subtrees and solve the problem in $O(H)$ time (which is $O(\log N)$ for a balanced tree).

4. Step-by-Step Evolution of the Optimal Iterative Algorithm

Instead of recursion which incurs stack frame overhead, we can implement the search for a ceil iteratively using a single pointer (curr or root) and a ceil variable to track our best candidate so far.

Algorithm Walkthrough

1. Initialize ceil to -1 (or a sentinel value indicating no valid ceil found yet).
2. Set a pointer curr to the root of the BST.
3. While curr is not null:
   • Case 1: Exact Match Found (curr.val == X)
     • If the current node's value is equal to $X$, then $X$ itself is the smallest value greater than or equal to $X$. We update ceil = curr.val and immediately terminate our search (return ceil), as we cannot possibly find a smaller valid number.
   • Case 2: Current Node is Too Small (curr.val < X)
     • If curr.val is strictly less than $X$, it cannot be a valid ceil (since it is smaller than $X$). We must look for larger values. Therefore, we move to the right subtree (curr = curr.right).
   • Case 3: Current Node is Valid (curr.val > X)
     • If curr.val is strictly greater than $X$, it is a valid candidate for our ceil! However, there might be an even closer (smaller) valid value tucked away in its left subtree. We record ceil = curr.val as our potential answer and then move to the left subtree (curr = curr.left) to search for a tighter fit.

5. Complete Flow Walkthrough

Let's trace the algorithm with a concrete example.

BST Structure:

       8
     /   \
    4     12
   / \    / \
  2   6  10  14

Target ($X$): 5

• Step 1: curr points to 8.

  • Is 8 == 5? No.
  • Is 8 < 5? No.
  • Is 8 > 5? Yes. 8 is a valid candidate.
  • Update ceil = 8.
  • Since we want a smaller valid value, move left: curr = 4.

• Step 2: curr points to 4.

  • Is 4 == 5? No.
  • Is 4 < 5? Yes. 4 is too small to be $\ge 5$. It cannot be our ceil.
  • Since we need larger values, move right: curr = 6.

• Step 3: curr points to 6.

  • Is 6 == 5? No.
  • Is 6 < 5? No.
  • Is 6 > 5? Yes. 6 is a valid candidate.
  • Update ceil = 6.
  • Move left: curr = null (since 6 has no left child).

• Termination: curr becomes null. Loop terminates.

• Final Result: ceil = 6.

6. Code Implementations

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 findCeil(TreeNode* root, int input) {
        int ceil = -1;
        TreeNode* curr = root;
        
        while (curr != nullptr) {
            // If we found the exact match, it is the optimal ceil
            if (curr->val == input) {
                ceil = curr->val;
                return ceil;
            }
            
            // If current value is smaller than input, ceil must lie in the right subtree
            if (curr->val < input) {
                curr = curr->right;
            } 
            // If current value is greater than input, it's a valid candidate
            // but we search the left subtree for a tighter (smaller) valid value
            else {
                ceil = curr->val;
                curr = curr->left;
            }
        }
        
        return ceil;
    }
};

int main() {
    // Constructing test BST
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(4);
    root->right = new TreeNode(12);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(6);
    root->right->left = new TreeNode(10);
    root->right->right = new TreeNode(14);

    Solution sol;
    int input = 5;
    std::cout << "Ceil of " << input << " is: " << sol.findCeil(root, input) << std::endl;

    return 0;
}

Java Implementation

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

public class Solution {
    public static int findCeil(TreeNode root, int input) {
        int ceil = -1;
        TreeNode curr = root;
        
        while (curr != null) {
            // Exact match is the best possible ceil
            if (curr.val == input) {
                ceil = curr.val;
                return ceil;
            }
            
            // If current node value is less than input, go right
            if (curr.val < input) {
                curr = curr.right;
            } 
            // If current node value is greater than input, store it and go left
            else {
                ceil = curr.val;
                curr = curr.left;
            }
        }
        
        return ceil;
    }

    public static void main(String[] args) {
        // Constructing test BST
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(4);
        root.right = new TreeNode(12);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(6);
        root.right.left = new TreeNode(10);
        root.right.right = new TreeNode(14);

        int input = 5;
        System.out.println("Ceil of " + input + " is: " + findCeil(root, input));
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Definition of Ceil: The ceil of a key $X$ in a BST is the smallest node value in the tree that is greater than or equal to ($\ge$) $X$.
• Leveraging BST Properties: By comparing the target key with the current node's value, we eliminate half of the remaining search space at each step, matching binary search efficiency.
• Handling Exact Matches: If curr.val == input, we immediately return curr.val because no smaller valid number greater than or equal to the input can exist.
• Candidate Tracking: When curr.val > input, we store curr.val as our potential answer (ceil = curr.val) and venture into the left subtree to search for a tighter match.
• Ignoring Invalid Subtrees: When curr.val < input, the current node and its entire left subtree are discarded because their values are too small; we move exclusively to the right subtree.
• Iterative Optimization: Implementing the search iteratively ensures $O(1)$ auxiliary space complexity by eliminating recursion stack overhead.
• Robust Failure Handling: If no valid ceil exists in the tree (i.e., all nodes are smaller than $X$), the algorithm correctly returns the initialized default value of -1.