Ceil in a Binary Search Tree - Striver's A2Z DSA Course

Problem Statement: Given a BST and a number X, find the Ceil of X.
Note: Ceil(X) is a number that is either equal to X or is immediately greater than X.

If Ceil cannot be found, return -1.

Examples

Example 1:

Input Format:

X = 3

Result: 3

Explanation: We find 3 in BST, so ceil of 3 is 3.

Example 2:

Input Format:

X = 6

Result: 7

Explanation: We find 7 in BST, so ceil of 6 is 7 as the immediate number greater than 6 appears to be 7 in the BST.

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Practice:

Solve Problem

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution:

Approach:

This Problem can be easily solved by using a similar approach as we use to Binary Search a linear array and find the number that is just greater or equal to the given target input value.

Algorithm:

We start from the root element and check whether the number whose ceil we have to find out is equal to the value of the root or not. If its value is equal, we simply return the number.
Now, if the value of the number is not equal to the root’s value but is greater, we can conclude by saying that the number’s ceil value also lies in the right subtree of the given BST because, in BST, the right subtree contains all the elements whose values are greater than the root element.
If the value of the number, however, is lesser than the root’s value, then a possible ceil value could be the root itself as the number is less than its value. So, to check whether the number can be reduced further, we move to the left subtree and keep on updating the ceiling value accordingly.
Once, we encounter any node whose value is null, we return the computed ceil value.

Dry-run: Please refer to the attached video for a detailed dry-run.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

//Declaring the struct for Tree implementation.
struct node
{
    int data;
    struct node *left, *right;
};

//Defining a function for inserting new-node in BST
struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return (node);
}

int findCeil(node *root, int input)
{

    int ceil = -1;
    
    while (root)
    {
        // If the input is already available in BST, return that.
        if (root->data == input)
            return input;

        // If the input is greater than root, then the ceil value must be in the right subtree.
        else if (root->data < input)
        {
            root = root->right;
        }

        // Otherwise, we mark ceil to be root and move to 
        // left subtree where it may be further closer to the input value
        else
        {
            ceil = root->data;
            root = root->left;
        }
    }

    //Return computed ceil value.
    return ceil;
}

int main()
{
    // Driver Code.
    struct node *root = newNode(10);
    root->left = newNode(5);
    root->left->left = newNode(4);
    root->left->right = newNode(7);
    root->left->right->right = newNode(8);
    root->right = newNode(11);

    cout << findCeil(root, 6);
    cout << endl;

    return 0;
}

Output: 7

Time Complexity: O(log(N)) {Similar to Binary Search, at a given time we’re searching one half of the tree, so the time taken would be of the order log(N) where N are the total nodes in the BST and log(N) is the height of the tree.}

Space Complexity: O(1) {As no extra space is being used, we’re just traversing the BST.}

Java Code

class Node {
    int data;
    Node left, right;
    
    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class CeilInBST {
    static int findCeil(Node root, int input) {
        int ceil = -1;
        
        while (root != null) {
            if (root.data == input) {
                return input;  // If input is found in the tree, return it as ceil.
            } else if (root.data < input) {
                root = root.right;  // Move to the right subtree if input is greater than current node's data.
            } else {
                ceil = root.data;   // Mark ceil to be current node's data.
                root = root.left;   // Move to the left subtree to find a closer ceil value.
            }
        }
        
        return ceil;  // Return computed ceil value.
    }
    
    public static void main(String[] args) {
        // Driver Code.
        Node root = new Node(10);
        root.left = new Node(5);
        root.left.left = new Node(4);
        root.left.right = new Node(7);
        root.left.right.right = new Node(8);
        root.right = new Node(11);

        System.out.println(findCeil(root, 6));  // Find and print the ceil of 6 in the BST.
    }
}

Output: 7

Space Complexity: O(1) {As no extra space is being used, we’re just traversing the BST.}

Python Code

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def find_ceil(root, input_val):
    ceil = -1
    
    while root:
        if root.data == input_val:
            return input_val  # If input is found in the tree, return it as ceil.
        elif root.data < input_val:
            root = root.right  # Move to the right subtree if input is greater than current node's data.
        else:
            ceil = root.data   # Mark ceil to be current node's data.
            root = root.left   # Move to the left subtree to find a closer ceil value.
            
    return ceil  # Return computed ceil value.

if __name__ == "__main__":
    # Driver Code.
    root = Node(10)
    root.left = Node(5)
    root.left.left = Node(4)
    root.left.right = Node(7)
    root.left.right.right = Node(8)
    root.right = Node(11)

    print(find_ceil(root, 6))  # Find and print the ceil of 6 in the BST.

Output: 7

Space Complexity: O(1) {As no extra space is being used, we’re just traversing the BST.}

Javascript Code

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

function findCeil(root, input) {
    let ceil = -1;
    
    while (root !== null) {
        if (root.data === input) {
            return input;  // If input is found in the tree, return it as ceil.
        } else if (root.data < input) {
            root = root.right;  // Move to the right subtree if input is greater than current node's data.
        } else {
            ceil = root.data;   // Mark ceil to be current node's data.
            root = root.left;   // Move to the left subtree to find a closer ceil value.
        }
    }
    
    return ceil;  // Return computed ceil value.
}

// Driver Code
let root = new Node(10);
root.left = new Node(5);
root.left.left = new Node(4);
root.left.right = new Node(7);
root.left.right.right = new Node(8);
root.right = new Node(11);

console.log(findCeil(root, 6));  // Find and print the ceil of 6 in the BST.

Output: 7

Space Complexity: O(1) {As no extra space is being used, we’re just traversing the BST.}

Video Explanation

Special thanks to Priyanshi Goel for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article