{"id":27408,"date":"2018-02-05T21:44:49","date_gmt":"2018-02-05T16:14:49","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27408"},"modified":"2018-02-05T21:44:49","modified_gmt":"2018-02-05T16:14:49","slug":"c-program-print-bst-keys-given-range","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-program-print-bst-keys-given-range\/","title":{"rendered":"C Program Print BST keys in the given range"},"content":{"rendered":"

Given two values k1 and k2 (where k1 < 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<=x<=k2 and x is a key of given BST. Print all the keys in increasing order.<\/span><\/p>\n

For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.<\/p>\n

Algorithm:<\/strong>
\n1) If value of root\u2019s key is greater than k1, then recursively call in left subtree.
\n2) If value of root\u2019s key is in range, then print the root\u2019s key.
\n3) If value of root\u2019s key is smaller than k2, then recursively call in right subtree.<\/p>\n

Implementation:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%20%0A%2F*%20A%20tree%20node%20structure%20*%2F%0Astruct%20node%0A%7B%0A%20%20int%20data%3B%0A%20%20struct%20node%20*left%3B%0A%20%20struct%20node%20*right%3B%0A%7D%3B%0A%20%0A%2F*%20The%20functions%20prints%20all%20the%20keys%20which%20in%20the%20given%20range%20%5Bk1..k2%5D.%0A%20%20%20%20The%20function%20assumes%20than%20k1%20%3C%20k2%20*%2F%0Avoid%20Print(struct%20node%20*root%2C%20int%20k1%2C%20int%20k2)%0A%7B%0A%20%20%20%2F*%20base%20case%20*%2F%0A%20%20%20if%20(%20NULL%20%3D%3D%20root%20)%0A%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%2F*%20Since%20the%20desired%20o%2Fp%20is%20sorted%2C%20recurse%20for%20left%20subtree%20first%0A%20%20%20%20%20%20If%20root-%3Edata%20is%20greater%20than%20k1%2C%20then%20only%20we%20can%20get%20o%2Fp%20keys%0A%20%20%20%20%20%20in%20left%20subtree%20*%2F%0A%20%20%20if%20(%20k1%20%3C%20root-%3Edata%20)%0A%20%20%20%20%20Print(root-%3Eleft%2C%20k1%2C%20k2)%3B%0A%20%0A%20%20%20%2F*%20if%20root\u2019s%20data%20lies%20in%20range%2C%20then%20prints%20root\u2019s%20data%20*%2F%0A%20%20%20if%20(%20k1%20%3C%3D%20root-%3Edata%20%26%26%20k2%20%3E%3D%20root-%3Edata%20)%0A%20%20%20%20%20printf(%22%25d%20%22%2C%20root-%3Edata%20)%3B%0A%20%0A%20%20%2F*%20If%20root-%3Edata%20is%20smaller%20than%20k2%2C%20then%20only%20we%20can%20get%20o%2Fp%20keys%0A%20%20%20%20%20%20in%20right%20subtree%20*%2F%0A%20%20%20if%20(%20k2%20%3E%20root-%3Edata%20)%0A%20%20%20%20%20Print(root-%3Eright%2C%20k1%2C%20k2)%3B%0A%7D%0A%20%0A%2F*%20Utility%20function%20to%20create%20a%20new%20Binary%20Tree%20node%20*%2F%0Astruct%20node*%20newNode(int%20data)%0A%7B%0A%20%20struct%20node%20*temp%20%3D%20new%20struct%20node%3B%0A%20%20temp-%3Edata%20%3D%20data%3B%0A%20%20temp-%3Eleft%20%3D%20NULL%3B%0A%20%20temp-%3Eright%20%3D%20NULL%3B%0A%20%0A%20%20return%20temp%3B%0A%7D%0A%20%0A%2F*%20Driver%20function%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20struct%20node%20*root%20%3D%20new%20struct%20node%3B%0A%20%20int%20k1%20%3D%2010%2C%20k2%20%3D%2025%3B%0A%20%0A%20%20%2F*%20Constructing%20tree%20given%20in%20the%20above%20figure%20*%2F%0A%20%20root%20%3D%20newNode(20)%3B%0A%20%20root-%3Eleft%20%3D%20newNode(8)%3B%0A%20%20root-%3Eright%20%3D%20newNode(22)%3B%0A%20%20root-%3Eleft-%3Eleft%20%3D%20newNode(4)%3B%0A%20%20root-%3Eleft-%3Eright%20%3D%20newNode(12)%3B%0A%20%0A%20%20Print(root%2C%20k1%2C%20k2)%3B%0A%20%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/strong><\/p>\n

12 20 22<\/pre>\n
Time Complexity:<\/strong> O(n) where n is the total number of keys in tree.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
C Program Print BST keys in the given range – Binary Search Tree – 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,69866,1],"tags":[81560,81569,81568,81558,81559,81565,81561,81563,81562,81564],"class_list":["post-27408","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-binary-search-tree","category-c-programming","category-coding","tag-binary-search-tree-print-java","tag-binary-search-tree-range-count","tag-binary-search-tree-range-query","tag-count-bst-nodes-that-lie-in-a-given-range","tag-count-bst-subtrees-that-lie-in-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\/27408","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=27408"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27408\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27408"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27408"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27408"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}