{"id":27409,"date":"2018-02-03T21:52:20","date_gmt":"2018-02-03T16:22:20","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27409"},"modified":"2018-02-03T21:52:20","modified_gmt":"2018-02-03T16:22:20","slug":"java-program-print-bst-keys-given-range","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-program-print-bst-keys-given-range\/","title":{"rendered":"Java Program Print BST keys in the given range"},"content":{"rendered":"<p>Given two values k1 and k2 (where k1 &lt; k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1&lt;=x&lt;=k2 and x is a key of given BST. Print all the keys in increasing order.<\/p>\n<p>For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.<\/p>\n<p><strong>Algorithm:<\/strong><br \/>\n1) If value of root\u2019s key is greater than k1, then recursively call in left subtree.<br \/>\n2) If value of root\u2019s key is in range, then print the root\u2019s key.<br \/>\n3) If value of root\u2019s key is smaller than k2, then recursively call in right subtree.<\/p>\n<p><strong>Implementation:<\/strong><\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java Programming<\/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 print BST in given range<br\/> <br\/>\/\/ A binary tree node<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\/>    \/* The functions prints all the keys which in the given range [k1..k2].<br\/>     The function assumes than k1 &lt; k2 *\/<br\/>    void Print(Node node, int k1, int k2) {<br\/>         <br\/>        \/* base case *\/<br\/>        if (node == null) {<br\/>            return;<br\/>        }<br\/> <br\/>        \/* Since the desired o\/p is sorted, recurse for left subtree first<br\/>         If root-&gt;data is greater than k1, then only we can get o\/p keys<br\/>         in left subtree *\/<br\/>        if (k1 &lt; node.data) {<br\/>            Print(node.left, k1, k2);<br\/>        }<br\/> <br\/>        \/* if root&#039;s data lies in range, then prints root&#039;s data *\/<br\/>        if (k1 &lt;= node.data &amp;&amp; k2 &gt;= node.data) {<br\/>            System.out.print(node.data + &quot; &quot;);<br\/>        }<br\/> <br\/>        \/* If root-&gt;data is smaller than k2, then only we can get o\/p keys<br\/>         in right subtree *\/<br\/>        if (k2 &gt; node.data) {<br\/>            Print(node.right, k1, k2);<br\/>        }<br\/>    }<br\/>     <br\/> <br\/>    public static void main(String[] args) {<br\/>        BinaryTree tree = new BinaryTree();<br\/>        int k1 = 10, k2 = 25;<br\/>        tree.root = new Node(20);<br\/>        tree.root.left = new Node(8);<br\/>        tree.root.right = new Node(22);<br\/>        tree.root.left.left = new Node(4);<br\/>        tree.root.left.right = new Node(12);<br\/> <br\/>        tree.Print(root, k1, k2);<br\/>    }<br\/>}<br\/> <br\/>\/\/ This code has been contributed by Mayank Jaiswal<\/code><\/pre> <\/div>\n<p><strong>Output:<\/strong><\/p>\n<pre>12 20 22<\/pre>\n<p><strong>Time Complexity:<\/strong> O(n) where n is the total number of keys in tree.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Java Program Print BST keys in the given range &#8211; Binary Search Tree &#8211; Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree.\n<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,80126,1,2139],"tags":[81560,81558,81559,81566,81565,81561,81563,81562,81564],"class_list":["post-27409","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-binary-search-tree","category-coding","category-java","tag-binary-search-tree-print-java","tag-count-bst-nodes-that-lie-in-a-given-range","tag-count-bst-subtrees-that-lie-in-given-range","tag-java-program-print-bst-keys-in-the-given-range","tag-print-a-binary-search-tree-in-sorted-order","tag-print-binary-search-tree-c","tag-remove-bst-keys-outside-the-given-range","tag-search-range-in-binary-search-tree-leetcode","tag-what-is-the-minimum-height-of-binary-tree-with-n-nodes"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27409","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\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27409"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27409\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27409"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27409"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}