How to Find the Largest BST in BT

In this problem, we are given a Binary Tree. We have to find a subtree of this given binary tree, which also satisfies the requirements to be classified as a binary search tree. At last, we have to return the size of the binary search tree subtree of the given binary tree. We define the size of the subtree as the total number of nodes in that tree. Let us see some illustrations to visualize the problem.

Examples:

Input:

Output:

 5 

Explanation: The complete tree is a binary search tree. Hence, the size of the binary search subtree is 5.

Input:

Output:

 3 

The binary search subtree in this problem is:

Hence, the size of the subtree is 3.

Approach - 1

In this approach, we will check if the subtree is a binary search tree or not using the min value and max value technique. The condition of a complete tree to be a binary search tree is that the root node value of the tree should have a greater value than the largest node value of the left subtree, and the root node should have a smaller value than the minimum node value of the right subtree.

We will traverse the tree in the bottom-up direction. For each node traversed, we will store the minimum and maximum values for the subtree of the current root node. If the current node follows the properties discussed above, then the current subtree is a binary search tree. We will update the size of the binary search tree. Following these steps, we will return the size of the largest binary search tree subtree in the end.

Below is the implementation of this approach.

Code

Output:

 Tree - 1 The size of the largest BST subtree is 3 Tree - 2 The size of the largest BST subtree is 5 

Time Complexity: In this program, we are using the DFS search to traverse the binary tree; therefore, the time complexity will be O(n)

Space complexity: We have used space to store the recursion stack. The space complexity due to the recursion stack is O(n).