Largest Binary Search Tree (BST) in a 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.

VN:F [1.9.22_1171]
Rating: 4.7/5 (40 votes cast)
Largest Binary Search Tree (BST) in a Binary Tree, 4.7 out of 5 based on 40 ratings

68 thoughts on “Largest Binary Search Tree (BST) in a Binary Tree

  1. Anonymous

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

    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
  3. Gregory

    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]
    +5
  4. 1337c0d3r

    @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
  5. 1337c0d3r

    @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
  6. Gregory

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

    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
  8. Gregory

    @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
  9. Coman

    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
  10. Gregory

    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
  11. Gregory

    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
    1. Amm Sokun

      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
    2. lipingwu

      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
  12. Matija

    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
  13. jjjjjjj

    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
  14. jjjjjjj

    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
    1. codingC

      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
  15. SG ...

    @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
  16. yyy

    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
  17. Deep

    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
  18. Pingback: Largest Binary Search Tree (BST) in a Binary Tree | ε£β”œδΊΊδΊΊβ”‚μ˜ Blog

  19. L

    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
  20. Anonymous

    // 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
    1. Anonymous

      // 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
  21. Sun Yi

    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
  22. Prashant

    @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
    1. Prashant

      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
  23. Gerald

    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
  24. peng

    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
  25. Praveen

    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
  26. Karthick

    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
  27. Karthick

    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
  28. KFL

    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
  29. Pingback: Amazon interview preparation | What I learn, I blog !

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

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

  32. _why

    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
  33. Vinod

    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
  34. Vinod

    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
  35. theOtherWC

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

    VA:F [1.9.22_1171]
    0
    1. Dinesh Appavoo

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

      VA:F [1.9.22_1171]
      0
  36. Umesh Singla

    In the above code,

    shouldn’t this be

    instead?

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*