Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/53236a7f96390cf27e3b39b0ec2e0d30 to your computer and use it in GitHub Desktop.
Save jianminchen/53236a7f96390cf27e3b39b0ec2e0d30 to your computer and use it in GitHub Desktop.
Leetcode 333 - biggest binary search tree - peer performed very well
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.
Note:
A subtree must include all of its descendants.
Here's an example:
10
/ \
5 15
/ \ \
1 8 7
The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree's size, which is 3.
Hint:
You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.
Follow up:
Can you figure out ways to solve it with O(n) time complexity?
class Node{
boolean isBST;
int size;
int min, max;
public Node(){
isBST=true
size=0;
}
}
10
/ \
5 15
/ \ \
1 8 7
n n
1 -> Node() min=INteger.MIN_VALUE, max=1, size 1
8 -> min=Integer.MIN_VALUE, max=1, size 1
//https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/LargestBSTInBinaryTree.java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// https://www.youtube.com/watch?v=4fiDs7CCxkc
class Node{
int min, max, size;
boolean isBST;
public Node(){
min=Integer.MAX_VALUE;
max=Integer.MIN_VALUE;
isBST=true;
size=0;
}
}
public int largestBSTSubtree(TreeNode root) {
Node r=get(root);
return r.size;
}
//bc
if root is null
return new Node();
Node left=get(root.left)
if(leftisbst or rightisbst)
root val
< <
left val max right val min
left size + right size +1
else
math left size, right size
https://www.youtube.com/watch?v=4fiDs7CCxkc
public Node get(TreeNode root) {
//bc
if(root==null){
return new Node();
}
//post order because left, right, then root
Node left = get(root.left);
Node right = get(root.right);
Node cur = new Node();
//if either child is not a BST or
//if the left child's max is larger than root or
//if the right child's min is smaller than the root
//it's NOT a BST
if(!left.isBST ||
!right.isBST ||
left.max >= root.val || right.min <= root.val){
cur.isBST=false;
//get max of right and left size
cur.size = Math.max(left.size, right.size); // ?
return cur;
}
//if it makes it here, then it is a BST
cur.isBST = true;
//size is both children plus this node
cur.size = left.size + right.size + 1;
//if the left child is null, set min to root.val,
//otherwise set it to child's min
cur.min = root.left != null? left.min : root.val;
//if the right child is null, set min to root.val,
//otherwise set it to child's min
cur.max = root.right!= null? right.max : root.val;
return cur;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment