Find the largest BST subtree in a given Binary Tree
Solution:
- Traverse tree in PostOrder
- Create Node info (isBST, size, min, max)
Algorithm:
- Create a class to hold (isBST, size, min, max) properties for every node
- Traverse in postOrder
- If
node is null
thenreturn null
- If
node is leaf
then,return isBST = true, size = 1, min = node.data, max = node.data
left = recursively call for node.left
right = recursively call for node.right
- if
left.isBST == true and right.isBST == true and left.min < node.data < right.max
thenreturn isBST = true, size = 1+ left.size + right.size, min = left.min, max = right.max
- else
return isBST = false, size = max (left.size , right.size), min = 0, max = 0
- If
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