{"id":28316,"date":"2017-10-15T18:22:55","date_gmt":"2017-10-15T12:52:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=28316"},"modified":"2017-10-15T18:22:55","modified_gmt":"2017-10-15T12:52:55","slug":"c-programming-floor-ceil-bst","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-floor-ceil-bst\/","title":{"rendered":"C Programming – Floor and Ceil from a BST"},"content":{"rendered":"

There are numerous applications we need to find floor (ceil) value of a key in a binary search tree or sorted array. <\/span>For example, consider designing memory\u00a0management system in which free nodes are arranged in BST. Find best fit for the input request.<\/p>\n

Ceil Value Node<\/em>: Node with smallest data larger than or equal to key value.<\/p>\n

Imagine we are moving down the tree, and assume we are root node. The comparison yields three possibilities,<\/p>\n

A)<\/strong> Root data is equal to key. We are done, root data is ceil value.<\/p>\n

B)<\/strong> Root data < key value, certainly the ceil value can\u2019t be in left subtree. Proceed to search on right subtree as reduced problem instance.<\/p>\n

C)<\/strong> Root data > key value, the ceil value may be<\/em> 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.<\/p>\n

Here is the code for ceil value.[ad type=”banner”]\n

C Program<\/span> <\/div> 
\/\/ Program to find ceil of a given value in BST#include <stdio.h>#include <stdlib.h> \/* A binary tree node has key, left child and right child *\/struct node{    int key;    struct node* left;    struct node* right;}; \/* Helper function that allocates a new node with the given key and   NULL left and right  pointers.*\/struct node* newNode(int key){    struct node* node = (struct node*)malloc(sizeof(struct node));    node->key = key;    node->left = NULL;    node->right = NULL;    return(node);} \/\/ Function to find ceil of a given input in BST. If input is more\/\/ than the max key in BST, return -1int 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;} \/\/ Driver program to test above functionint main(){    node *root = newNode(8);     root->left = newNode(4);    root->right = newNode(12);     root->left->left = newNode(2);    root->left->right = newNode(6);     root->right->left = newNode(10);    root->right->right = newNode(14);     for(int i = 0; i < 16; i++)        printf("%d  %d\\n", i, Ceil(root, i));     return 0;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
0  2\r\n1  2\r\n2  2\r\n3  4\r\n4  4\r\n5  6\r\n6  6\r\n7  8\r\n8  8\r\n9  10\r\n10  10\r\n11  12\r\n12  12\r\n13  14\r\n14  14\r\n15  -1<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Floor and Ceil from a BST – Binary Search Tree -There are numerous applications we need to find floor (ceil) value of a key in a binary search tree <\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126],"tags":[82762,82768,82766,82764,82763,82765,82767],"class_list":["post-28316","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","tag-ceil-and-floor-in-c-language","tag-ceil-function-in-c","tag-ceil-in-c","tag-floor-function-in-c","tag-roundup-function-in-c","tag-undefined-reference-to-ceil","tag-undefined-reference-to-floor"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28316","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=28316"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28316\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=28316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=28316"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=28316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}