Size of the Largest BST in a Binary Tree Editorial

Practice Problem Link: Size of the Largest BST in a Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a binary tree containing one or more BSTs, find the size of the largest BST subtree.

Naive Approach

The simple solution is to check every node from the top if it is BST or not. If BST, then calculate the size of the subtree starting from that node and return it as the answer. Otherwise check the children nodes recursively.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int maxVal (Node* root) {
	int ans = INT_MIN;
	if(root->left != NULL) {
		ans = max(ans, maxVal(root->left));
	}
	ans = max(ans, root->data);
	if(root->right != NULL) {
		ans = max(ans, maxVal(root->right));
	}
	return ans;
}
int minVal (Node* root) {
	int ans = INT_MAX;
	if(root->left != NULL) {
		ans = min(ans, minVal(root->left));
	}
	ans = min(ans, root->data);
	if(root->right != NULL) {
		ans = min(ans, minVal(root->right));
	}
	return ans;
}
bool isBst(Node* root) {
    if (root == NULL) {
		return true;
	}
	if (root->left != NULL && maxVal(root->left) >= root->data) {
		return false;
	}
	if (root->right != NULL && minVal(root->right) <= root->data) {
		return false;
	}
	if (isBst(root->left) == false || isBst(root->right) == false) {
		return false;
	}
	return true;
}
int bstSize;
int getSize(Node* root) {
	if (root == NULL) {
		return 0;
	}
	return 1 + getSize(root->left) + getSize(root->right);
}
int getLargestBstSize(Node* root) {
    if (isBst(root)) {
		bstSize = 0;
		return getSize(root);
	}
	return max(getLargestBstSize(root->left), getLargestBstSize(root->right));
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	int maxVal (Node root) {
		int ans = Integer.MIN_VALUE;
		if(root.left != null) {
			ans = Math.max(ans, maxVal(root.left));
		}
		ans = Math.max(ans, root.data);
		if(root.right != null) {
			ans = Math.max(ans, maxVal(root.right));
		}
		return ans;
	}
	int minVal (Node root) {
		int ans = Integer.MAX_VALUE;
		if(root.left != null) {
			ans = Math.min(ans, minVal(root.left));
		}
		ans = Math.min(ans, root.data);
		if(root.right != null) {
			ans = Math.min(ans, minVal(root.right));
		}
		return ans;
	}
	boolean isBst(Node root) {
	    if (root == null) {
			return true;
		}
		if (root.left != null && maxVal(root.left) >= root.data) {
			return false;
		}
		if (root.right != null && minVal(root.right) <= root.data) {
			return false;
		}
		if (isBst(root.left) == false || isBst(root.right) == false) {
			return false;
		}
		return true;
	}
	int bstSize;
	int getSize(Node root) {
		if (root == null) {
			return 0;
		}
		return 1 + getSize(root.left) + getSize(root.right);
	}
	int getLargestBstSize(Node root) {
	    if (isBst(root)) {
			bstSize = 0;
			return getSize(root);
		}
		return Math.max(getLargestBstSize(root.left), getLargestBstSize(root.right));
	}
}

Optimal Approach

For every node, first check if its subtrees are BST or not recursively. Also, keep the track of the size of the subtree if it is a BST and the maximum and minimum value in the subtree. If both the subtrees are BST and the value of the current node lies in the correct range then update the size of the largest BST as 1 + size of left BST + size of right BST otherwise, update the size of the largest BST as max(size of left BST, size of right BST).

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
void largestBstSize(Node* root, int &maxVal, int &minVal, int &bstSize, bool &isBst) {
	if (root == NULL) {
		isBst = true;
		return;
	}
	bool isLeftBst = false, isRightBst = false;
	int leftSize = 0, rightSize = 0;
	int leftMaxVal = INT_MIN, leftMinVal = INT_MAX, rightMaxVal = INT_MIN, rightMinVal = INT_MAX;
	largestBstSize(root->left, leftMaxVal, leftMinVal, leftSize, isLeftBst);
	largestBstSize(root->right, rightMaxVal, rightMinVal, rightSize, isRightBst);
	maxVal = max(root->data, max(leftMaxVal, rightMaxVal));
	minVal = min(root->data, min(leftMinVal, rightMinVal));
	if (isLeftBst && isRightBst && leftMaxVal < root->data && rightMinVal > root->data) {
		isBst = true;
		bstSize = 1 + leftSize + rightSize;
	} else {
		bstSize = max(leftSize, rightSize);
	}
	return;
}
int getLargestBstSize(Node* root) {
    int maxVal = INT_MIN;
	int minVal = INT_MAX;
	bool isBst = false;
	int bstSize = 0;
	largestBstSize(root, maxVal, minVal, bstSize, isBst);
	return bstSize;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	class Val {
		int size = 0; 
		boolean flag = false;
		int minimum = Integer.MAX_VALUE; 
		int maximum = Integer.MIN_VALUE;
	}
	void largestBstSize(Node root, Val maxVal, Val minVal, Val bstSize, Val isBst) {
		if (root == null) {
			isBst.flag = true;
			return;
		}
		Val isLeftBst = new Val(), isRightBst = new Val();
		Val leftSize = new Val(), rightSize = new Val();
		Val leftMaxVal = new Val(), leftMinVal = new Val(), rightMaxVal = new Val(), rightMinVal = new Val();
		largestBstSize(root.left, leftMaxVal, leftMinVal, leftSize, isLeftBst);
		largestBstSize(root.right, rightMaxVal, rightMinVal, rightSize, isRightBst);
		maxVal.maximum = Math.max(root.data, Math.max(leftMaxVal.maximum, rightMaxVal.maximum));
		minVal.minimum = Math.min(root.data, Math.min(leftMinVal.minimum, rightMinVal.minimum));
		if (isLeftBst.flag && isRightBst.flag && leftMaxVal.maximum < root.data && rightMinVal.minimum > root.data) {
			isBst.flag = true;
			bstSize.size = 1 + leftSize.size + rightSize.size;
		} else {
			bstSize.size = Math.max(leftSize.size, rightSize.size);
		}
		return;
	}
	int getLargestBstSize(Node root) {
		Val maxVal = new Val(), minVal = new Val();
		Val bstSize = new Val(), isBst = new Val();
		largestBstSize(root, maxVal, minVal, bstSize, isBst);
		return bstSize.size;
	}
}