Largest Binary Search Tree (BST) in a Binary Tree

November 22, 2010

Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.

Note:

In this post, we develop a solution to find the largest BST in a binary tree. Please note that the largest BST may or may not include all of its descendants. If you are interested in the solution for finding the largest BST subtree where it must include all of its descendants, read my previous post: Largest Subtree Which is a Binary Search Tree (BST).

An anonymous reader left an interesting comment in my previous post where the interviewer was asking what if the largest BST may or may not include all of its descendants.

From now onwards, we use the term largest BST for largest BST which may or may not include all of its descendants, while largest BST subtree is for largest BST subtree which must include all of its descendants.

The example I showed in my last post was too trivial, so here I show a slightly more complicated example.

```               ___________________15___________________
/                                        \
___________10___________                             20
/                        \
5                   _____7____
/          \
__2__       __5
/     \     /
0      8    3 ```

The largest BST (may or may not include all of its descendants) from the above example should be:

```         ____15____
/          \
_10          20
/
5
```

while the largest BST subtree (must include all of its descendants) should be:

```      __2_
/    \
0     8
```
An Incorrect Solution:

One might try to do an in-order traversal of the binary tree and find the longest increasing contiguous sequence or the longest increasing subsequence. Although these two approaches seemed to work for many cases, they are flawed and cannot handle the above case.

Let’s do an in-order traversal for the above binary tree:

`5 10 0 2 8 7 3 5 15 20`

The longest increasing contiguous sequence is:

`3 5 15 20`

The longest increasing subsequence is:

`0 2 3 5 15 20`

As you can see, neither one of them is correct.

A Top-down Approach:
The largest BST subtree solution requires a bottom-up approach where the min and max values are passed bottom-up. 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.

However, finding the largest BST requires a slightly different approach. We want the largest BST by including as many nodes as possible while we traverse down the tree, as long the current BST constraint is maintained. What happens when we see a node that breaks the current BST constraint? The answer is we can simply exclude it. However, we must treat it as an entirely new tree (ie, find in that tree if there is another larger BST). As you can see, we are passing the min and max values top-down, while the nodes count are passed bottom-up (Read my previous post to know how).

As a tree is defined recursively using its left and right subtrees, you could not simply return root node of the largest BST as this would include all of its subtrees. You would need to create copies of the subtrees or delete nodes from the original binary tree. My code below create copies of the subtrees. As it does not handle the deletion of trees, some of the subtrees that are created dynamically will eventually be memory-leaked. Handling this problem would require more complicated code. I will not demonstrate how to do it here since this post is to illustrate the algorithm.

VN:F [1.9.22_1171]
Largest Binary Search Tree (BST) in a Binary Tree, 4.5 out of 5 based on 17 ratings

54 responses to Largest Binary Search Tree (BST) in a Binary Tree

1. Brilliant!!
Hats off to you for explaining the very common mistake people do using the longest contiguous subsequence.
I am fan of you buddy!

VA:F [1.9.22_1171]
0
2. Thanks!!! ^_^

VA:F [1.9.22_1171]
0
3. So cool.

VA:F [1.9.22_1171]
0
4. Hi 1337c0d3r,
But I found one condition of the code handling is strange.
else {
// include this node breaks the BST constraint,
// so treat this node as an entirely new tree and
// check if a larger BST exist in this tree
findLargestBST(p, INT_MIN, INT_MAX, maxNodes, largestBST, child);
// must return 0 to exclude this node
return 0;
}

Shouldn't this be
else{
findLargestBST(p.left, INT_MIN, INT_MAX, maxNodes, largestBST, child);
findLargestBST(p.right, INT_MIN, INT_MAX, maxNodes, largestBST, child);
}

VA:F [1.9.22_1171]
0
5. Actually there seems to be a problem if the root of the largest BST is actually contained in a BST currently being computed… The only possible roots in your code are the nodes that didn't make it in a BST (unless I missed something).

VA:F [1.9.22_1171]
0
• The above code is not correct.It works for some cases only.Plz update the code.

VA:F [1.9.22_1171]
0
6. @Anonymous:
Basically what that line of code is doing — because including the node breaks the current BST constraint, so treat that node and its subtrees as an entirely new search for the largest BST.

VA:F [1.9.22_1171]
0
7. @Gregory:
Do you have an input case which shows the problem? I would be interested to know.

I believe there would not be a problem. Computing the number of nodes uses a bottom-up approach (although the min and max values are passed top-down). It will traverse up the tree to continue including its parent node if it satisfies the BST constraint. It's kinda like a greedy approach, so you will always be guaranteed that the largest BST is always obtained.

VA:F [1.9.22_1171]
0
8. stunning..
keep them coming bro

VA:F [1.9.22_1171]
0
9. @1337c0d3r

_________11_________
/ \
12 ______________15______________
/ \
___________10___________ 20
/ \
5 _____7____
/ \
__2__ __5
/ \ /
0 8 3

(just in case blogger kills the ascii art, I set 11 as a root node, with left leaf 12 and the default tree (starting at 15) as the right child.

This one returns 7 2 0 as largest BST when I tested.

Changing the beginning of the function fixes the problem, but the complexity is just terrible :

int findLargestBST(…) {
if (!p) return 0;
if (min < p->data && p->data < max) {
if ((min != INT_MIN) || (max != INT_MAX)){
findLargestBST(p, INT_MIN, INT_MAX, maxNodes, largestBST, child);
}

Any ideas ?

VA:F [1.9.22_1171]
0
10. Thanks blogger…
Link to a pastebin version :
http://pastebin.com/raw.php?i=zuaQ9SLd

VA:F [1.9.22_1171]
0
11. @Gregory:
Awesome find.
I am thinking on how to fix this one.
Meanwhile…
Ideas, anyone?

VA:F [1.9.22_1171]
0
12. I suspect if the else part is working. IMO, it shouldn't return zero. This will mess up the things. Example is
15
100 5
20 170 3 2

above example is a complete binary tree in case formatting doesn't work. Am I right or missing smthng. I didn't test it but just went through the code and suspect this.

VA:F [1.9.22_1171]
0
13. @Akash

Selecting the largest BST is done in the recursive call findLargestBST in that else part. The return value is only used to count the number of nodes when the current node is not the root. So when you are in the else, the current node is the root of the computed BST, and thus it should not be counted as a node one level higher. The return 0 is there to tell the node which made the function call NOT to count that node.

(this is probably my worst comment ever, congrats if you manage to understand it ^^)

VA:F [1.9.22_1171]
0
14. I think bottom-up is better here to reduce duplicate checking. Combining left and right with parent node needs some top-down pruning on the left/right child bst, and the combined bst should be compared with left/right max bst. The count of bst rooted at each node may also need to be saved. This way, we can achieve nlogn time complexity instead of n^2 as in the post.
Not sure, my idea gets across clear enough.

VA:F [1.9.22_1171]
0
15. Quick code which seems to work correctly : http://pastebin.com/5QjBnjiS

Uses the bottom-up approach : recreate a tree from bottom up, and when a node violates the BST rules, cut it off. Each node has a size field to avoid recomputing it over and over again.

Complexity : O(n log n)

VA:F [1.9.22_1171]
0
16. Looks like yesterday's comment didn't work :/

Here's a quick bottom-up implementation : when moving up, recreate a tree, and cut off the branches which don't respect the BST limitations. When you found the largestBST's root node, just scan the initial tree and remove all the branches that don't fit in.

Complexity : n log n

http://pastebin.com/5QjBnjiS

VA:F [1.9.22_1171]
0
• can u try ur code for this inorder and preorder sequence?

inorder: 8,2,3,5,-4,1,0,4,6,7,9,10,12
preorder: 5,2,8,3,7,4,1,-4,0,6,10,9,12

i think ur algorithm doesnt work for this test case.
Would like if you could test it out.

Thanks

VA:F [1.9.22_1171]
0
• Gregory, check my codes. I had the same idea to yours, but I used the hash table instead to store the size associated with each node but didn’t create a new structure with size information for the node:

int largestBST(Node* root, map &table){
if(root == NULL) return 0;

int lSize = largestBST(root->left, table);
int rSize = largestBST(root->right, table);

int size = 1;
if(lSize!=0 && root->left->data data){
size += lSize;
Node* node = root->left;
while(node!=NULL && node->datadata) node = node->right;
if(node != NULL) size -= table.find(node)->second;
}
if(rSize!=0 && root->right->data >= root->data){
size += rSize;
Node* node = root->right;
while(node!=NULL && node->data>=root->data) node = node->left;
if(node != NULL) size -= table.find(node)->second;
}

table[root] = size;
return size;
}

Node* largestBST(Node* root){
if(root == NULL) return NULL;

map table;
largestBST(root, table);

int maxSize = 0;
Node* maxRoot;
for(map::iterator it = table.begin(); it != table.end(); it ++){
if(maxSize second){
maxSize = it->second;
maxRoot = it->first;
}
}

cout << "Largest size: " << maxSize << endl;
return maxRoot;
}

VA:F [1.9.22_1171]
0
17. My idea uses a similar approach and it’s also O(N log N), and it’s quite simple.

One DFS is needed to traverse a tree. Also, when you enter a node, put it on a stack and when you call the recursion for child nodes, mark which way you’re going (left or right).

Example of such a stack – 15 left 10 right 12 left. That way you know the left and right boundaries.

For each node, move up the stack as much as you can (don’t pop anything) – thus preserving BST rule and for each node on stack, do a simple increment in a global counting array. When the BST rule is broken, break. The idea is to count for each node in how many BSTs it’s in (by incrementing the counter for the root of each one).

I hope I explained it well enough..

VA:F [1.9.22_1171]
0
18. I attach an O(N) bottom up solution. Please comment.

Node* FindSubBST(Node* root, int& curNum, int& maxNum)

curNum is the maximum node number of sub BST using input Node root as its ROOT.
maxNum is the maximum node number of sub BST under input Node root.

curNum is at least 1 if root exists. maxNum is always greater than or equal to curNum.

return value Node* is the ROOT of sub BST with maximum node number.

Thanks.

Node* FindSubBST(Node* root, int& curNum, int& maxNum)
{
if (! root) {
curNum = 0;
maxNum = 0;
return NULL;
}

int leftcur, rightcur, leftmax, rightmax;

Node* left = FindSubBST(root->GetLeft(), leftcur, leftmax);
Node* right = FindSubBST(root->GetRight(), rightcur, rightmax);

curNum = 1;

if (root->GetLeft()) {
if (root->GetValue() >= root->GetLeft()->GetValue()) {
curNum += leftcur;
}
}

if (root->GetRight()) {
if (root->GetValue() >= root->GetRight()->GetValue()) {
curNum += rightcur;
}
}

maxNum = max(curNum, max(leftmax, rightmax));

if (leftmax == maxNum){
return left;
} else if (rightmax == maxNum){
return right;
} else {
return cur;
}
}

VA:F [1.9.22_1171]
0
19. Last post is incorrect. Attach a new one, bottom up, O(n)

Node* FindSubBST(Node* root, int& min, int& max, int& maxNum, int& curNum, Node*& maxTree)
{
if (! root) {
min = numeric_limits::max();
max = numeric_limits::min();

maxNum = 0;
curNum = 0;
maxTree = NULL;
return NULL;
}

int leftmin, leftmax, rightmin, rightmax;
int leftNum, rightNum, leftcur, rightcur;
Node* leftTree, *rightTree;

Node* left = FindSubBST(root->left, leftmin, leftmax, leftNum, leftcur, leftTree);
Node* right = FindSubBST(root->right, rightmin, rightmax, rightNum, rightcur, rightTree);

Node* node = new Node(root);
node->left = NULL;
node->right = NULL;

bool matchleft = (root->value >= leftmax);
bool matchright = (root->value value; max = node->value;
curNum = 1;

if (matchleft) {
root->left = left;
min = leftmin;
curNum += leftcur;
}

if (matchright) {
root->right = right;
max = rightmax;
curNum += rightcur;
}

if (curNum > max(leftmax, rightmax)) {
maxTree = node;
maxNum = curNum;
} else if (leftmax > rightmax) {
maxTree = leftTree;
maxNum = leftmax;
} else {
maxTree = rightTree;
maxNum = rightmax;
}

return node;
}

VA:F [1.9.22_1171]
0
• This is not correct. Even if root-value<leftmax, parts of left subtree still could be left child of the root in the largest BST.

VA:F [1.9.22_1171]
0
20. @1337c0d3r :: thanks for creating such a fabulous blog.

I realized, this peace of code has a bug. Please try to run the code for following Input and let us know the output

Node *Tree = NULL;
Tree = new_node(15);
Tree->left = new_node(10);
Tree->left->left = new_node(5);
Tree->left->right = new_node(7);
Tree->left->right->left = new_node(2);
Tree->left->right->left->left = new_node(0);
Tree->left->right->left->right = new_node(8);

Tree->left->right->left->right->right = new_node(10);
Tree->left->right->left->right->right->right = new_node(12);
Tree->left->right->left->right->left = new_node(6);

Tree->left->right->right = new_node(4);
Tree->left->right->right->left = new_node(3);

Tree->right = new_node(20);

If I am not making a blunder than output should be the root with value 2 but it is returning (inorder sequence ) 6 8 10 12

correct me if I am wrong

VA:F [1.9.22_1171]
0
21. Sounds like some problem.

Don’t you think you should not use “else…”?

When the condition for “if” is true, some constrain is forced for MIN and MAX. But it is possible to get a a bigger tree with MIN=INT_MIN, and MAX=INT_MAX. So, we should always run the part in else section.

How do you think?

VA:F [1.9.22_1171]
0
22. I think we will have to follow both bottom up and top down approach and find the largest BST.

Example
Root : 10
10′s Lchild = 2
2′s Rchild = 6
6′s Rchild = 11
11′s Lchild = 9

If we follow bottom up we find tree 2, 6 ,11, 9 is largest BST with 4 nodes. We find an issue when we examine node=10.

If we follow top down, we find 10, 2, 6 is largest BST with 3 nodes against a BST 11,9. We find an issue when we examine node =11

Thus we need to for both the approaches and see which gives us the largest BST.

VA:F [1.9.22_1171]
0
23. L said on July 31, 2011

There should be 3 cases.

1. One where there is a large tree in my left and right, but my current node cannot be included.

2. One where there is a large tree in my left and right, but my current node can be included, but the subsequent tree cannot be included in the parent tree.

3. One where there is a large tree in my left and right, but my current node can be included, but the subsequent tree can be included in the parent tree.

you’re not accounting for 2.

VA:F [1.9.22_1171]
0
24. What is the time complexity of the top-down approach? O(nlogn)?

VA:F [1.9.22_1171]
0
25. // bottom up approach
int findLargestBST(tree *root)
{
if(root == NULL)
return 0;
count = 1;
countL = findLargestBST(root->left);
countR = findLargestBST(root->right);
if(root->left != NULL && root->data > root->left->data)
count += countL;
if(root->right != NULL && root->data > root->right->data)
count += countR;
return max(count, countL, countR);
}

VA:F [1.9.22_1171]
0
• // CORRECTED CODE
// bottom up approach
int findLargestBST(tree *root)
{
if(root == NULL)
return 0;
int count = 1;
int countL = findLargestBST(root->left);
int countR = findLargestBST(root->right);
if(root->left != NULL && root->data > root->left->data)
count += root->left->count;
if(root->right != NULL && root->data right->data)
count += root->right->count;
root->count = count;
return max(count, max(countL, countR));
}

VA:F [1.9.22_1171]
0
26. I am not entirely sure if the code does the job.

In the code, a new search from a node is initialized only if it cannot be added to the larger tree. However, even if it can be added, the size of the found left and right subtree can still be limited, and may be much smaller than the tree starting from that node…

For example if we have a tree
3
2 4
1 5
4 7
6 8
consider node 2, clearly the bst starting from node 2 contains the whole subtree
however, node 2 can be added to the tree above, so there won’t be a search from 2 with unlimited range. As a result, the tree returned has to be 3,2,1,5,4. A new, unlimited range search will only start from 5 as it doesn’t fit into the range [2,3]

Maybe I’m just very wrong….

VN:F [1.9.22_1171]
0
27. Wow this html format is so annoying, the tree I mean is
24
15
47
68

VN:F [1.9.22_1171]
0
28. @1337c0d3r:
These are really awesome tutorials:
For the problem that is being discussed, I have worked out a solution based in ur previous solution for finding the largestBSTSubtree following a strictly bottom up approach:
Only thing that I changed is, when a subtree doesn’t satisfy the BST constraint don’t omit that subtree altogether but start a new search for the largest subtree from there.
Here is the code:
// Find the largest BST in a binary tree.
// The min and max values are passed bottom-up to check if
// including a node satisfies the current BST constraint.
// The child nodes are passed bottom-up to be assigned
// to its parent. Also, maxNodes and largestBST are passing values bottom-up and
// contains information about largest BST seen so far
// Returns the total number of nodes the child holds.

int findLargestBSTSubtree(BinaryTree *p, int &min, int &max, BinaryTree *& child, int &maxNodes, BinaryTree *& largestBST) {

if (!p) return 0;
bool isBST = true;
int leftNodes = findLargestBSTSubtree(p->left, min, max,child,maxNodes,largestBST);

int currMin;
BinaryTree* left;
if(leftNodes == 0) {
left = NULL;
currMin = p->data;
}
else {
left = child;
currMin = min;
}
//if the node voilates the BST constraints start a new search
if(leftNodes != 0 && p->data right, min, max,child,maxNodes, largestBST);

int currMax;
BinaryTree* right;
if(rightNodes == 0) {
right = NULL;
currMax = p->data;
}
else {
right = child;
currMax = max;
}
//if the node voilates the BST constraints start a new search
if(rightNodes != 0 && p->data data);
parent->left = left;
parent->right = right;
child = parent;
int totalNodes = leftNodes + rightNodes + 1;
if (totalNodes > maxNodes) {
maxNodes = totalNodes;
largestBST = p;
}
} else {
//starting a new search
return 0; // This subtree is not a BST
}
}

BinaryTree* findLargestBSTSubtree(BinaryTree *root) {
BinaryTree *largestBST = NULL,*child=NULL;
int min, max;
int maxNodes = INT_MIN;
findLargestBSTSubtree(root, min, max,child maxNodes, largestBST);
return largestBST;
}

VA:F [1.9.22_1171]
0
• I’m extremely sorry, there are few typos inthe above comment. Reposting it.

(hope this is posted correctly…!!)

// Find the largest BST in a binary tree.
// The min and max values are passed bottom-up to check if
// including a node satisfies the current BST constraint.
// The child nodes are passed bottom-up to be assigned
// to its parent. Also, maxNodes and largestBST are passing values bottom-up and
// contains information about largest BST seen so far
// Returns the total number of nodes the child holds.

int findLargestBSTSubtree (BinaryTree *p, int &min, int &max, BinaryTree *& child, int &maxNodes, BinaryTree *& largestBST) {

if (!p) return 0;
bool isBST = true;
int leftNodes = findLargestBSTSubtree(p->left, min, max,child,maxNodes,largestBST);

int currMin;
BinaryTree* left;
if(leftNodes == 0) {
left = NULL;
currMin = p->data;
}
else {
left = child;
currMin = min;
}
//if the node voilates the BST constraints start a new search
if(leftNodes != 0 && p->data right, min, max,child,maxNodes, largestBST);

int currMax;
BinaryTree* right;
if(rightNodes == 0) {
right = NULL;
currMax = p->data;
}
else {
right = child;
currMax = max;
}
//if the node voilates the BST constraints start a new search
if(rightNodes != 0 && p->data >= min) isBST = false;

if(isBST) {
min = currMin;
max = currMax;
BinaryTree* parent = new BinaryTree(p->data);
parent->left = left;
parent->right = right;
child = parent;
int totalNodes = leftNodes + rightNodes + 1;
if (totalNodes > maxNodes) {
maxNodes = totalNodes;
largestBST = p;
}
} else {
//starting a new search
min = max = p->data;
BinaryTree* parent = new BinaryTree(p->data);
parent->left = parent->right= NULL;
child = parent;
return 1; // node a size 1 is always a binary tree
}
}

BinaryTree* findLargestBSTSubtree(BinaryTree *root) {
BinaryTree *largestBST = NULL,*child=NULL;
int min, max;
int maxNodes = INT_MIN;
findLargestBSTSubtree(root, min, max,child maxNodes, largestBST);
return largestBST;
}

VA:F [1.9.22_1171]
0
29. awesome!!

VA:F [1.9.22_1171]
0
pre-order: {5, 11, 8, 6,4,2,10,12,14}
in-order: {5, 2,4,6,8,10,12,14,11}
You can construct a unique tree based on the given pre-order and in-order traversal above. The largest BST given by the code in this article include nodes {5,6,8,10,11}. However the correct answer is {2,4,6,8,10,12,14}.

VA:F [1.9.22_1171]
0
• yes,you are right the solution in the post is not right. @1337c0d3r

VN:F [1.9.22_1171]
0
• The routine in the post should be run for every node in the tree to get the largest BST.

VN:F [1.9.22_1171]
0
31. I use a Dynamic Programming strategy and I think it is very clear.

I define f(n) as the largest number of nodes in a binary search tree rooted EXACTLY at n. Here as usual, this BST doesn’t need to contain all the descendants.

For a particular node “n”, there are four cases:
1) if (n->left==0 && n->right==0) f(n)=1
2) if (n->left && n->right==0) ,
f(n) = f(n->left)+1 if n and the BST rooted at n->left can be combined.
f(n) = 1 if they can not be combined
3) if (n->left==0 && n->right)
f(n) = f(n->right)+1 if n and the BST rooted at n->right can be combined
f(n) = 1 if they can not be combined
4) if(n->left && n->right)
f(n) = f(n->left)+f(n->right)+1 if n can be combined with left and right
f(n) = f(n->left) + 1 if n can only be combined with left
f(n) = f(n->right) + 1 if n can only be combined with right
f(n) = 1 if n can be combined with neither

By keeping track of the largest f(n) and its corresponding tree node, we can get the results. This idea passes the counter examples given in this thread.

VN:F [1.9.22_1171]
0
• This is not correct , consider the data below:
3
/ \
2 4
/ \ / \
1 10 2 5

VN:F [1.9.22_1171]
0
32. Very simple and efficient recursive code for finding out largest BST in a binary tree…

The idea is about considering the length of the child nodes as long as they are accepting BST rules, otherwise ignoring the length of child nodes.

VA:F [1.9.22_1171]
0
33. Let’s consider the following tree:(I hope the blogger does not mess with the tree structure)

Here, I think the above code would return the largestBST consisting of nodes 6,7,8,25.
But the actual answer should be the sub-tree starting at 8.
I am not sure, but I think the code breaks when the largest BST is a sub-tree extending upto the leaf as is the problem with the above example.

Please correct me if I am wrong.

Thanks,

VN:F [1.9.22_1171]
0
34. The blogger has partially messed with the tree!

Here,
7 is the right child of 6
8 is the right child of 7
25 is the right child of 8

Others seem to be okay

VN:F [1.9.22_1171]
0
35. Hi @1337c0d3r,

Do you have a fix for the bug that @Gregory mentioned? I also noticed this problem that your solution didn’t handle the case where the _real_ largest BST’s root is in the BST you are currently computing.

In other words, it seems wrong to assume if a node breaks current BST constraints, it’s possible that there’s a candidate which rooted at this node. In fact, there might be a candidate at any node which is this node’s ascendant.

Example:

http://pastebin.com/raw.php?i=Zxp6msbW

In this example, 11 breaks the constraint [5,10], but the _real_ largest BST is the one rooted at 5, or 10.

VN:F [1.9.22_1171]
0
36. the above approach doesnt work for 10,5,3,2,#,#,4,#,#,11,#,13,12,#,#,14,#,#,12

VA:F [1.9.22_1171]
0

.

VA:F [1.9.22_1171]
0
38. can someone please explain how it works for the case
7
/
2
/ \
0 8

the output is correct when i tested 0 2 7

Can someone put the trace how it neglects 8 i traced the above program and i got lost….

VN:F [1.9.22_1171]
0
• @1337c0d3r please explain the programs trace how it works ?

VN:F [1.9.22_1171]
0
39. Great post!! I made an implementation in Java, you can find it here: http://www.librethinking.com/2013/09/find-largest-binary-search-tree-in-tree.html

VA:F [1.9.22_1171]
0
40. This will break for the below example:
result : 10 20 30 35 (size 4)
expected : 10 20 25 40 45 (size 5)

void printTree(BinaryTree *root)
{
if (root == NULL)
return;
printTree(root->left);
std::cout << " " <data <right);
}

int main()
{
BinaryTree *root = new BinaryTree(30);
root->left = new BinaryTree(20);
root->right = new BinaryTree(35);
root->left->left = new BinaryTree(10);
root->left->right = new BinaryTree(40);
root->left->left->left = new BinaryTree(11);
root->left->right->left = new BinaryTree(25);
root->left->right->right = new BinaryTree(45);

BinaryTree *subroot = findLargestBST(root);
printTree(subroot );
}

VA:F [1.9.22_1171]
0
• Print method you can ignore, some code copy past problem.

VA:F [1.9.22_1171]
0
41. This solution wont work for the below tree. re posting because some code missing last time.

void printTree(BinaryTree *root)
{
if (root == NULL)
return;
printTree(root->left);
std::cout << " " <data <right);
}

int main()
{
BinaryTree *root = new BinaryTree(30);
root->left = new BinaryTree(20);
root->right = new BinaryTree(35);
root->left->left = new BinaryTree(10);
root->left->right = new BinaryTree(40);
root->left->left->left = new BinaryTree(11);
root->left->right->left = new BinaryTree(25);
root->left->right->right = new BinaryTree(45);

BinaryTree *subroot = findLargestBST(root);
printTree(subroot );
}

VA:F [1.9.22_1171]
0