Largest Binary Search Tree (BST) in a Binary Tree

November 22, 2010 in binary tree

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.

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

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

}

Rating: 4.6/5 (5 votes cast)

Largest Binary Search Tree (BST) in a Binary Tree, 4.6 out of 5 based on 5 ratings

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

Convert Sorted Array to Balanced Binary Search Tree (BST) →

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

Anonymous said on November 23, 2010
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
Reply
- Rishabh jain said on July 23, 2012
  Really you are awesome man !!!
  VN:F [1.9.22_1171]
  0
  Reply
1337c0d3r said on November 23, 2010
Thanks!!! ^_^
VA:F [1.9.22_1171]
0
Reply
Anonymous said on November 26, 2010
So cool.
VA:F [1.9.22_1171]
0
Reply
Anonymous said on November 28, 2010
Hi 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);
}
VA:F [1.9.22_1171]
0
Reply
Gregory said on November 29, 2010
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
Reply
1337c0d3r said on November 29, 2010
@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
Reply
1337c0d3r said on November 29, 2010
@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
Reply
Anonymous said on November 29, 2010
stunning..
keep them coming bro
VA:F [1.9.22_1171]
0
Reply
Gregory said on November 29, 2010
@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
Reply
Gregory said on November 29, 2010
Thanks blogger…
Link to a pastebin version :
http://pastebin.com/raw.php?i=zuaQ9SLd
VA:F [1.9.22_1171]
0
Reply
1337c0d3r said on November 29, 2010
@Gregory:
Awesome find.
I am thinking on how to fix this one.
Meanwhile…
Ideas, anyone?
VA:F [1.9.22_1171]
0
Reply
Akash said on November 30, 2010
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
Reply
Gregory said on November 30, 2010
@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
Reply
Coman said on December 8, 2010
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
Reply
Gregory said on December 14, 2010
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
Reply
Gregory said on December 15, 2010
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
Reply
- Amm Sokun said on June 2, 2011
  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
  Reply
- lipingwu said on August 7, 2011
  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
  Reply
Matija said on February 28, 2011
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
Reply
jjjjjjj said on March 1, 2011
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
Reply
jjjjjjj said on March 17, 2011
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
Reply
- codingC said on May 31, 2011
  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
  Reply
SG ... said on May 24, 2011
@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
Reply
yyy said on July 10, 2011
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
Reply
Deep said on July 15, 2011
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
Reply
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
Reply
Bugaboo said on October 2, 2011
What is the time complexity of the top-down approach? O(nlogn)?
VA:F [1.9.22_1171]
0
Reply
Anonymous said on November 27, 2011
// 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
Reply
- Anonymous said on November 27, 2011
  // 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
  Reply
Sun Yi said on January 18, 2012
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
Reply
Sun Yi said on January 18, 2012
Wow this html format is so annoying, the tree I mean is
24
15
47
68
VN:F [1.9.22_1171]
0
Reply
Prashant said on February 13, 2012
@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;
}
VA:F [1.9.22_1171]
0
Reply
- Prashant said on February 13, 2012
  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;
  }
  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;
  }
  VA:F [1.9.22_1171]
  0
  Reply
Ankush said on February 19, 2012
awesome!!
VA:F [1.9.22_1171]
0
Reply
Gerald said on February 22, 2012
The 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}.
VA:F [1.9.22_1171]
0
Reply
- outlaw said on July 28, 2012
  yes,you are right the solution in the post is not right. @1337c0d3r
  VN:F [1.9.22_1171]
  0
  Reply
- outlaw said on July 28, 2012
  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
  Reply
peng said on May 11, 2012
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
Reply
- outlaw said on July 28, 2012
  This is not correct , consider the data below:
  3
  / \
  2 4
  / \ / \
  1 10 2 5
  VN:F [1.9.22_1171]
  0
  Reply

Praveen said on July 31, 2012

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.

public int getLargetBST (Node root) {
		if (root == null) return 0;
		
		int leftLength = 0, rightLength = 0;
		
		if (root.leftChild != null) {
			if (root.value > root.leftChild.value) {
				leftLength = getLargetBST(root.leftChild);	
			} else {
				getLargetBST(root.leftChild);
			}
		}
		if (root.rightChild != null) {
			if (root.value < root.rightChild.value) {
				rightLength = getLargetBST(root.rightChild);
			} else {
				getLargetBST(root.rightChild);
			}
		}
		
		int currentBSTLength = 1 + leftLength + rightLength;
		if (currentBSTLength > maxSize)  {
			maxSize = currentBSTLength;
			startBST = root;
		}
			
		return currentBSTLength;
	}

public int getLargetBST (Node root) {

if (root == null) return 0;

int leftLength = 0, rightLength = 0;

if (root.leftChild != null) {

if (root.value > root.leftChild.value) {

leftLength = getLargetBST(root.leftChild);

} else {

getLargetBST(root.leftChild);

}

if (root.rightChild != null) {

if (root.value < root.rightChild.value) {

rightLength = getLargetBST(root.rightChild);

} else {

getLargetBST(root.rightChild);

}

int currentBSTLength = 1 + leftLength + rightLength;

if (currentBSTLength > maxSize) {

maxSize = currentBSTLength;

startBST = root;

}

return currentBSTLength;

}

Karthick said on August 28, 2012

Let’s consider the following tree:(I hope the blogger does not mess with the tree structure)

/ \

2 7

/ \

4 8

/ \

5 25

/ \

3 6

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,

Karthick said on August 28, 2012
The 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
VN:F [1.9.22_1171]
0
Reply
- wiscer said on October 16, 2012
  Karthick, you are right, the code is incorrect.
  VA:F [1.9.22_1171]
  0
  Reply
KFL said on October 16, 2012
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
Reply
dk said on March 19, 2013
the above approach doesnt work for 10,5,3,2,#,#,4,#,#,11,#,13,12,#,#,14,#,#,12
VA:F [1.9.22_1171]
0
Reply