142. Largest BST in Binary Tree

Given a root of Binary Tree, where the nodes have integer values. Return the size of the largest subtree of the binary tree which is also a BST.

A binary search tree (BST) is a binary tree data structure which has the following properties.

  • The left subtree of a node contains only nodes with data less than the node’s data.
  • The right subtree of a node contains only nodes with data greater than the node’s data.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

Input : root = [2, 1, 3]

Output : 3

Explanation :

The given complete binary tree is a BST consisting of 3 nodes.

Example 2:

Input : root = [10, null, 20, null, 30, null, 40, null, 50]

Output : 5

Explanation :

If we consider the node 10 as root node then it forms the largest BST.

Now Your Turn!

Pick the correct output for the given input

Input : root = [3, 1, 4, null, null, 2]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= Number of Nodes <= 104
  • 1 <= Node.val <= 105

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
 
class Solution{
public:
int largestBST(TreeNode* root){
//your code goes here
}
};
Test Case

Input:

Root
to save your code