{"id":27565,"date":"2018-04-04T19:35:50","date_gmt":"2018-04-04T14:05:50","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27565"},"modified":"2018-04-04T19:35:50","modified_gmt":"2018-04-04T14:05:50","slug":"c-program-find-largest-bst-subtree-given-binary-tree","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-program-find-largest-bst-subtree-given-binary-tree\/","title":{"rendered":"C Program-Find the largest BST subtree in a given Binary Tree"},"content":{"rendered":"<p>Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree.<span id=\"more-7291\"><\/span><\/p>\n<p>Examples:<\/p>\n<pre>Input: \r\n      5\r\n    \/  \\\r\n   2    4\r\n \/  \\\r\n1    3\r\n\r\nOutput: 3 \r\nThe following subtree is the maximum size BST subtree \r\n   2  \r\n \/  \\\r\n1    3\r\n\r\n\r\nInput: \r\n       50\r\n     \/    \\\r\n  30       60\r\n \/  \\     \/  \\ \r\n5   20   45    70\r\n              \/  \\\r\n            65    80\r\nOutput: 5\r\nThe following subtree is the maximum size BST subtree \r\n      60\r\n     \/  \\ \r\n   45    70\r\n        \/  \\\r\n      65    80\r\n<\/pre>\n<div id=\"practice\">\n<h4 id=\"recommended-please-solve-it-on-practice-first-before-moving-on-to-the-solution\"><a href=\"http:\/\/practice.geeksforgeeks.org\/problems\/largest-bst\/1\">Recommended: Please solve it on \u201c<b><i><u>PRACTICE<\/u><\/i><\/b>\u201d first, before moving on to the solution.<\/a><\/h4>\n<\/div>\n<p><strong>Method 1 (Simple but inefficient)<\/strong><br \/>\nStart from root and do an inorder traversal of the tree. For each node N, check whether the subtree rooted with N is BST or not. If BST, then return size of the subtree rooted with N. Else, recur down the left and right subtrees and return the maximum of values returned by left and right subtrees.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20%0A%20%20See%20http%3A%2F%2Fwww.geeksforgeeks.org%2Farchives%2F632%20for%20implementation%20of%20size()%0A%20%0A%20%20See%20Method%203%20of%20http%3A%2F%2Fwww.geeksforgeeks.org%2Farchives%2F3042%20for%0A%20%20implementation%20of%20isBST()%20%0A%20%0A%20%20max()%20returns%20maximum%20of%20two%20integers%20%0A*%2F%20%20%0Aint%20largestBST(struct%20node%20*root)%0A%7B%0A%20%20%20if%20(isBST(root))%0A%20%20%20%20%20return%20size(root)%3B%20%0A%20%20%20else%0A%20%20%20%20return%20max(largestBST(root-%3Eleft)%2C%20largestBST(root-%3Eright))%3B%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<div>\n<p>Time Complexity: The worst case time complexity of this method will be O(n^2). Consider a skewed tree for worst case analysis.<\/p>\n<p><strong>Method 2 (Tricky and Efficient)<\/strong><br \/>\nIn method 1, we traverse the tree in top down manner and do BST test for every node. If we traverse the tree in bottom up manner, then we can pass information about subtrees to the parent. The passed information can be used by the parent to do BST test (for parent node) only in constant time (or O(1) time). A left subtree need to tell the parent whether it is BST or not and also need to pass maximum value in it. So that we can compare the maximum value with the parent\u2019s data to check the BST property. Similarly, the right subtree need to pass the minimum value up the tree. The subtrees need to pass the following information up the tree for the finding the largest BST.<br \/>\n<strong>1)<\/strong> Whether the subtree itself is BST or not (In the following code, is_bst_ref is used for this purpose)<br \/>\n<strong>2)<\/strong> If the subtree is left subtree of its parent, then maximum value in it. And if it is right subtree then minimum value in it.<br \/>\n<strong>3)<\/strong> Size of this subtree if this subtree is BST (In the following code, return value of largestBSTtil() is used for this purpose)<\/p>\n<p>max_ref is used for passing the maximum value up the tree and min_ptr is used for passing minimum value up the tree.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%23include%20%3Climits.h%3E%0A%20%0A%2F*%20A%20binary%20tree%20node%20has%20data%2C%20pointer%20to%20left%20child%0A%20%20%20and%20a%20pointer%20to%20right%20child%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20left%3B%0A%20%20%20%20struct%20node*%20right%3B%0A%7D%3B%0A%20%0A%2F*%20Helper%20function%20that%20allocates%20a%20new%20node%20with%20the%0A%20%20%20given%20data%20and%20NULL%20left%20and%20right%20pointers.%20*%2F%0Astruct%20node*%20newNode(int%20data)%0A%7B%0A%20%20struct%20node*%20node%20%3D%20(struct%20node*)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20malloc(sizeof(struct%20node))%3B%0A%20%20node-%3Edata%20%3D%20data%3B%0A%20%20node-%3Eleft%20%3D%20NULL%3B%0A%20%20node-%3Eright%20%3D%20NULL%3B%0A%20%0A%20%20return(node)%3B%0A%7D%0A%20%0Aint%20largestBSTUtil(struct%20node*%20node%2C%20int%20*min_ref%2C%20int%20*max_ref%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20*max_size_ref%2C%20bool%20*is_bst_ref)%3B%0A%20%0A%2F*%20Returns%20size%20of%20the%20largest%20BST%20subtree%20in%20a%20Binary%20Tree%0A%20%20(efficient%20version).%20*%2F%0Aint%20largestBST(struct%20node*%20node)%0A%7B%0A%20%20%2F%2F%20Set%20the%20initial%20values%20for%20calling%20largestBSTUtil()%0A%20%20int%20min%20%3D%20INT_MAX%3B%20%20%2F%2F%20For%20minimum%20value%20in%20right%20subtree%0A%20%20int%20max%20%3D%20INT_MIN%3B%20%20%2F%2F%20For%20maximum%20value%20in%20left%20subtree%0A%20%0A%20%20int%20max_size%20%3D%200%3B%20%20%2F%2F%20For%20size%20of%20the%20largest%20BST%0A%20%20bool%20is_bst%20%3D%200%3B%0A%20%0A%20%20largestBSTUtil(node%2C%20%26min%2C%20%26max%2C%20%26max_size%2C%20%26is_bst)%3B%0A%20%0A%20%20return%20max_size%3B%0A%7D%0A%20%0A%2F*%20largestBSTUtil()%20updates%20*max_size_ref%20for%20the%20size%20of%20the%20largest%20BST%0A%20%20%20subtree.%20%20%20Also%2C%20if%20the%20tree%20rooted%20with%20node%20is%20non-empty%20and%20a%20BST%2C%0A%20%20%20then%20returns%20size%20of%20the%20tree.%20Otherwise%20returns%200.*%2F%0Aint%20largestBSTUtil(struct%20node*%20node%2C%20int%20*min_ref%2C%20int%20*max_ref%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20*max_size_ref%2C%20bool%20*is_bst_ref)%0A%7B%0A%20%0A%20%20%2F*%20Base%20Case%20*%2F%0A%20%20if%20(node%20%3D%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20%20*is_bst_ref%20%3D%201%3B%20%2F%2F%20An%20empty%20tree%20is%20BST%0A%20%20%20%20%20return%200%3B%20%20%20%20%2F%2F%20Size%20of%20the%20BST%20is%200%0A%20%20%7D%0A%20%0A%20%20int%20min%20%3D%20INT_MAX%3B%0A%20%0A%20%20%2F*%20A%20flag%20variable%20for%20left%20subtree%20property%0A%20%20%20%20%20i.e.%2C%20max(root-%3Eleft)%20%3C%20root-%3Edata%20*%2F%0A%20%20bool%20left_flag%20%3D%20false%3B%0A%20%0A%20%20%2F*%20A%20flag%20variable%20for%20right%20subtree%20property%0A%20%20%20%20%20i.e.%2C%20min(root-%3Eright)%20%3E%20root-%3Edata%20*%2F%0A%20%20bool%20right_flag%20%3D%20false%3B%0A%20%0A%20%20int%20ls%2C%20rs%3B%20%2F%2F%20To%20store%20sizes%20of%20left%20and%20right%20subtrees%0A%20%0A%20%20%2F*%20Following%20tasks%20are%20done%20by%20recursive%20call%20for%20left%20subtree%0A%20%20%20%20a)%20Get%20the%20maximum%20value%20in%20left%20subtree%20(Stored%20in%20*max_ref)%0A%20%20%20%20b)%20Check%20whether%20Left%20Subtree%20is%20BST%20or%20not%20(Stored%20in%20*is_bst_ref)%0A%20%20%20%20c)%20Get%20the%20size%20of%20maximum%20size%20BST%20in%20left%20subtree%20(updates%20*max_size)%20*%2F%0A%20%20*max_ref%20%3D%20INT_MIN%3B%0A%20%20ls%20%3D%20largestBSTUtil(node-%3Eleft%2C%20min_ref%2C%20max_ref%2C%20max_size_ref%2C%20is_bst_ref)%3B%0A%20%20if%20(*is_bst_ref%20%3D%3D%201%20%26%26%20node-%3Edata%20%3E%20*max_ref)%0A%20%20%20%20%20left_flag%20%3D%20true%3B%0A%20%0A%20%20%2F*%20Before%20updating%20*min_ref%2C%20store%20the%20min%20value%20in%20left%20subtree.%20So%20that%20we%0A%20%20%20%20%20have%20the%20correct%20minimum%20value%20for%20this%20subtree%20*%2F%0A%20%20min%20%3D%20*min_ref%3B%0A%20%0A%20%20%2F*%20The%20following%20recursive%20call%20does%20similar%20(similar%20to%20left%20subtree)%20%0A%20%20%20%20task%20for%20right%20subtree%20*%2F%0A%20%20*min_ref%20%3D%20%20INT_MAX%3B%0A%20%20rs%20%3D%20largestBSTUtil(node-%3Eright%2C%20min_ref%2C%20max_ref%2C%20max_size_ref%2C%20is_bst_ref)%3B%0A%20%20if%20(*is_bst_ref%20%3D%3D%201%20%26%26%20node-%3Edata%20%3C%20*min_ref)%0A%20%20%20%20%20right_flag%20%3D%20true%3B%0A%20%0A%20%20%2F%2F%20Update%20min%20and%20max%20values%20for%20the%20parent%20recursive%20calls%0A%20%20if%20(min%20%3C%20*min_ref)%0A%20%20%20%20%20*min_ref%20%3D%20min%3B%0A%20%20if%20(node-%3Edata%20%3C%20*min_ref)%20%2F%2F%20For%20leaf%20nodes%0A%20%20%20%20%20*min_ref%20%3D%20node-%3Edata%3B%0A%20%20if%20(node-%3Edata%20%3E%20*max_ref)%0A%20%20%20%20%20*max_ref%20%3D%20node-%3Edata%3B%0A%20%0A%20%20%2F*%20If%20both%20left%20and%20right%20subtrees%20are%20BST.%20And%20left%20and%20right%0A%20%20%20%20%20subtree%20properties%20hold%20for%20this%20node%2C%20then%20this%20tree%20is%20BST.%0A%20%20%20%20%20So%20return%20the%20size%20of%20this%20tree%20*%2F%0A%20%20if(left_flag%20%26%26%20right_flag)%0A%20%20%7B%0A%20%20%20%20%20if%20(ls%20%2B%20rs%20%2B%201%20%3E%20*max_size_ref)%0A%20%20%20%20%20%20%20%20%20*max_size_ref%20%3D%20ls%20%2B%20rs%20%2B%201%3B%0A%20%20%20%20%20return%20ls%20%2B%20rs%20%2B%201%3B%0A%20%20%7D%0A%20%20else%0A%20%20%7B%0A%20%20%20%20%2F%2FSince%20this%20subtree%20is%20not%20BST%2C%20set%20is_bst%20flag%20for%20parent%20calls%0A%20%20%20%20%20*is_bst_ref%20%3D%200%3B%20%0A%20%20%20%20%20return%200%3B%0A%20%20%7D%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Let%20us%20construct%20the%20following%20Tree%0A%20%20%20%20%20%20%20%20%20%2050%0A%20%20%20%20%20%20%20%2F%20%20%20%20%20%20%5C%0A%20%20%20%20%2010%20%20%20%20%20%20%20%2060%0A%20%20%20%20%2F%20%20%5C%20%20%20%20%20%20%20%2F%20%20%5C%0A%20%20%205%20%20%2020%20%20%20%2055%20%20%20%2070%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%2F%20%20%5C%0A%20%20%20%20%20%20%20%20%20%2045%20%20%20%20%2065%20%20%20%2080%0A%20%20*%2F%0A%20%0A%20%20struct%20node%20*root%20%3D%20newNode(50)%3B%0A%20%20root-%3Eleft%20%20%20%20%20%20%20%20%3D%20newNode(10)%3B%0A%20%20root-%3Eright%20%20%20%20%20%20%20%3D%20newNode(60)%3B%0A%20%20root-%3Eleft-%3Eleft%20%20%3D%20newNode(5)%3B%0A%20%20root-%3Eleft-%3Eright%20%3D%20newNode(20)%3B%0A%20%20root-%3Eright-%3Eleft%20%20%3D%20newNode(55)%3B%0A%20%20root-%3Eright-%3Eleft-%3Eleft%20%20%3D%20newNode(45)%3B%0A%20%20root-%3Eright-%3Eright%20%3D%20newNode(70)%3B%0A%20%20root-%3Eright-%3Eright-%3Eleft%20%3D%20newNode(65)%3B%0A%20%20root-%3Eright-%3Eright-%3Eright%20%3D%20newNode(80)%3B%0A%20%0A%20%20%2F*%20The%20complete%20tree%20is%20not%20BST%20as%2045%20is%20in%20right%20subtree%20of%2050.%0A%20%20%20%20%20The%20following%20subtree%20is%20the%20largest%20BST%0A%20%20%20%20%20%20%20%2060%0A%20%20%20%20%20%20%2F%20%20%5C%0A%20%20%20%2055%20%20%20%2070%0A%20%20%20%2F%20%20%20%20%20%2F%20%20%5C%0A%2045%20%20%20%20%2065%20%20%20%2080%0A%20%20*%2F%0A%20%20printf(%22%20Size%20of%20the%20largest%20BST%20is%20%25d%22%2C%20largestBST(root))%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<p><strong>Time Complexity:<\/strong> O(n) where n is the number of nodes in the given Binary Tree.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126],"tags":[70276,70669,81872,70712,81868,81864,81871,73310,80557,81878,80553,81865,81876,81869,81862,81866,81867,81863,81875,81860,81877,81874,81859,81873,81861,81870],"class_list":["post-27565","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","tag-algorithm-for-binary-search","tag-binary-search-tree-applications","tag-binary-search-tree-c-code","tag-binary-search-tree-complexity","tag-binary-search-tree-deletion-algorithm-in-data-structure","tag-binary-search-tree-insertion-algorithm","tag-binary-search-tree-insertion-example","tag-binary-search-tree-program-in-c","tag-binary-search-tree-with-example","tag-binary-tree-delete","tag-binary-tree-in-java","tag-binary-tree-remove-node","tag-bst-traversal","tag-build-binary-search-tree","tag-c-programming-examples-on-trees","tag-delete-node-in-bst","tag-deletion-in-binary-tree","tag-explain-binary-search-tree","tag-explain-binary-search-tree-with-example","tag-finding-the-largest-subtree-in-a-bst","tag-height-of-binary-tree","tag-implement-binary-search-tree-in-java","tag-iteratively-find-the-size-of-largest-bst-subtree-in-a-given","tag-java-binary-search-tree-code","tag-largest-bst-in-a-binary-tree","tag-search-bst"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27565","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=27565"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27565\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27565"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27565"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27565"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}