# Find the largest BST subtree in a given Binary Tree

### Find the largest BST subtree in a given Binary Tree

Solution:

• Traverse tree in PostOrder
• Create Node info (isBST, size, min, max)
##### Algorithm:
1. Create a class to hold (isBST, size, min, max) properties for every node
2. Traverse in postOrder
1. If` node is null` then
1. `return null`
2. If `node is leaf `then,
1. `return isBST = true, size = 1, min = node.data, max = node.data`
3. `left = recursively call for node.left`
4. `right = recursively call for node.right`
5. if `left.isBST == true and right.isBST == true and left.min < node.data < right.max` then
1. `return isBST = true, size = 1+ left.size + right.size, min = left.min, max = right.max`
6. else
1. `return isBST = false, size = max (left.size , right.size), min = 0, max = 0`

Latest Source Code:
Github: LargestBSTInBinaryTree.java

Output:

```
25
/ \
/   \
/     \
/       \
/         \
/           \
/             \
/               \
18               50
/ \             / \
/   \           /   \
/     \         /     \
/       \       /       \
19       20       35       60
\     / \     / \     / \
\   /   \   /   \   /   \
15   18   25   20   40   55   70
\
25

Largest BST size: 8
```
Author: