## Largest Subtree Which is a Binary Search Tree (BST)

November 18, 2010

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:

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
```

```      __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.

A Flawed Approach:

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.

Further Thoughts:

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.

VN:F [1.9.22_1171]
Rating: 4.4/5 (14 votes cast)
Largest Subtree Which is a Binary Search Tree (BST), 4.4 out of 5 based on 14 ratings

### 56 responses to Largest Subtree Which is a Binary Search Tree (BST)

1. Thank you for the solution. A beautiful one. Will run against few more test cases and get back to you.

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

VA:F [1.9.22_1171]
0
2. 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.. :/

VA:F [1.9.22_1171]
0
3. @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?)

VA:F [1.9.22_1171]
0
4. @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.

VA:F [1.9.22_1171]
0
5. @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

VA:F [1.9.22_1171]
0
6. 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)?

VA:F [1.9.22_1171]
-1
7. hi there, i saw a pretty smart solution this afternoon. take a look http://www.rawkam.com/?p=822

VA:F [1.9.22_1171]
0
8. @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.

VA:F [1.9.22_1171]
0
9. @Yuan:
That method is correct for the second variant mentioned by Anonymous

VA:F [1.9.22_1171]
0
10. @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.

VA:F [1.9.22_1171]
0
11. 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.

VA:F [1.9.22_1171]
0

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;
}

VA:F [1.9.22_1171]
0
13. 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.

VA:F [1.9.22_1171]
0
14. @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

VA:F [1.9.22_1171]
0
15. Hey ihas1337 may i have your gmail id .

VA:F [1.9.22_1171]
0
16. A nice solution indeed! Most of the ppl give a top down approach which doesn’t work.

VA:F [1.9.22_1171]
0
17. 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.

VA:F [1.9.22_1171]
0
• 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.

VN:F [1.9.22_1171]
0
18. my Java version:

VA:F [1.9.22_1171]
0
• 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.

VA:F [1.9.22_1171]
0
19. @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;
}
} 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)

VA:F [1.9.22_1171]
0
20. if(leftIsBST && rightIsBST && min val && max >= root->va l) //<<< rightCount) ? leftMax : rightMax;
*count = (leftCount > rightCount) ? leftCount : rightCount;
return false;
}

VA:F [1.9.22_1171]
0
21. 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.

VA:F [1.9.22_1171]
0
22. found a descent place to paste my code.
http://ideone.com/TyfDs

VA:F [1.9.22_1171]
0
• 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);

VA:F [1.9.22_1171]
0
• @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!

VA:F [1.9.22_1171]
0
• 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

VA:F [1.9.22_1171]
0
23. 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.

VA:F [1.9.22_1171]
0
• @codingC: yes you are correct, you may want to check my reply to anonymous above your current post.

VA:F [1.9.22_1171]
0
24. 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?

VA:F [1.9.22_1171]
0
25. 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??

VA:F [1.9.22_1171]
0
• 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..

VA:F [1.9.22_1171]
0
26. 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

VA:F [1.9.22_1171]
0
27. 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

VA:F [1.9.22_1171]
0
28. 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

VA:F [1.9.22_1171]
0
29. Works fine.. made tree incorrectly..

VA:F [1.9.22_1171]
0
30. 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
}

VA:F [1.9.22_1171]
0
31. 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)

VN:F [1.9.22_1171]
0
32. 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

VA:F [1.9.22_1171]
0
33. @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?

VA:F [1.9.22_1171]
0
34. Here min and max are not updating

VA:F [1.9.22_1171]
0
35. 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??

VN:F [1.9.22_1171]
0
36. Slight modification of your code. correcting min , max

VA:F [1.9.22_1171]
0
37. What is meant by this line ?:

if (leftNodes == -1 ||
(leftNodes != 0 && p->data <= max))
isBST = false;

VA:F [1.9.22_1171]
0
38. 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.
!(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;
}

VN:F [1.9.22_1171]
0
39. grunt explanation of why the author’s solution is correct:
https://raw.github.com/bharanis/algorithms/master/bst/largest_bst_in_bt.c

VN:F [1.9.22_1171]
0
40. VN:F [1.9.22_1171]
0
41. 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).

VA:F [1.9.22_1171]
0
42. 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

VN:F [1.9.22_1171]
0
43. can’t we use postorder traversal and return the max and min up the tree.
is it necessary to use inorder like u have used…
can u post a post order solution to the same problem pls!

VA:F [1.9.22_1171]
0
44. int noOfNodes;

BinaryTree* findLargestBSTSubtree(BinaryTree *root) {
if (!root) {
noOfNodes = 0;
return root;
}
BinaryTree* leftLargestBST = findLargestBSTSubtree(root->left);
int leftSubtreeNodes = noOfNodes;
BinaryTree* rightLargestBST = findLargestBSTSubtree(root->right);
int rightSubtreeNodes = noOfNodes;
if (leftLargestBST == root->left && rightLargestBST == root->right) {
if ((!root->left || root->left->data data) &&
(!root->right || root->right->data >= root->data)) {
noOfNodes = leftSubtreeNodes + rightSubtreeNodes + 1;
return root;
}
}
return (leftSubtreeNodes > rightSubtreeNodes) ? leftLargestBST : rightLargestBST;
}

VN:F [1.9.22_1171]
0
45. Sorry, posted this in a hurry, missed setting noOfNodes in last line. We can change last line ::

return (leftSubtreeNodes > rightSubtreeNodes) ? leftLargestBST : rightLargestBST;

to ::

if (leftSubtreeNodes > rightSubtreeNodes) {
noOfNodes = leftSubtreeNodes;
return leftLargestBST;
} else {
noOfNodes = leftSubtreeNodes;
return rightLargestBST;
}

Also missed operator ‘left);
int leftSubtreeNodes = noOfNodes;
BinaryTree* rightLargestBST = findLargestBSTSubtree(root->right);
int rightSubtreeNodes = noOfNodes;
if (leftLargestBST == root->left && rightLargestBST == root->right) { // both left and right are BST
if ((!root->left || root->left->data right || root->right->data >= root->data)) { // BST property satisfied at root
noOfNodes = leftSubtreeNodes + rightSubtreeNodes + 1;
return root;
}
}
if (leftSubtreeNodes > rightSubtreeNodes) {
noOfNodes = leftSubtreeNodes;
return leftLargestBST;
} else {
noOfNodes = rightSubtreeNodes;
return rightLargestBST;
}
}

VN:F [1.9.22_1171]
0
• VN:F [1.9.22_1171]
0
• Formatted code :

VN:F [1.9.22_1171]
0