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

**is for**

*largest BST subtree**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.

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 39 40 41 42 43 44 45 46 |
// Find the largest BST in a binary tree. // This code does not delete dynamically-allocated nodes, // so memory will be leaked upon exit. // The min and max values are passed top-down to check if // including a node satisfies the current BST constraint. // The child nodes are passed bottom-up to be assigned // to its parent. // Returns the total number of nodes the child holds. int findLargestBST(BinaryTree *p, int min, int max, int &maxNodes, BinaryTree *& largestBST, BinaryTree *& child) { if (!p) return 0; if (min < p->data && p->data < max) { int leftNodes = findLargestBST(p->left, min, p->data, maxNodes, largestBST, child); BinaryTree *leftChild = (leftNodes == 0) ? NULL : child; int rightNodes = findLargestBST(p->right, p->data, max, maxNodes, largestBST, child); BinaryTree *rightChild = (rightNodes == 0) ? NULL : child; // create a copy of the current node and // assign its left and right child. BinaryTree *parent = new BinaryTree(p->data); parent->left = leftChild; parent->right = rightChild; // pass the parent as the child to the above tree. child = parent; int totalNodes = leftNodes + rightNodes + 1; if (totalNodes > maxNodes) { maxNodes = totalNodes; largestBST = parent; } return totalNodes; } 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; } } BinaryTree* findLargestBST(BinaryTree *root) { BinaryTree *largestBST = NULL; BinaryTree *child; int maxNodes = INT_MIN; findLargestBST(root, INT_MIN, INT_MAX, maxNodes, largestBST, child); return largestBST; } |

Brilliant!!

Hats off to you for explaining the very common mistake people do using the longest contiguous subsequence.

I am fan of you buddy!

0Really you are awesome man !!!

0Thanks!!! ^_^

0So cool.

0Hi 1337c0d3r,

Thanks for your detail explanation.

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

}

0Actually 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).

+5The above code is not correct.It works for some cases only.Plz update the code.

0@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.

0@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.

0stunning..

keep them coming bro 🙂

0@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 ?

0Thanks blogger…

Link to a pastebin version :

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

0@Gregory:

Awesome find.

I am thinking on how to fix this one.

Meanwhile…

Ideas, anyone?

0I 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.

0@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 ^^)

0I 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.

0Quick 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)

0Looks 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

0can 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

0Gregory, 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;

}

0My 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.. 🙂

0I 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;

}

}

0Last 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;

}

0This is not correct. Even if root-value<leftmax, parts of left subtree still could be left child of the root in the largest BST.

0@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

0Sounds 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?

0I 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.

0Pingback: Largest Binary Search Tree (BST) in a Binary Tree | 口├人人│의 Blog

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.

0What is the time complexity of the top-down approach? O(nlogn)?

0// 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);

}

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

}

0I 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….

0the same problem as yyy said, i think so. every node should be treated as root once, so the descendants could enjoy looser limits rather than those passed down from very high level.

0Wow this html format is so annoying, the tree I mean is

24

15

47

68

0@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;

}

return totalNodes;

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

}

0I’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;

}

return totalNodes;

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

}

0awesome!!

0The code given in this article is not correct. Try following tree:

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

0yes,you are right the solution in the post is not right. @1337c0d3r

0The routine in the post should be run for every node in the tree to get the largest BST.

0I 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.

0This is not correct , consider the data below:

3

/ \

2 4

/ \ / \

1 10 2 5

0Very 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.

0Hi Praveen

Where you have initialized maxSize and startBST??

0Let’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,

0The blogger has partially messed with the tree!

So, I would just add an explanation about 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

0Karthick, you are right, the code is incorrect.

0Hi @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.

0Pingback: Amazon interview preparation | What I learn, I blog !

the above approach doesnt work for 10,5,3,2,#,#,4,#,#,11,#,13,12,#,#,14,#,#,12

0Pingback: MSFT Office, SQL, Azure team interviews - Hil's managed code development - Site Home - MSDN Blogs

Pingback: GsFGs important questions | What I learn, I blog !

To embed your code, please use

.

0can 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….

0@1337c0d3r please explain the programs trace how it works ?

0Great 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

0This 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 );

}

0Print method you can ignore, some code copy past problem.

0This 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 );

}

0I proposed a dynamic programming version of solution, and please correct me if I’m wrong.

Let OPT[n] denote the largest node count of the largest BST in the tree rooted in n. Please note that the largest BST does not have to root in node n – it just has to be in some tree rooted in n.

So OPT[n] = max{ OPT[n.Left], OPT[n.Right], maxBSTRootedinN(n)}.

The reasoning is that given any tree rooted in n, the maximum BST in the tree lies in only 3 possible places: (1) a tree in its left subtree (2) a tree in its right subtree (3)a BST rooted in n

maxBSTRootedinN(n) finds the maximum BST rooted in node n. It is an O(n) operation using any DFS algroithm.

The algorithm takes O(n^2) time to run.

0Well, this is actually divide and conquer. So nlogn

0Can you please explain why we are calling this solution bottom-up?

Since we are going from root at the top down to deep levels, isn’t it a top-down?

0In top-down approach we can’t test the BST satisfying condition. So we will reach the bottom and test from there.

0The correct implementation of largest BST ing a BT (java) is available in the following URL

https://github.com/dineshappavoo/Implementation/tree/master/LARGEST_BST_IN_BT_NOT_INDUCED_VER1.0

0Simply awesome!!

0http://www.ideserve.co.in/learn/size-of-largest-bst-in-binary-tree

Here is a nice detailed explanation of the algorithm.

+1In the above code,

shouldn’t this be

instead?

0