Largest Bst Subtree - Leetcode Solution

Problem Statement:

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it among all BST subtrees.

Example:

Input:

         10
       /    \
      5      15
     / \    /  \
    1   8  7    20

Output: 3 (size of the largest BST subtree rooted at 5)

Solution:

We can solve this problem in two steps. At first, we define a recursive function to check if a binary tree is a BST. The second step is to iterate through each node in the tree and determine the size of the largest BST subtree rooted at it.

1. Checking for BST:

We can define a recursive function called isBST(node) which returns whether the given tree is a BST or not. We can define this function as follows:

a. The base case is when the node is null. In this case, the tree is a BST.

b. If the node has no left and right children, it is a BST.

c. If the node has a left child and the value of that child is greater than the value of the node, then it is not a BST.

d. If the node has a right child and the value of that child is smaller than the value of the node, then it is not a BST.

e. If the node has both left and right children, then recursively check that both the left and right subtrees are BSTs and the value of the left child is less than the value of the node and the value of the right child is greater than the value of the node.

Here is the code for checking if a tree is a BST:

bool isBST(TreeNode* root, int min_val, int max_val) { if (!root) // base case return true; if (root->val > min_val && root->val < max_val) // check if current node value is in range return (isBST(root->left, min_val, root->val) && isBST(root->right, root->val, max_val)); // recursively check for left and right subtree else return false; }

2. Finding the largest BST Subtree:

To find the largest BST subtree, we traverse the tree in a post-order manner. At each node, we check if the current subtree is a BST or not. If it is a BST, we calculate the size of the subtree and compare it with the previous maximum size of a BST subtree. If the current size is larger, we update the maximum size.

Here is the code for finding the largest BST subtree:

int largestBSTSubtree(TreeNode* root) { int max_size = 0; // initializing maximum size findLargestBST(root, &max_size); return max_size; }

int findLargestBST(TreeNode* root, int* max_size) { if (!root) return 0; int left_size = findLargestBST(root->left, max_size); // recursive call for left subtree int right_size = findLargestBST(root->right, max_size); // recursive call for right subtree if (isBST(root, INT_MIN, INT_MAX)) { // checking if current subtree is a BST int size = left_size + right_size + 1; // calculating size of current BST subtree if (size > *max_size) // updating maximum size *max_size = size; return size; } return 0; }

Overall time complexity of the algorithm is O(n^2), as for each node we are checking if the corresponding subtree is BST or not, which takes O(n) in worst case if the tree is skewed. However, it can be optimized to O(n) using a more efficient approach.

1