Find the Ceil in a Binary Search Tree (BST)

Given a binary search tree (BST) and a target value x, write a program to find the Ceil of x in the BST. The Ceil of x is the smallest element in the BST that is greater than or equal to x. If no such element exists, return -1.

Input/Output Examples

plaintext
Example 1:
Input:

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

x = 5
Output: 6
Explanation: The smallest value greater than or equal to 5 in the BST is 6.

Example 2:
Input:

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

x = 13
Output: 14
Explanation: The smallest value greater than or equal to 13 in the BST is 14.

Example 3:
Input:

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

x = 15
Output: -1
Explanation: There is no value greater than or equal to 15 in the BST.

Approach to Find the Ceil in a BST

  1. Binary Search Tree Property:
    • In a BST, for any node N, all nodes in its left subtree are smaller than N, and all nodes in its right subtree are larger than N.
    • This property allows us to efficiently find the ceil value by traversing the tree.
  2. Recursive or Iterative Approach:
    • Start from the root of the tree.
    • If the value of the current node is equal to x, then x is the ceil.
    • If the value of the current node is greater than x, the current node may be the ceil, but there might be a smaller value in the left subtree that is still greater than or equal to x. Thus, move to the left subtree and keep track of the current node.
    • If the value of the current node is smaller than x, move to the right subtree, as the ceil must be in the right subtree.
    • If no such value is found, return -1.
  3. Edge Case:
    • If the tree is empty, return -1.

C++ Program to Find the Ceil in a BST

cpp
#include <iostream>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Function to find the ceil value in a BST
int findCeil(TreeNode* root, int x) {
    int ceil = -1;

    while (root != NULL) {
        if (root->data == x) {
            return root->data;
        }

        // If the current node's value is greater than x, it could be the ceil
        if (root->data > x) {
            ceil = root->data;
            root = root->left;
        }
        // Move to the right subtree if the current node's value is smaller than x
        else {
            root = root->right;
        }
    }

    return ceil;
}

int main() {
    // Create a sample 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 x = 5;
    int ceilValue = findCeil(root, x);

    if (ceilValue != -1) {
        cout << "Ceil of " << x << " in the BST is: " << ceilValue << endl;
    } else {
        cout << "Ceil not found for " << x << " in the BST." << endl;
    }

    return 0;
}

Java Program to Find the Ceil in a BST

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class CeilInBST {

    // Function to find the ceil value in a BST
    public static int findCeil(TreeNode root, int x) {
        int ceil = -1;

        while (root != null) {
            if (root.data == x) {
                return root.data;
            }

            // If the current node's value is greater than x, it could be the ceil
            if (root.data > x) {
                ceil = root.data;
                root = root.left;
            }
            // Move to the right subtree if the current node's value is smaller than x
            else {
                root = root.right;
            }
        }

        return ceil;
    }

    public static void main(String[] args) {
        // Create a sample 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 x = 5;
        int ceilValue = findCeil(root, x);

        if (ceilValue != -1) {
            System.out.println("Ceil of " + x + " in the BST is: " + ceilValue);
        } else {
            System.out.println("Ceil not found for " + x + " in the BST.");
        }
    }
}

Python Program to Find the Ceil in a BST

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to find the ceil value in a BST
def find_ceil(root, x):
    ceil = -1

    while root:
        if root.data == x:
            return root.data

        # If the current node's value is greater than x, it could be the ceil
        if root.data > x:
            ceil = root.data
            root = root.left
        # Move to the right subtree if the current node's value is smaller than x
        else:
            root = root.right

    return ceil

# Example usage
if __name__ == "__main__":
    # Create a sample BST
    root = TreeNode(8)
    root.left = TreeNode(4)
    root.right = TreeNode(12)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(6)
    root.right.left = TreeNode(10)
    root.right.right = TreeNode(14)

    x = 5
    ceil_value = find_ceil(root, x)

    if ceil_value != -1:
        print(f"Ceil of {x} in the BST is: {ceil_value}")
    else:
        print(f"Ceil not found for {x} in the BST.")
  • Time Complexity: O(h), where h is the height of the binary search tree. In the worst case, this could be O(n) for a skewed tree, but for a balanced BST, it is O(log n).
  • Space Complexity: O(1) for the iterative approach, as no extra space is required other than variables.

DSA

3846

135

Related Articles