हिन्दी flagहिन्दी  
CLOSE

Suggested:

Problem Statement

You are given the root of a Binary Search Tree (BST) and a target integer value X. The task is to find:

  1. Floor: The largest value in the BST that is less than or equal to X. If no such value exists, return -1.
  2. Ceil: The smallest value in the BST that is greater than or equal to X. If no such value exists, return -1.

Examples

Example 1:

Input
Tree:
        8
       / \
      4   12
     / \   / \
    2   6 10  14

X = 5

Output:
Floor = 4
Ceil = 6

Explanation:
The largest value ≤ 5 is 4 (Floor).
The smallest value ≥ 5 is 6 (Ceil).
Example 2:

Input
Tree:
        8
       / \
      4   12
     / \   / \
    2   6 10  14

X = 13

Output:
Floor = 12
Ceil = 14

Explanation:
The largest value ≤ 13 is 12 (Floor).
The smallest value ≥ 13 is 14 (Ceil).
Example 3:

Input
Tree:
        8
       / \
      4   12
     / \   / \
    2   6 10  14

X = 1

Output:
Floor = -1
Ceil = 2

Explanation:
No value in the BST is ≤ 1, so Floor = -1.
The smallest value ≥ 1 is 2 (Ceil).
Example 4:

Input
Tree:
        8
       / \
      4   12
     / \   / \
    2   6 10  14

X = 15

Output:
Floor = 14
Ceil = -1

Explanation:
The largest value ≤ 15 is 14 (Floor).
No value in the BST is ≥ 15, so Ceil = -1.

Different Approaches

1️⃣ Recursive Approach

Intuition:

We navigate the tree recursively using the following rules:

If the current node's value equals X, both the floor and ceil are X.
If X is smaller than the current node's value:
The current node is a candidate for the ceil.
Explore the left subtree for a better (smaller) ceil.
If X is greater than the current node's value:
The current node is a candidate for the floor.
Explore the right subtree for a better (larger) floor.

Approach:

  1. Start from the root.
  2. Traverse the tree recursively to compute the floor and ceil values.
  3. Use helper functions to track the potential candidates for floor and ceil.

Code:

class Solution {
public:
    // Recursive helper function to find floor
    void findFloor(TreeNode* root, int X, int& floor) {
        if (!root) return;

        if (root->data == X) {
            floor = X;
            return;
        }
        if (root->data < X) {
            floor = root->data;
            findFloor(root->right, X, floor);
        } else {
            findFloor(root->left, X, floor);
        }
    }

    // Recursive helper function to find ceil
    void findCeil(TreeNode* root, int X, int& ceil) {
        if (!root) return;

        if (root->data == X) {
            ceil = X;
            return;
        }
        if (root->data > X) {
            ceil = root->data;
            findCeil(root->left, X, ceil);
        } else {
            findCeil(root->right, X, ceil);
        }
    }

    // Main function
    pair<int, int> floorAndCeil(TreeNode* root, int X) {
        int floor = -1, ceil = -1;
        findFloor(root, X, floor);
        findCeil(root, X, ceil);
        return {floor, ceil};
    }
};

Complexity Analysis:

  • Time Complexity: O(h), where h is the height of the BST.
    • Best Case (balanced BST): O(log N).
    • Worst Case (skewed BST): O(N).
  • Space Complexity: O(h), for the recursion stack.

2️⃣ Iterative Approach

Intuition:

Finding the floor value in a Binary Search Tree (BST) involves tracking the largest node value that is smaller than or equal to the given key. The thought process here is to either find the exact key or reach nodes close to the key’s value. During traversal, if the key matches the node’s value, this value is assigned as the floor, and the search concludes. If the key is smaller than the current node’s value, the algorithm moves to the left subtree to find a smaller value. If the key is larger, the algorithm updates the floor with the current node’s value and explores the right subtree for potentially larger values.

Approach:

  1. Initialize a variable floor to -1 to store the floor value initially.
  2. Traverse the Binary Search Tree starting from the root and continue until reaching the end of the tree or finding the key. At each node:
    1. If the key value equals the node’s value, assign it as the floor value and return.
    2. If the key value is greater than the current node’s value, update floor with the current node’s value and move to the right subtree.
    3. If the key value is smaller than the current node’s value, move to the left subtree as the potential floor value should be smaller.
  3. Return the computed floor value if the key is not found in the tree. This floor value represents the largest node value smaller than the key, or -1 if no such value exists in the BST.

Code:

#include <bits/stdc++.h>
using namespace std;

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

class Solution {
public:
    vector<int> floorCeilOfBST(TreeNode* root, int key) {
        // Initialize the floor and ceil values
        int floor = -1;
        int ceil = -1;
        
        // Find the floor value
		// Start from the root of the BST
        TreeNode* current = root;
        while (current) {
			// If the key matches the current node's value
            if (current->data == key) {
				// Set floor to this value
                floor = current->data; 
                break;
			/* If the key is greater than the current node's value
               Update floor to the current node's value 
               If the key is smaller than the current node's value
               Move to the left subtree to find a smaller value */	
            } else if (current->data < key) {
                floor = current->data; 
                current = current->right; 
            } else {
                current = current->left; 
            }
        }
        
        // Find the ceil value

		// Reset current to start from the root again
        current = root;
        while (current) {
			// If the key matches the current node's value
            if (current->data == key) {
				// Set ceil to this value
                ceil = current->data; 
                break;

			/* If the key is smaller than the current node's value
             Update ceil to the current node's value 
             If the key is greater than the current node's value
             Move to the right subtree to find a larger value */ 

            } else if (current->data > key) {
                ceil = current->data;
                current = current->left;
            } else {
                current = current->right; 
            }
        }
        
        // Return the floor and ceil values as a vector
        return {floor, ceil};
    }
};

// Utility function to insert a new node with given key in BST
TreeNode* insert(TreeNode* node, int key) {
    if (node == nullptr) return new TreeNode(key);
    if (key < node->data)
        node->left = insert(node->left, key);
    else if (key > node->data)
        node->right = insert(node->right, key);
    return node;
}

int main() {
    // Create the BST
    TreeNode* root = nullptr;
    root = insert(root, 8);
    insert(root, 4);
    insert(root, 12);
    insert(root, 2);
    insert(root, 6);
    insert(root, 10);
    insert(root, 14);

    // Key value to find floor and ceil for
    int key = 11;

    // Solution instance
    Solution sol;
    vector<int> result = sol.floorCeilOfBST(root, key);

    // Output the floor and ceil values
    cout << "Floor: " << result[0] << ", Ceil: " << result[1] << endl;

    return 0;
}

Complexity Analysis:

  • Time Complexity: O(h) where h is the height of the BST, since we traverse down the tree once for each of the floor and ceil searches.
  • Space Complexity: O(1) as we only use a constant amount of extra space for storing the floor and ceil values.

Your experience on this site will be improved by allowing cookies Cookie Policy