# C Program-Find the largest BST subtree in a given Binary Tree

write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST).

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.

[pastacode lang=”c” manual=”%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” message=”c” highlight=”” provider=”manual”/]

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.

## Binary Search

Binary Search – search and sorting – Search a sorted array by dividing the search interval in half. Begin with an interval covering the whole array.

## C program to check if a binary tree is BST or not

C program to check if a binary tree is BST or not – Binary Search Tree – A binary search tree (BST) is a node based binary tree data structure.

## Inorder Successor in Binary Search Tree

Python Program – In order Successor in Binary Search Tree – Binary Search Tree – In order Successor is NULL for the last node in In order traversal.

## Check if a binary tree is BST or not

Python program to check if a binary tree is BST or not – Data Structure – A binary search tree is a node based binary tree data structure.

## Data Structure for a single resource reservations

Data Structure for a single resource reservations-Binary Search Tree-Every job requires exactly k time units of the machine. The machine can do only one job

## C Program Lowest Common Ancestor in a Binary Search Tree

C Program Lowest Common Ancestor in a Binary Search Tree – Data Structure – write a c program to find the Lowest Common Ancestor (LCA).