What is the time complexity of the isBST function?The time complexity of the isBST function is O(N) because we run an inorder traversal inside this function whose time complexity is O(N). What is the time complexity of the size function?The time complexity of the size function is O(N) because we run an inorder traversal inside this function whose time complexity is O(N). For what min and max are used in the isBST function?The min and max specify the range in which the current node’s value should lie to follow the BST property.

How did we come to the optimized approach for the problem of finding the Largest BST subtree?Earlier in approach 1, we traversed from up to down and checked if its subtree is BST or not for each node. But in approach 2, we started from down to up and used information returned by the child to the parent to figure out if the current node subtree is BST or not. How do we determine if the current node subtree is a BST or not?The current node’s value should be greater than the left child’s subtree maximum value and smaller than the right child’s minimum value.

Largest BST subtree in the given Binary Tree

Introduction:

You are given a Binary Tree, and you need to return the size of the largest subtree of the given Binary Tree, which is a BST(Binary Search Tree). If, in any case, your entire Binary Tree is the BST, return the size of the whole Binary Tree.

Let us see a few examples:

INPUT:

OUTPUT: 3

EXPLANATION:

These are the only SubTrees that are BSTs. So, the largest BST subtree among them has size 3. Hence, the output is 3.

INPUT:

OUTPUT: 6

EXPLANATION: Since the entire Binary Tree is the BST. Hence, the largest BST Subtree is of size 6.

Approach 1:

You can run any(inorder, preorder, postorder) traversal on the tree and check if the subtree rooted at your current node is BST or not. In this way, you can find the largest BST subtree size.

Please refer to the below code for the approach mentioned above.

int largestBST(Node root)
{
  if (root == null){
  return 0;
}

  /*

      calling isBST function to check if subtree
rooted at the current node is a BST or not
*/
  if (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE)){

  /*

          calling size function to find the size
of the subtree rooted at the current node
*/
  return size(root);
}

  // return the largest BST subtree size.
  return Math.max(largestBST(root.left), largestBST(root.right));
}
boolean isBST(Node root, int min, int max){
  if(root == null) {

return true;

    }
  boolean left = isBST(root.left, min, Math.min(max, root.data));
  boolean right = isBST(root.right, Math.max(min, root.data), max);

  /*

      If left part or right part
is not BST return false
*/
  if(left == false || right == false) {
  return false;
}

  /*

      If the current node doesn't follow the BST
Property returns false.
*/
  if(root.data <= min || root.data >= max) {
  return false;
}

  return true;
}
static int size(Node root){
  if(root == null) {
  return 0;
}

  return 1 + size(root.left) + size(root.right);
}

Time Complexity: The time complexity for the above code is O(N ^ 2) (where ‘N’ denotes the number of nodes in the given binary tree) because, for each node, we check if the subtree rooted at the current node is BST. We call this function for each node, and ‘isBST()’ runs in O(N) time. Hence, the time complexity is O(N * N). Also time complexity of size() function is O(N).

Space Complexity: We are not using any auxiliary space, but we are using the recursive call stack space of O(N).

Approach 2:

In approach 1, for each node, we checked its subtree for it to be a part of BST. But, what if we iterate from the bottom and return some information to the node to check if the current node subtree is BST or not in constant time(O(1)).

We will start from the leaf nodes, and the information which we would receive from its child would include the following things:-

If the child subtree is BST or not.
Maximum and Minimum value of all the nodes of child subtrees.
Size of child subtree if it is BST else -1.
Maximum answer till the child.

Now, how to check if the current node subtree is BST or not in O(1) time!

You can apply the following checks to check that:-

curNode.data > left.max (left.max: Maximum node value of left subtree)
curNode.data < right.min (right.min: Minimum node value of right subtree)

If the above two conditions satisfy, that means your current node subtree is a BST because a node’s value should be greater than the maximum value of its left child subtree and smaller than the minimum value of its right child subtree.

In this way, you can find the largest BST subtree size.

Please refer to the below code for the approach mentioned above.

class Solution{
  static int largestBstSize(Node root)
{
  return find(root).maxAns;
}
  static retVal find(Node root){
  if(root == null) {
  return new retVal(Integer.MAX_VALUE, Integer.MIN_VALUE, 0, 0);
}

  /*
Calling left and right child
to get the information we needed
for the current node
*/
retVal left = find(root.left);
retVal right = find(root.right);

  /*
Checking if left or right subtree is not
BST, then returning false for a current node, also
*/
  if(left.cans == -1 || right.cans == -1) {
  return new retVal(Integer.MAX_VALUE, Integer.MIN_VALUE, -1, Math.max(left.maxAns, right.maxAns));
}

  /*
Check if the current node is
satisfying the BST property
Or not.
*/
  if(left.max >= root.data || right.min <= root.data) {
  return new retVal(Integer.MAX_VALUE, Integer.MIN_VALUE, -1, Math.max(left.maxAns, right.maxAns));
}

  /*
If the current node subtree is a BST,
calculating the size of the current
Node subtree.
*/
  int curNodeAns = left.cans + right.cans + 1;

  /*
Returning the information for
the current node's parent
*/
  return new retVal(Math.min(left.min, Math.min(root.data, right.min)), Math.max(left.max, Math.max(root.data, right.max)), left.cans + right.cans + 1, curNodeAns);
}
}
class retVal{

  //Minimum value of the current subtree
  int min;

  //Maximum value of the current subtree
  int max;

  //Answer for the current node subtree
  int cans;

  //Overall maximum size BST subtree
  int maxAns;
retVal(int min, int max, int cans, int maxAns){
  this.min = min;
  this.max = max;
  this.cans = cans;
  this.maxAns = maxAns;
}
}

Time complexity: The time complexity for the above code is O(N) because we only traverse the tree once.

Space Complexity: Constant auxiliary space is used. We are just using O(N) recursive call stack space.

FAQ:

Approach1:

What is the time complexity of the isBST function?
The time complexity of the isBST function is O(N) because we run an inorder traversal inside this function whose time complexity is O(N).
What is the time complexity of the size function?
The time complexity of the size function is O(N) because we run an inorder traversal inside this function whose time complexity is O(N).
For what min and max are used in the isBST function?
The min and max specify the range in which the current node’s value should lie to follow the BST property.

Approach 2:

How did we come to the optimized approach for the problem of finding the Largest BST subtree?
Earlier in approach 1, we traversed from up to down and checked if its subtree is BST or not for each node. But in approach 2, we started from down to up and used information returned by the child to the parent to figure out if the current node subtree is BST or not.
How do we determine if the current node subtree is a BST or not?
The current node’s value should be greater than the left child’s subtree maximum value and smaller than the right child’s minimum value.

Key Takeaways:

In this blog, we have covered the following things:

How to find the largest BST subtree size.
We optimized our approach 1 from O(N * N) approach to O(N) approach.

If you want to learn more about Trees and practice some questions requiring you to take your basic knowledge on Trees a notch higher, you can visit our Guided Path for Trees.

Until then, All the best for your future endeavors, and Keep Coding.