{"id":28322,"date":"2017-10-15T18:34:41","date_gmt":"2017-10-15T13:04:41","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=28322"},"modified":"2017-10-15T18:34:41","modified_gmt":"2017-10-15T13:04:41","slug":"java-programming-floor-ceil-bst","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-floor-ceil-bst\/","title":{"rendered":"Java Programming &#8211; Floor and Ceil from a BST"},"content":{"rendered":"<p>There are numerous applications we need to find floor (ceil) value of a key in a binary search tree or sorted array. <span id=\"more-12996\"><\/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<p><em>Ceil Value Node<\/em>: Node with smallest data larger than or equal to key value.<\/p>\n<p>Imagine we are moving down the tree, and assume we are root node. The comparison yields three possibilities,<\/p>\n<p><strong>A)<\/strong> Root data is equal to key. We are done, root data is ceil value.<\/p>\n<p><strong>B)<\/strong> Root data &lt; key value, certainly the ceil value can\u2019t be in left subtree. Proceed to search on right subtree as reduced problem instance.<\/p>\n<p><strong>C)<\/strong> Root data &gt; key value, the ceil value <em>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<p>Here is the code for ceil value.[ad type=&#8221;banner&#8221;]\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java Program<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ Java program to find ceil of a given value in BST<br\/> <br\/>class Node {<br\/> <br\/>    int data;<br\/>    Node left, right;<br\/> <br\/>    Node(int d) {<br\/>        data = d;<br\/>        left = right = null;<br\/>    }<br\/>}<br\/> <br\/>class BinaryTree {<br\/> <br\/>    static Node root;<br\/>     <br\/>    \/\/ Function to find ceil of a given input in BST. If input is more<br\/>    \/\/ than the max key in BST, return -1<br\/>    int Ceil(Node node, int input) {<br\/>         <br\/>        \/\/ Base case<br\/>        if (node == null) {<br\/>            return -1;<br\/>        }<br\/> <br\/>        \/\/ We found equal key<br\/>        if (node.data == input) {<br\/>            return node.data;<br\/>        }<br\/> <br\/>        \/\/ If root&#039;s key is smaller, ceil must be in right subtree<br\/>        if (node.data &lt; input) {<br\/>            return Ceil(node.right, input);<br\/>        }<br\/> <br\/>        \/\/ Else, either left subtree or root has the ceil value<br\/>        int ceil = Ceil(node.left, input);<br\/>        return (ceil &gt;= input) ? ceil : node.data;<br\/>    }<br\/>     <br\/>    \/\/ Driver program to test the above functions<br\/>    public static void main(String[] args) {<br\/>        BinaryTree tree = new BinaryTree();<br\/>        tree.root = new Node(8);<br\/>        tree.root.left = new Node(4);<br\/>        tree.root.right = new Node(12);<br\/>        tree.root.left.left = new Node(2);<br\/>        tree.root.left.right = new Node(6);<br\/>        tree.root.right.left = new Node(10);<br\/>        tree.root.right.right = new Node(14);<br\/>        for (int i = 0; i &lt; 16; i++) {<br\/>            System.out.println(i + &quot; &quot; + tree.Ceil(root, i));<br\/>        }<br\/>    }<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>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=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Floor and Ceil from a BST &#8211; Binary Search Tree &#8211; 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":[82776,82775,82772,82773,82774,82770,82771,82769],"class_list":["post-28322","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","tag-convert-double-to-int-in-java","tag-double-to-int-in-java","tag-java-floor-int","tag-java-math-ceil-int","tag-java-math-ceil-integer","tag-math-floor-in-java","tag-math-rint-in-java","tag-round-function-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28322","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=28322"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28322\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=28322"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=28322"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=28322"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}