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.
Examples:
Input:
5
/ \
2 4
/ \
1 3
Output: 3
The following subtree is the maximum size BST subtree
2
/ \
1 3
Input:
50
/ \
30 60
/ \ / \
5 20 45 70
/ \
65 80
Output: 5
The following subtree is the maximum size BST subtree
60
/ \
45 70
/ \
65 80
Method 1 (Simple but inefficient)
Start 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.
Time Complexity: The worst case time complexity of this method will be O(n^2). Consider a skewed tree for worst case analysis.
Method 2 (Tricky and Efficient)
In 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’s 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.
1) Whether the subtree itself is BST or not (In the following code, is_bst_ref is used for this purpose)
2) 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.
3) Size of this subtree if this subtree is BST (In the following code, return value of largestBSTtil() is used for this purpose)
max_ref is used for passing the maximum value up the tree and min_ptr is used for passing minimum value up the tree.
[pastacode lang=”c” manual=”%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” message=”C Programming” highlight=”” provider=”manual”/]Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.