333. Largest BST Subtree
Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST),
where the largest means subtree has the largest number of nodes.
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:
The left subtree values are less than the value of their parent (root) node's value.
The right subtree values are greater than the value of their parent (root) node's value.
Note: A subtree must include all of its descendants.
Example 1:
Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree's size, which is 3.
Example 2:
Input: root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
Output: 2
Constraints:
The number of nodes in the tree is in the range [0, 104].
-104 ≤ Node.val ≤ 104
Overview:-
We need to find the largest subtree which is also a Binary Search Tree (BST),
where the largest means subtree has the maximum number of nodes.
Binary Search Tree is a binary tree data structure in which all of its nodes have the following properties:
The left subtree of a node contains only nodes with values less than the node’s value.
The right subtree of a node contains only nodes with values greater than the node’s value.
The left and right subtree of each node in a BST should also be binary search trees.
While this property is not directly stated in the problem description,
it can be inferred since all nodes must have the above two properties.
If you are unfamiliar with binary search trees, we encourage you to check out our BST Explore Card.
We have also included a few similar practice problems that you can try:
Validate Binary Search Tree
Binary Tree Preorder Traversal
Binary Tree Postorder Traversal
House Robber III: Approach 1: Pre-Order Traversal
We need to find the largest BST of the given tree.
The root of the largest BST could be any node in the given tree.
Hence we can think of traversing each node of the given tree and check if the subtree rooted at the current node is a BST or not.
If it is a valid BST, we can count the nodes in this tree and update the answer.
Otherwise, we will search for the largest BST in the left and right subtrees.
This approach is suboptimal and might result in time limit exceeded (TLE).
However, it is presented here for learning purposes.
It explains a few methods that solve classic problems related to binary trees,
such as counting the number of nodes and finding the maximum and minimum valued nodes in subtrees.
As such, the intention of this approach is to provide a better foundation for understanding the subsequent approaches.
Note that the efficiency of this approach could be improved by caching the results for each of the operations listed below.
However, this optimization is not implemented here because this approach is only intended to be used as a stepping stone to help us understand the subsequent optimized solutions.
How to check if a binary tree is a Binary Search Tree ?
We can create a function isValidBST which will return True if the subtree rooted at the current node is a valid BST.
At each node of the tree:
The left subtree of a node contains only nodes with values less than the current node’s value.
We can call a findMax function which will explore all of the nodes in the left subtree and return the maximum node value.
If the max value is less than the current node value it means all nodes in the left subtree have a smaller value than the current node.
The right subtree of a node contains only nodes with values greater than the current node’s value.
We can call a findMin function which will explore all of the nodes in the right subtree and return the minimum node value.
If the min value is more than the current node's value it means all nodes in the right subtree have greater value than the current node.
The left and right subtree of a node must also be a binary search tree.
To check this condition we can recursively call this isValidBST function on the left child and the right child of the current node.
If all these three conditions are true then the subtree rooted at the current node is also a Binary Search Tree.
Approach 1:
isValidBST root:
// An empty tree is a valid Binary Search Tree.
if root is NULL
return True
leftMax = max node value in root's left subtree
if leftMax >= root's value
return False
rightMin = min node value in root's right subtree
if rightMin <= root's value
return False
if root's left and root's right subtree are BST
return True
return False
How to find min / max node value in a binary tree?
We can create a function findMax which will return the max node value in the subtree rooted at the current node.
Recursively get max value from the left and right subtrees of the current node.
The max node of the current subtree will be the max value from left subtree max value, right subtree max value, or current node value.
We can use a similar process to get the minimum node value.
findMax in root:
// Max node in an empty tree should be smaller than parent.
if root is NULL
return INT_MIN (Max node is smallest possible value)
maxValue = max of root's value and root's left subtree and root's right subtree
return maxValue
findMin in root:
// Min node in an empty tree should be larger than parent.
if root is NULL
return INT_MAX (Min node is largest possible value)
minValue = min of root's value and root's left subtree and root's right subtree
return minValue
How to count nodes in a given binary tree?
We can create a function countNodes which will return the number of nodes in the subtree rooted at the current node.
Recursively get the number of nodes in the left and right subtree of the current node.
Then, the total number of nodes in the subtree rooted at the current node will be 1
(for the current node) plus the number of nodes in the left subtree plus the number of nodes in the right subtree.
//countNodes in root:
if root is NULL
return 0 (No nodes in an empty tree)
current size = 1 (for current root) + nodes in root's left subtree + nodes in root's right subtree
return current size
Traverse each node of the given tree one by one.
For each node of the given tree:
Perform the following steps to check if the subtree rooted at the current node is a BST:
For each node in the current tree, find the maximum value in the left subtree of the current node,
and find the minimum value in the right subtree of the current node.
If the current node is greater than the left subtree's max value and smaller than the right subtree's min value
and the left and right subtrees are also BSTs, then return True.
Otherwise, the subtree rooted at the current node is not a BST, so return False.
If it is a BST, then perform the following steps to count the number of nodes in this subtree:
Recursively get the number of nodes in the left and right subtree of the current node.
Return 1 (for the current node) plus the number of nodes in its left subtree plus the number of nodes in its right subtree.
If the tree rooted at the current node is BST, then its subtrees must contain smaller size BSTs.
In this case, return the current BST size as there is no need to check either of the subtrees.
Otherwise, we need to return the maximum size BST found in the left or right subtree of the current node.
Implementation
class Solution {
// Function to check if given tree is a valid Binary Search Tree or not.
private boolean isValidBST(TreeNode root) {
// An empty tree is a valid Binary Search Tree.
if (root == null) {
return true;
}
// Find the max node in the left subtree of current node.
int leftMax = findMax(root.left);
// If the left subtree has a node greater than or equal to the current node,
// then it is not a valid Binary Search Tree.
if (leftMax >= root.val) {
return false;
}
// Find the min node in the right subtree of current node.
int rightMin = findMin(root.right);
// If the right subtree has a value less than or equal to the current node,
// then it is not a valid Binary Search Tree.
if (rightMin <= root.val) {
return false;
}
// If the left and right subtrees of current tree are also valid BST.
// then the whole tree is a BST.
if (isValidBST(root.left) && isValidBST(root.right)) {
return true;
}
return false;
}
private int findMax(TreeNode root) {
// Max node in a empty tree should be smaller than parent.
if (root == null) {
return Integer.MIN_VALUE;
}
// Check the maximum node from the current node, left and right subtree of the current tree
return Math.max(Math.max(root.val, findMax(root.left)), findMax(root.right));
}
private int findMin(TreeNode root) {
// Min node in a empty tree should be larger than parent.
if (root == null) {
return Integer.MAX_VALUE;
}
// Check the minimum node from the current node, left and right subtree of the current tree
return Math.min(Math.min(root.val, findMin(root.left)), findMin(root.right));
}
private int countNodes(TreeNode root) {
// Empty tree has 0 nodes.
if (root == null) {
return 0;
}
// Add nodes in left and right subtree.
// Add 1 and return total size.
return 1 + countNodes(root.left) + countNodes(root.right);
}
public int largestBSTSubtree(TreeNode root) {
if (root == null) {
return 0;
}
// If current subtree is a validBST, its children will have smaller size BST.
if (isValidBST(root)) {
return countNodes(root);
}
// Find BST in left and right subtrees of current nodes.
return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
}
}
Complexity Analysis
Here, N and H are the number of nodes and the max height of the given tree respectively.
Time complexity: 3*O(N^3).
In the isValidBST function, each node of the tree is traversed and at each node,
the max node value is found in each left subtree and min node value is found in each right subtree.
To find the max and min valued nodes we traverse the whole subtrees, which leads to a total of O(N) time for both of the functions.
This is done once for each of the N nodes in the tree, which leads to an overall time of O(N2) to determine if the given tree is a Binary Search Tree.
The countNodes function traverses all of the nodes in the given tree, hence it takes O(N) time.
In the largestBSTSubtree function, we traverse all nodes of the given tree, and for each node, we find if the subtree rooted at the current node is a BST which takes 2*O(N^2) time and if it is a BST we count the nodes in this subtree which takes O(N) time.
Hence, it is 2 + O(N^2 + N) time operation for each tree node.
Thus to check all N nodes, this approach requires 2+ O(N*(N^2 + N)) time.
Space complexity: O(N).
The recursion call stack can take at most O(H) space; in the worst-case scenario, the height of the tree will equal N.
