Largest Subtree Which is a Binary Search Tree (BST)
November 18, 2010 in binary tree
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.
In this post, we develop a solution to find the largest BST subtree in a binary tree. Please note that a subtree must include all of its descendants. If you are only interested in the solution of finding the largest BST where it may or may not include all of its descendants, read my next post: Largest Binary Search Tree (BST) in a Binary Tree.
An anonymous reader asked this interesting question, so here you are. Amazon had asked this in technical interviews and it seemed to me that this is not a popular tree question. It is one of the trickier ones, since you are required to combine the idea from this problem: Determine if a Binary Tree is a Binary Search Tree, and also the idea of doing a Depth-first search (DFS).
It’s important that you understand the question correctly. Let’s try an example below. Which is the largest BST subtree?
____10____ / \ __5_ 15_ / \ \ 1 8 7
For most people, there would be two possible interpretations for the term “subtree”.
Is this ( subtree (1) ) the largest BST subtree?
____10____ / \ __5_ 15 -------- subtree (1) / \ 1 8
How about this one ( subtree (2) ) ?
__5_ / \ -------- subtree (2) 1 8
According to Wikipedia, a subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. Therefore, there is no doubt that subtree (2) is the correct answer, as subtree (1) does not include all of its descendants. It is important that you understand the term subtree correctly. If you are not sure, ask the interviewer and you should not make any assumptions.
Naive Approach:
A naive approach is to reuse the solution from Determine if a Binary Tree is a Binary Search Tree. Starting from the root, we process in the order of current node, left child, then right child. For each node, you would call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then we have to continue examining its left and right child. If only one of the subtrees is BST, then we can return that subtree. However, if both left and right subtrees are BSTs, then we have to compare which subtree is larger (has more descendant nodes), then return the larger one.
Assume that we have a complete tree (ie, all leaves are at the same depth) with n nodes, the naive approach’s run time complexity is O(n lg n). The proof is left as an exercise to the reader. 
How about doing an in-order traversal for the binary tree? The longest increasing contiguous sequence must be the largest BST subtree. Try to do an in-order traversal for the example tree above. This approach simply does not work. Period.
A Bottom-up Approach:
The naive approach is using a top-down approach. It is hardly efficient, simply because we are calling isBST() over and over again. Each time isBST() is called, it traverses down to the leaves to verify if the subtree is a BST.
Let’s think from another perspective. Instead of traversing down the tree, why not traverse up the tree using a bottom-up approach? In other words, we verify the deeper nodes before we verify if the above nodes satisfy the BST requirements.
The main reason of doing this is when one of the nodes does not satisfy the BST properties, all subtrees above (which includes this node as well) must also not satisfy the BST requirements.
First, let’s review our definition of a BST. A tree is a BST if the following properties are satisfied:
- Both left and right subtrees of a node are BSTs.
- The node’s value is greater than its left subtree’s maximum.
- The node’s value is less than its right subtree’s minimum.
Using a bottom-up approach, we need to pass some information up the tree. Obviously, we need to pass minimum and maximum values of the subtree as we traverse up the tree, so the above subtrees could be verified for BST’s properties.
As compared to the top-down approach, the bottom-up approach is such an awesome choice because the results for total number of nodes could be passed up the tree. This saves us from recalculating over and over again. The total number of nodes for a subtree is simply the total number of nodes of its left and right subtrees plus one.
Isn’t the bottom-up approach neat? It acts like magic until you understand it, and solves all the problems that the top-down approach has. The run-time complexity for the bottom-up approach is O(n). Beware of this gotcha when you implement the algorithm. Even though a node’s left subtree is not a BST, you must still continue traverse its right subtree as the largest BST subtree might be contained in its right subtree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | // Find the largest BST subtree in a binary tree. // If the subtree is a BST, return total number of nodes. // If the subtree is not a BST, -1 is returned. int findLargestBSTSubtree(BinaryTree *p, int &min, int &max, int &maxNodes, BinaryTree *& largestBST) { if (!p) return 0; bool isBST = true; int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST); int currMin = (leftNodes == 0) ? p->data : min; if (leftNodes == -1 || (leftNodes != 0 && p->data <= max)) isBST = false; int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST); int currMax = (rightNodes == 0) ? p->data : max; if (rightNodes == -1 || (rightNodes != 0 && p->data >= min)) isBST = false; if (isBST) { min = currMin; max = currMax; int totalNodes = leftNodes + rightNodes + 1; if (totalNodes > maxNodes) { maxNodes = totalNodes; largestBST = p; } return totalNodes; } else { return -1; // This subtree is not a BST } } BinaryTree* findLargestBSTSubtree(BinaryTree *root) { BinaryTree *largestBST = NULL; int min, max; int maxNodes = INT_MIN; findLargestBSTSubtree(root, min, max, maxNodes, largestBST); return largestBST; } |
Here is a variant of the largest BST problem. What if we want to find the largest BST in a tree where it may or may not include all of its descendants? Read my next post: Largest Binary Search Tree (BST) in a Binary Tree to find out.
Largest Subtree Which is a Binary Search Tree (BST),
Anonymous said on November 18, 2010
Thank you for the solution. A beautiful one. Will run against few more test cases and get back to you.
Quick Comments:
I think you need to initialize min and max in findLargestBST() to INT_MIN and INT_MAX respectively.
The interviewer was actually posing different variants for this Q.
Let me put them here:
1. What to do to make the "subtree (1)" as your answer? What I mean here is, I need largest BST, not necessarily something which is a subtree sticking to the Wiki Definition.
2. What if there is no restriction for the sub-tree to extend till the leaves [sub-tree => any part of the tree, not as per wiki def again]
Thanks
vitorbal said on November 18, 2010
This is a very good question… the kind of question you are very prone to make some kind of small mistake if you need to write the whole solution on a white board.. :/
1337c0d3r said on November 18, 2010
@Anonymous:
I did not initialize min and max because they will be initialized when it reaches down to the leaf.
In fact, the variant number 1) is easier to solve. Just use the top-down approach and pass the min and max values down the tree. Traverse down the tree as long as including a node doesn't break the BST constraint. Similar to implementing isBST(), pass the min and max values down the tree.
Could you explain a little more on variant 2)? I am not quite sure what you meant. (Did you mean the nodes in the original tree could be connected indirectly (ie, skipping one or more indirect nodes) to form a BST?)
1337c0d3r said on November 18, 2010
@vitorbal:
Yes, especially when bottom-up approach is usually harder than top-down. You need to be careful of tracking how the values are being modified as it traverse up the tree, which could be tricky.
Anonymous said on November 18, 2010
@1337c0d3r
My second variant is not about connecting nodes indirectly, What I mean is, let me tell with example:
a
/ \
b c
/ \ / \
d e f g
/ \
h i
What if my answer can be only the tree with nodes [b,d,e], this is a subtree which doesnt extend till leaves.
Hope you got the idea.
Thanks
1337c0d3r said on November 19, 2010
To me, it seemed that variant 1) is the same as variant 2). Could you give me an example that differentiate variant 1) and variant 2)?
Yuan Jin said on November 20, 2010
hi there, i saw a pretty smart solution this afternoon. take a look http://www.rawkam.com/?p=822
1337c0d3r said on November 20, 2010
@Yuan:
That solution is incorrect. In fact, either one of these are incorrect: maximum increasing contiguous sequence OR maximum increasing subsequence. Try to come up with a counter example.
I just found a better solution which is more elegant using top-down approach. I will give counter examples and post the solution in my next post. Stay tuned.
Anonymous said on November 21, 2010
@Yuan:
That method is correct for the second variant mentioned by Anonymous
1337c0d3r said on November 23, 2010
@Anonymous:
Please read my next post (solution for Anonymous's variant 1) ), I have given a counter example for the maximum increasing contiguous sequence method.
The second variant mentioned by Anonymous is not clear to me, so I can't tell for sure.
Anonymous said on December 6, 2010
I guess this solution can be speed up to lg(n). if a node fails to pass the test w.r.t. left subtree, i.e., isBST = false, there is no need to check the right subtree.
Anonymous said on January 30, 2011
what about this top down approach ?
int max_len = -1;
node *max_node = NULL;
int longestbst(node *root, int min, int max)
{
if(!root)
return 0;
if(root->data < min || root->data > max)
{
longestbst(root,INT_MIN, INT_MAX);
return -1;
}
int llen = longestbst(root->left, min, root->data);
int rlen= longestbst(root->right, root->data +1, max) ;
if(llen == -1 || rlen == -1)
{
return -1;
}
if((llen + rlen +1) > max_len)
{
max_len = llen + rlen +1;
max_node = root;
}
return llen + rlen + 1;
}
Shashank Mani Narayan said on February 17, 2011
you have 2-d array, with m length and n width.
You are also given k, ( k<=n && k<=m ).
Now, select a square of size k, which returns maximum sum.
Algoseekar said on March 6, 2011
@ihas1337 Code ..Awesome man You Doing Excellent Job..My Very Best Wishes to you..Keep Helping Us..One Day I will B like You …thnx a lot
Greed said on March 14, 2011
Hey ihas1337 may i have your gmail id .
Manoj said on March 14, 2011
A nice solution indeed! Most of the ppl give a top down approach which doesn’t work.
SK said on March 31, 2011
For the naive approach:
For each node, you would call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then we have to continue examining its left and right child. If only one of the subtrees is BST, then we can return that subtree.
How do you justify this ? If the number of nodes in left subtree is 5 while the number of nodes in right subtree is 1000, it is highly likely that deep down under the right subtree, there can be a BST with number of nodes > 5. Hence, we can’t return as soon as we find one of the subtrees to be a BST.
peng said on May 11, 2012
The naive approach is obviously not correct, but the idea of using min and max to keep track of the boundary scope of a BST is brilliant.
Adrian M said on April 29, 2011
my Java version:
yifeng said on January 7, 2013
that’s not right for your solution. for BST, the current node’s value must be larger than the max value of left tree and smaller than the min value of right tree. In java, we need some static variables to do that.
aimless said on May 8, 2011
@Elite (1337c0d3r)
I think you need to revisit your proposed solution once, though didn’t try coding and running it, but by seeing the code it seems that after you have checked the condition
if (isBST) {
min = currMin;
max = currMax;
int totalNodes = leftNodes + rightNodes + 1;
if (totalNodes > maxNodes) {
maxNodes = totalNodes;
largestBST = p;
}
return totalNodes;
} else {
return -1; // This subtree is not a BST
}
you ignored the possibility that right or left subtree can still be max BST subtree.
After reading the question, I had thought the solution just by extending your BST checking algo and here is the code, its working fine for me
//====================================================
bool MaxBST(Node *root, int *count, Node **maxNode, int min, int max)
{
if(!root)
{
*count = 0;
*maxNode = root;
return true;
}
Node* leftMax = NULL;
Node* rightMax = NULL;
int leftCount = 0, rightCount = 0;
bool leftIsBST = MaxBST(root->left, &leftCount, &leftMax, min, root->val);
bool rightIsBST = MaxBST(root->right, &rightCount, &rightMax, root->val, max);
if(leftIsBST && rightIsBST && minval && max >=root->val)
{
*count = leftCount + rightCount + 1;
*maxNode = root;
return true;
}
else
{
*maxNode = (leftCount > rightCount) ? leftMax : rightMax;
*count = (leftCount > rightCount) ? leftCount : rightCount;
return false;
}
}
//====================================
call it as
int count = 0; //number of node is max subtree
Node *maxNode = NULL: //max subtree node shall be returned in this variable
MaxBST(root, &count, &maxNode, INT_MIN, INT_MAX)
aimless said on May 8, 2011
if(leftIsBST && rightIsBST && min val && max >= root->va l) //<<< rightCount) ? leftMax : rightMax;
*count = (leftCount > rightCount) ? leftCount : rightCount;
return false;
}
aimless said on May 8, 2011
i think there is some mess up happening and operators are being confused as HTML tags. i tried posting the correction but its more messed up. anyway i hope you got the idea, second “if” condition in my code, checks if value is between MAX and MIN, just like BST checking code.
aimless said on May 10, 2011
found a descent place to paste my code.
http://ideone.com/TyfDs
anonymous said on June 12, 2011
Your code is not CORRECT. Check it with few input at least (before posting it here). For below input, it shows 4 (right subtree of root), where as ans is 6 (left subtree of root)
Tree *root = new Tree(20);
root->left = new Tree(20);
root->right = new Tree(40);
root->left->left = new Tree(10);
root->left->right = new Tree(25);
root->right->left = new Tree(35);
root->right->right = new Tree(50);
root->left->left->left = new Tree(5);
root->left->left->right = new Tree(15);
root->left->right->right = new Tree(28);
root->right->right->left = new Tree(41);
aimless said on June 13, 2011
@anonymous: i am sorry! for your disappointment and i understand it. i react to such situations in almost similar ways and had done that in this forum too. i did check my code (before posting) with some inputs, yet i missed a bug. thanks for pointing out the issue. i have CORRECTED the approach and re-posted it here:
http://ideone.com/cPG29
LOGIC: start building BST bottoms up instead of(unlike my last approach) canceling the one which doesn’t adhere to be a BST based on the limits set by parent nodes.
Following are the inputs i had used to test my old code (http://ideone.com/TyfDs)
INPUT 1:
root = createNode(4);
root->left=createNode(2);
root->left->left=createNode(1);
root->left->right=createNode(3);
root->right=createNode(5);
INPUT2:
root = createNode(10);
root->left=createNode(5);
root->left->left=createNode(1);
root->left->right=createNode(8);
root->right=createNode(15);
root->right->right=createNode(7);
root->left->left->left=createNode(19);
root->right->right->right=createNode(29);
here is my updated code:
http://ideone.com/cPG29
it is checked with above two and a third input mentioned above by @anonymous.
thanks for challenging the code once again!
AA said on December 18, 2011
Still something is missing ..Its not working for this,
root = createNode(20);
root->left = createNode(50);
root->right = createNode(40);
root->left->left = createNode(10);
root->left->right = createNode(25);
root->right->left = createNode(35);
root->right->right = createNode(50);
root->left->left->left = createNode(5);
root->left->left->right = createNode(15);
root->left->right->right = createNode(28);
root->left->right->left = createNode(23);
root->right->right->left = createNode(41);
giving 4 – 40
should be 3 -25
codingC said on May 31, 2011
Hi,
I suspect the naive top-down solution you proposed is not right.
In the case that only one of the subtree is BST, the solution will return the subtree right away. But this is not correct. You still need to traverse the other subtree to find the largest BST subtree. Otherwise, your solution will return the highest BST subtree(with the greatest height), not the largest one.
aimless said on June 13, 2011
@codingC: yes you are correct, you may want to check my reply to anonymous above your current post.
slimboy said on July 8, 2011
hey 1337coder,
I did not understand this part of the code
leftNodes != 0 && p->data <= max
Why does this condition result in isBST becoming false?
Nisarg said on July 16, 2011
I think Min and Max are not getting updated properly..
We should keep track of max from left subtree and min from right subtree. How is this happening in the above code??
Prateek Caire said on August 11, 2012
Yes. Even i think min and max are not getting updated correctly. Possible change in above code is to store min1 and max1 as min and max from left node. And min2 and max2 from right node. Returned min (passed by referenced one) should min = Min(min1, min2). max = Max(max1, max2). rest is correct. great solution..
fzzh24 said on August 8, 2011
For the naive approach, see this counter example
______ 30______
/ \
20 _____60_
/ \ / \
15 25 ___70 ___ 31
/ \
__50__ __90__
/ \ / \
40 60 80 100
/ \ / \
39 83 95 105
fzzh24 said on August 8, 2011
For the naive approach, see this counter example
…………._______30______
………../………………………..\
…..20………………….._____60_
…./…..\………………./…………….\
.15…..25……….___70___……….31
…………………./……………\
…………….__50__………__90__
……………/………..\……./………..\
………….40………..60..80………100
…………./………………….\………./….\
…………39………………..83…..95….105
AA said on December 18, 2011
Original solution does not work for data here..
http://www.ideone.com/GUGiZ
BinaryTree *root = NULL;
root = createNode(20);
root->left = createNode(50);
root->right = createNode(40);
root->left->left = createNode(50);
root->left->right = createNode(25);
root->right->left = createNode(35);
root->right->right = createNode(50);
root->left->left->left = createNode(5);
root->left->left->right = createNode(15);
root->left->right->right = createNode(28);
root->left->right->left = createNode(23);
root->right->right->left = createNode(41);
return root;
should be 25 , 3
gives 40, 4
AA said on December 18, 2011
Works fine.. I was doing wrong calculation..
AA said on December 18, 2011
Works fine.. made tree incorrectly..
swathi said on January 1, 2012
In the else case has to be modified…
——7
—2—10
-3–8
if (isBST)
{
// as it is.. (explained in the above code)
}
else
{
// I think we need to set the min and max to p->data?
min = p->data;
max = p->data;
return -1; // This subtree is not a BST
}
Balaji said on January 25, 2012
Looking at the signature of the method can someone tell me what is the significance of “BinaryTree *& largerstBST”… I thought just a pointer should suffice.. what is with “&*”
int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,
int &maxNodes, BinaryTree *& largestBST)
vk said on March 13, 2012
hey balaji, *&, means reference to a pointer, its like you are passing alias for the pointer variable.
chk out the following link, it has a example also
http://markgodwin.blogspot.com/2009/08/c-reference-to-pointer.html
reader said on March 17, 2012
@1337c0d3r:
Nice solution.
One question. This will always return the left-most node as the largest BST for any input that is not a BST.Is this the desired result for this question?
siva said on May 18, 2012
Here min and max are not updating
Eugene said on May 19, 2012
seems the naive way is not correct, and I can’t get the complexity nlogn either, for complete tree, for every layer the problem size will shrink by half, cuz you can find a full BST in every layer, so it’s actually n+n/2+n/4+n/4+n/8+n/8+…, the result should be n??
Prateek Caire said on August 11, 2012
Slight modification of your code. correcting min , max
Prateek Caire said on August 11, 2012
forgot writing return ts within if(bBST) scope
Cupidvogel said on November 22, 2012
What is meant by this line ?:
if (leftNodes == -1 ||
(leftNodes != 0 && p->data <= max))
isBST = false;
Barney said on February 5, 2013
grunt explanation of why the above code works from basic pseudo code.
#if 0
Logic used:
===========
1. Current node forms a BST if:
a. left subtree is BST or NULL
b. right subtree is BST or NULL
c. root->key > (left subtree).max value
d. root->key < (right subtree).min value
2. Leaf node is treated as a BST of size 1
Leaf node is identified by 2 NULL subtrees.
3. If current node is a BST, pass it up
If not pass up the largest BST between left and right subtree
Data required from each subtree (recursion level):
1. isBST << is the subtree a BST
2. max << max value of the subtree
3. min << min value of the subtree
4. largestbstsize << size of largest BST contained in the subtree
5. largestbst << pointer to largest BST contained in the subtree
6. isNULL << is the subtree a NULL subtree
Data passed to each subtree (recursion level):
1. root < input params
o. => o/p return value right
l. => left
(o.isBST, o.min, o.max, o.largestbstsize, o.largestbst, o.isNULL) returned from LBST() taking (i.root)
{
if NULL == i.root {
o.isNULL = true
o.largestbstsize = 0
return;
} else
o.isNULL = false
l.(isBST, isNULL, max, min, largestbst, largestbstsize) left)
r.(isBST, isNULL, max, min, largestbst, largestbstsize) right)
// Extract Min and Max values
// if left subtree exists, inherit smallest node, else current node is smallest
o.min = (l.isNULL)?i.root->key:l.min
// if right subtree exists, inherit largest node, else current node is largest
o.max = (r.isNULL)?i.root->key:r.max
// set o.isBST
// if we are leaf node mark bst as true
// if left is bst and right is bst and current node is in order
// if left is NULL and right is BST
// if right is NULL and left is BST
if (l.isNULL || (l.isBST && i.root->key > l.max)) &&
(r.isNULL || (r.isBST && i.root->key r.largestbstsize)?l.largestbst:r.largestbst;
}
}
pseudo code optimisation (reducing stack usage):
===============================================
Iteration 1 uses approx 3(l,r,o)*6(struct elems) => 18 state variables per stack level.
Also return stack values => copying entire struct on each return call.
1) iteration1 flow
if root==NULL {
o.isNULL=true;
o.largestbstsize = 0;
return;
}
l.(isBST, isNULL, max, min, largestbst, largestbstsize) left)
r.(isBST, isNULL, max, min, largestbst, largestbstsize) right)
o.min = (l.isNULL)?i.root->key:l.min
o.max = (r.isNULL)?i.root->key:r.max
o.isBST = ((l.isNULL || (l.isBST && i.root->key > l.max)) && (r.isNULL || (r.isBST && i.root->key r.largestbstsize)?l.largestbst:r.largestbst;
}
2) Rearranging statements to resue same variable for left and right
step1: rearrange statements to group “l” and “r”
note
o.isBST = (x && y)?:true:false;
is equivalent to
o.isBST = !(x && y)?:false:true;
is equivalent to
o.isBST = (!x || !y)?:false:true;
is equivalent to
o.isBST = true;
if !x o.isBST = false;
if !y o.isBST = false;
o.isBST = true;
if root==NULL {
o.isNULL=true;
o.largestbstsize = 0;
return;
}
l.(isBST, isNULL, max, min, largestbst, largestbstsize) left)
if !(l.isNULL || (l.isBST && i.root->key > l.max))
o.isBST = false
o.min = (l.isNULL)?i.root->key:l.min
r.(isBST, isNULL, max, min, largestbst, largestbstsize) right)
if !(r.isNULL || (r.isBST && i.root->key key:r.max
if (o.isBST) {
// we are the largest subtree @ this level
o.largestbstsize = l.largestbstsize + r.largestbstsize + 1;
o.largestbst = i.root;
} else {
// pass up the largest subtree so far
o.largestbstsize = max(l.largestbstsize, r.largestbstsize)
o.largestbst = (l.largestbstsize > r.largestbstsize)?l.largestbst:r.largestbst;
}
step2: replace l and r with same variable “lr”
if root==NULL {
o.isNULL=true;
o.largestbstsize = 0;
return;
}
o.isBST = true;
lr.(isBST, isNULL, max, min, largestbst, largestbstsize) left)
if !(lr.isNULL || (lr.isBST && i.root->key > lr.max))
o.isBST = false
o.min = (l.isNULL)?i.root->key:l.min
lr.(isBST, isNULL, max, min, largestbst, largestbstsize) right)
if !(lr.isNULL || (lr.isBST && i.root->key key:lr.max
if (o.isBST) {
// we are the largest subtree @ this level
o.largestbstsize = l.largestbstsize + r.largestbstsize + 1;
o.largestbst = i.root;
} else {
// pass up the largest subtree so far
o.largestbstsize = max(l.largestbstsize, r.largestbstsize)
o.largestbst = (l.largestbstsize > r.largestbstsize)?l.largestbst:r.largestbst;
}
reduced 1*6 elems and added 2 new variables (l_xxx) => reduction of 4.
Total is 14.
3)use global variable (or top of recursion stack variable) to store the largestbst
instead of passing up recursion chain purely via stack variables.
g_largestbst, g_largestbstsize => accumulated across recursions
so we dont need to store largestbst.
and we can replace largestbstsize with just size (of the current tree if BST)
if root==NULL {
o.isNULL=true;
o.size = 0;
return;
}
o.isBST = true;
lr.(isBST, isNULL, max, min, size) left)
lsize = lr.size;
if !(lr.isNULL || (lr.isBST && i.root->key > lr.max))
o.isBST = false
o.min = (l.isNULL)?i.root->key:l.min
lr.(isBST, isNULL, max, min, size) right)
rsize = lr.size;
if !(lr.isNULL || (lr.isBST && i.root->key key:lr.max
if (o.isBST) {
// we are the largest subtree @ this level
o.size = lsize + rsize + 1;
if (g_largestbstsize isNULL && isBST
size == -1 => !isBST
size >= 1 => isBST
we dont have to return isBST.
Please Note
!(lr.isNULL || (lr.isBST && i.root->key key > lr.min)))
if root==NULL {
o.size = 0;
return;
}
isBST = true;
lr.(max, min, size) left)
lsize = lr.size;
if !((lr.size == 0) || ((lr.size>=0) && i.root->key > lr.max))
isBST = false
o.min = (lr.size == 0)?i.root->key:l.min
lr.(max, min, size) right)
rsize = lr.size;
if !((lr.size == 0) || ((lr.size>=0) && i.root->key key:lr.max
if (isBST) {
// we are the largest subtree @ this level
o.size = lsize + rsize + 1;
if (g_largestbstsize tree is not BST)
Unless at some level of unwinding, we start building recursion again (walking down another subtree)
We cache the min from left and max from right into local variables before overwriting the global min, max
with a recursion call.
Since we use global variables (or top of recursion stack variable), remove max/min from return context
This way we replace min/max from each side with min/max @ just our level.
Note
!((lsize == 0) || ((lsize>=0) && i.root->key > g_max))
is equivalent to
(!(lsize == 0) && (!(lsize>=0) || (i.root->key key key key <= g_max))
if root==NULL {
return 0;
}
isBST = true;
lsize left)
if !((lsize == 0) || ((lsize>=0) && i.root->key > g_max))
isBST = false
curmin = (lsize == 0)?i.root->key:g_min
rsize right)
if !((rsize == 0) || ((rsize>=0) && i.root->key key:g_max
if (isBST) {
// we are the largest subtree @ this level
size = lsize + rsize + 1;
if (g_largestbstsize 6
#endif
//code iteration 1:
//=================
// Direct implementation of pseudocode
// needs large stack space per iteration
// not all return variables are set at the time
struct lbst_op {
int isBST;
int isNULL;
int min;
int max;
int largestbstsize;
bnode *largestbst;
};
#define true 1
#define false 0
struct lbst_op LBST1(bnode *root)
{
struct lbst_op o, l, r;
if (NULL == root) {
o.isNULL = true;
o.largestbstsize = 0;
return o;
}
else {
o.isNULL = false;
}
l = LBST1(root->left);
r = LBST1(root->right);
// Extract Min and Max values
// if left subtree exists, inherit smallest node, else current node is smallest
o.min = (l.isNULL)?root->key:l.min;
// if right subtree exists, inherit largest node, else current node is largest
o.max = (r.isNULL)?root->key:r.max;
// set o.isBST
// if we are leaf node mark bst as true
// if left is bst and right is bst and current node is in order
if((l.isNULL || (l.isBST && (root->key > l.max))) &&
(r.isNULL || (r.isBST && (root->key r.largestbstsize)?l.largestbstsize:r.largestbstsize;
o.largestbst = (l.largestbstsize > r.largestbstsize)?l.largestbst:r.largestbst;
}
return o;
}
//code iteration 2:
//=================
// instead of global variable, we are using top of recursion stack variable
int _LBST2(bnode *root, int *min, int *max, bnode **largestbst, int *largestbstsize)
{
int lsize, rsize, isBST, curmin, curmax, size;
if (root==NULL)
return 0;
isBST = true;
lsize = _LBST2(root->left, min, max, largestbst, largestbstsize);
if (!((lsize == 0) || ((lsize>=0) && (root->key > *max))))
isBST = false;
curmin = (lsize == 0)?root->key:*min;
rsize = _LBST2(root->right, min, max, largestbst, largestbstsize);
if (!((rsize == 0) || ((rsize>=0) && (root->key key:*max;
if (isBST) {
// we are the largest subtree @ this level
size = lsize + rsize + 1;
if (*largestbstsize < size) {
*largestbstsize = size;
*largestbst = root;
}
*min = curmin;
*max = curmax;
return size;
}
else
return -1;
}
bnode *LBST2(bnode *root)
{
bnode *largestbst;
int min,max,largestbstsize=INT_MIN;
_LBST2(root, &min, &max, &largestbst, &largestbstsize);
return largestbst;
}
Barney said on February 5, 2013
grunt explanation of why the author’s solution is correct:
https://raw.github.com/bharanis/algorithms/master/bst/largest_bst_in_bt.c
Barney said on February 5, 2013
Li said on March 9, 2013
Can anyone explain why Naive Approach runs time complexity is O(n lg n)? I can only get O(N^2).
Peter Wang said on April 28, 2013
The min and max is not correctly used in the solution code. just make a simple tree:
when it traverse to subtree 3, the min is 1 max is 3, but the code will say it is not BST since p->data >= min