Floor and Ceil from a BST | GeeksforGeeks
Ceil Value Node: Node with smallest data larger than or equal to key value.
A) Root data is equal to key. We are done, root data is ceil value.
B) Root data < key value, certainly the ceil value can’t be in left subtree. Proceed to search on right subtree as reduced problem instance.
C) Root data > key value, the ceil value may be in left subtree. We may find a node with is larger data than key value in left subtree, if not the root itself will be ceil node.
Read full article from Floor and Ceil from a BST | GeeksforGeeks
Ceil Value Node: Node with smallest data larger than or equal to key value.
A) Root data is equal to key. We are done, root data is ceil value.
B) Root data < key value, certainly the ceil value can’t be in left subtree. Proceed to search on right subtree as reduced problem instance.
C) Root data > key value, the ceil value may be in left subtree. We may find a node with is larger data than key value in left subtree, if not the root itself will be ceil node.
int Ceil(node *root, int input){ // Base case if( root == NULL ) return -1; // We found equal key if( root->key == input ) return root->key; // If root's key is smaller, ceil must be in right subtree if( root->key < input ) return Ceil(root->right, input); // Else, either left subtree or root has the ceil value int ceil = Ceil(root->left, input); return (ceil >= input) ? ceil : root->key;}