Largest Subtree Which is a Binary Search Tree (BST)

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:

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

An anonymous reader asked this interesting question, so here you are. Amazon had asked this in technical interviews and it seemed to me that this is not a popular tree question. It is one of the trickier ones, since you are required to combine the idea from this problem: Determine if a Binary Tree is a Binary Search Tree, and also the idea of doing a Depth-first search (DFS).

It’s important that you understand the question correctly. Let’s try an example below. Which is the largest BST subtree?

         ____10____
        /          \
      __5_         15_
     /    \           \
     1     8           7

For most people, there would be two possible interpretations for the term “subtree”.

Is this ( subtree (1) ) the largest BST subtree?

         ____10____
        /          \
      __5_         15     -------- subtree (1)
     /    \ 
     1     8 

How about this one ( subtree (2) ) ?

      __5_
     /    \               -------- subtree (2)
     1     8 

According to Wikipedia, a subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. Therefore, there is no doubt that subtree (2) is the correct answer, as subtree (1) does not include all of its descendants. It is important that you understand the term subtree correctly. If you are not sure, ask the interviewer and you should not make any assumptions.

Naive Approach:
A naive approach is to reuse the solution from Determine if a Binary Tree is a Binary Search Tree. Starting from the root, we process in the order of current node, left child, then right child. For each node, you would call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then we have to continue examining its left and right child. If only one of the subtrees is BST, then we can return that subtree. However, if both left and right subtrees are BSTs, then we have to compare which subtree is larger (has more descendant nodes), then return the larger one.

Assume that we have a complete tree (ie, all leaves are at the same depth) with n nodes, the naive approach’s run time complexity is O(n lg n). The proof is left as an exercise to the reader.

A Flawed Approach:

How about doing an in-order traversal for the binary tree? The longest increasing contiguous sequence must be the largest BST subtree. Try to do an in-order traversal for the example tree above. This approach simply does not work. Period.

A Bottom-up Approach:
The naive approach is using a top-down approach. It is hardly efficient, simply because we are calling isBST() over and over again. Each time isBST() is called, it traverses down to the leaves to verify if the subtree is a BST.

Let’s think from another perspective. Instead of traversing down the tree, why not traverse up the tree using a bottom-up approach? In other words, we verify the deeper nodes before we verify if the above nodes satisfy the BST requirements.

The main reason of doing this is when one of the nodes does not satisfy the BST properties, all subtrees above (which includes this node as well) must also not satisfy the BST requirements.

First, let’s review our definition of a BST. A tree is a BST if the following properties are satisfied:

  • Both left and right subtrees of a node are BSTs.
  • The node’s value is greater than its left subtree’s maximum.
  • The node’s value is less than its right subtree’s minimum.

Using a bottom-up approach, we need to pass some information up the tree. Obviously, we need to pass minimum and maximum values of the subtree as we traverse up the tree, so the above subtrees could be verified for BST’s properties.

As compared to the top-down approach, the bottom-up approach is such an awesome choice because the results for total number of nodes could be passed up the tree. This saves us from recalculating over and over again. The total number of nodes for a subtree is simply the total number of nodes of its left and right subtrees plus one.

Isn’t the bottom-up approach neat? It acts like magic until you understand it, and solves all the problems that the top-down approach has. The run-time complexity for the bottom-up approach is O(n). Beware of this gotcha when you implement the algorithm. Even though a node’s left subtree is not a BST, you must still continue traverse its right subtree as the largest BST subtree might be contained in its right subtree.

Further Thoughts:

Here is a variant of the largest BST problem. What if we want to find the largest BST in a tree where it may or may not include all of its descendants? Read my next post: Largest Binary Search Tree (BST) in a Binary Tree to find out.

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

62 thoughts on “Largest Subtree Which is a Binary Search Tree (BST)

  1. Anonymous

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

    Quick Comments:

    I think you need to initialize min and max in findLargestBST() to INT_MIN and INT_MAX respectively.

    The interviewer was actually posing different variants for this Q.

    Let me put them here:
    1. What to do to make the "subtree (1)" as your answer? What I mean here is, I need largest BST, not necessarily something which is a subtree sticking to the Wiki Definition.
    2. What if there is no restriction for the sub-tree to extend till the leaves [sub-tree => any part of the tree, not as per wiki def again]

    Thanks

    VA:F [1.9.22_1171]
    0
  2. vitorbal

    This is a very good question… the kind of question you are very prone to make some kind of small mistake if you need to write the whole solution on a white board.. :/

    VA:F [1.9.22_1171]
    0
  3. 1337c0d3r

    @Anonymous:
    I did not initialize min and max because they will be initialized when it reaches down to the leaf.

    In fact, the variant number 1) is easier to solve. Just use the top-down approach and pass the min and max values down the tree. Traverse down the tree as long as including a node doesn't break the BST constraint. Similar to implementing isBST(), pass the min and max values down the tree.

    Could you explain a little more on variant 2)? I am not quite sure what you meant. (Did you mean the nodes in the original tree could be connected indirectly (ie, skipping one or more indirect nodes) to form a BST?)

    VA:F [1.9.22_1171]
    0
  4. 1337c0d3r

    @vitorbal:
    Yes, especially when bottom-up approach is usually harder than top-down. You need to be careful of tracking how the values are being modified as it traverse up the tree, which could be tricky.

    VA:F [1.9.22_1171]
    0
  5. Anonymous

    @1337c0d3r
    My second variant is not about connecting nodes indirectly, What I mean is, let me tell with example:
    a
    / \
    b c
    / \ / \
    d e f g
    / \
    h i
    What if my answer can be only the tree with nodes [b,d,e], this is a subtree which doesnt extend till leaves.
    Hope you got the idea.

    Thanks

    VA:F [1.9.22_1171]
    0
  6. 1337c0d3r

    To me, it seemed that variant 1) is the same as variant 2). Could you give me an example that differentiate variant 1) and variant 2)?

    VA:F [1.9.22_1171]
    -1
  7. 1337c0d3r

    @Yuan:
    That solution is incorrect. In fact, either one of these are incorrect: maximum increasing contiguous sequence OR maximum increasing subsequence. Try to come up with a counter example.

    I just found a better solution which is more elegant using top-down approach. I will give counter examples and post the solution in my next post. Stay tuned.

    VA:F [1.9.22_1171]
    0
  8. 1337c0d3r

    @Anonymous:
    Please read my next post (solution for Anonymous's variant 1) ), I have given a counter example for the maximum increasing contiguous sequence method.

    The second variant mentioned by Anonymous is not clear to me, so I can't tell for sure.

    VA:F [1.9.22_1171]
    0
  9. Anonymous

    I guess this solution can be speed up to lg(n). if a node fails to pass the test w.r.t. left subtree, i.e., isBST = false, there is no need to check the right subtree.

    VA:F [1.9.22_1171]
    0
  10. Anonymous

    what about this top down approach ?

    int max_len = -1;
    node *max_node = NULL;

    int longestbst(node *root, int min, int max)
    {
    if(!root)
    return 0;

    if(root->data < min || root->data > max)
    {
    longestbst(root,INT_MIN, INT_MAX);
    return -1;
    }
    int llen = longestbst(root->left, min, root->data);
    int rlen= longestbst(root->right, root->data +1, max) ;

    if(llen == -1 || rlen == -1)
    {
    return -1;
    }

    if((llen + rlen +1) > max_len)
    {
    max_len = llen + rlen +1;
    max_node = root;
    }
    return llen + rlen + 1;
    }

    VA:F [1.9.22_1171]
    0
  11. Shashank Mani Narayan

    you have 2-d array, with m length and n width.

    You are also given k, ( k<=n && k<=m ). Now, select a square of size k, which returns maximum sum.

    VA:F [1.9.22_1171]
    0
  12. Algoseekar

    @ihas1337 Code ..Awesome man You Doing Excellent Job..My Very Best Wishes to you..Keep Helping Us..One Day I will B like You …thnx a lot

    VA:F [1.9.22_1171]
    +1
  13. SK

    For the naive approach:

    For each node, you would call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then we have to continue examining its left and right child. If only one of the subtrees is BST, then we can return that subtree.

    How do you justify this ? If the number of nodes in left subtree is 5 while the number of nodes in right subtree is 1000, it is highly likely that deep down under the right subtree, there can be a BST with number of nodes > 5. Hence, we can’t return as soon as we find one of the subtrees to be a BST.

    VA:F [1.9.22_1171]
    0
  14. Adrian M

    my Java version:

    VA:F [1.9.22_1171]
    0
    1. yifeng

      that’s not right for your solution. for BST, the current node’s value must be larger than the max value of left tree and smaller than the min value of right tree. In java, we need some static variables to do that.

      VA:F [1.9.22_1171]
      0
  15. aimless

    @Elite (1337c0d3r)
    I think you need to revisit your proposed solution once, though didn’t try coding and running it, but by seeing the code it seems that after you have checked the condition
    if (isBST) {
    min = currMin;
    max = currMax;
    int totalNodes = leftNodes + rightNodes + 1;
    if (totalNodes > maxNodes) {
    maxNodes = totalNodes;
    largestBST = p;
    }
    return totalNodes;
    } else {
    return -1; // This subtree is not a BST
    }

    you ignored the possibility that right or left subtree can still be max BST subtree.

    After reading the question, I had thought the solution just by extending your BST checking algo and here is the code, its working fine for me
    //====================================================
    bool MaxBST(Node *root, int *count, Node **maxNode, int min, int max)
    {
    if(!root)
    {
    *count = 0;
    *maxNode = root;
    return true;
    }

    Node* leftMax = NULL;
    Node* rightMax = NULL;
    int leftCount = 0, rightCount = 0;
    bool leftIsBST = MaxBST(root->left, &leftCount, &leftMax, min, root->val);
    bool rightIsBST = MaxBST(root->right, &rightCount, &rightMax, root->val, max);

    if(leftIsBST && rightIsBST && minval && max >=root->val)
    {
    *count = leftCount + rightCount + 1;
    *maxNode = root;
    return true;
    }
    else
    {
    *maxNode = (leftCount > rightCount) ? leftMax : rightMax;
    *count = (leftCount > rightCount) ? leftCount : rightCount;
    return false;
    }
    }
    //====================================

    call it as
    int count = 0; //number of node is max subtree
    Node *maxNode = NULL: //max subtree node shall be returned in this variable
    MaxBST(root, &count, &maxNode, INT_MIN, INT_MAX)

    VA:F [1.9.22_1171]
    0
  16. aimless

    if(leftIsBST && rightIsBST && min val && max >= root->va l) //<<< rightCount) ? leftMax : rightMax;
    *count = (leftCount > rightCount) ? leftCount : rightCount;
    return false;
    }

    VA:F [1.9.22_1171]
    0
  17. aimless

    i think there is some mess up happening and operators are being confused as HTML tags. i tried posting the correction but its more messed up. anyway i hope you got the idea, second “if” condition in my code, checks if value is between MAX and MIN, just like BST checking code.

    VA:F [1.9.22_1171]
    0
    1. anonymous

      Your code is not CORRECT. Check it with few input at least (before posting it here). For below input, it shows 4 (right subtree of root), where as ans is 6 (left subtree of root)

      Tree *root = new Tree(20);
      root->left = new Tree(20);
      root->right = new Tree(40);
      root->left->left = new Tree(10);
      root->left->right = new Tree(25);
      root->right->left = new Tree(35);
      root->right->right = new Tree(50);
      root->left->left->left = new Tree(5);
      root->left->left->right = new Tree(15);
      root->left->right->right = new Tree(28);
      root->right->right->left = new Tree(41);

      VA:F [1.9.22_1171]
      0
      1. aimless

        @anonymous: i am sorry! for your disappointment and i understand it. i react to such situations in almost similar ways and had done that in this forum too. i did check my code (before posting) with some inputs, yet i missed a bug. thanks for pointing out the issue. i have CORRECTED the approach and re-posted it here:
        http://ideone.com/cPG29

        LOGIC: start building BST bottoms up instead of(unlike my last approach) canceling the one which doesn’t adhere to be a BST based on the limits set by parent nodes.

        Following are the inputs i had used to test my old code (http://ideone.com/TyfDs)
        INPUT 1:
        root = createNode(4);
        root->left=createNode(2);
        root->left->left=createNode(1);
        root->left->right=createNode(3);
        root->right=createNode(5);
        INPUT2:
        root = createNode(10);
        root->left=createNode(5);
        root->left->left=createNode(1);
        root->left->right=createNode(8);
        root->right=createNode(15);
        root->right->right=createNode(7);
        root->left->left->left=createNode(19);
        root->right->right->right=createNode(29);

        here is my updated code:
        http://ideone.com/cPG29

        it is checked with above two and a third input mentioned above by @anonymous.

        thanks for challenging the code once again!

        VA:F [1.9.22_1171]
        0
        1. AA

          Still something is missing ..Its not working for this,
          root = createNode(20);
          root->left = createNode(50);
          root->right = createNode(40);
          root->left->left = createNode(10);
          root->left->right = createNode(25);
          root->right->left = createNode(35);
          root->right->right = createNode(50);
          root->left->left->left = createNode(5);
          root->left->left->right = createNode(15);
          root->left->right->right = createNode(28);
          root->left->right->left = createNode(23);
          root->right->right->left = createNode(41);

          giving 4 – 40
          should be 3 -25

          VA:F [1.9.22_1171]
          0
  18. codingC

    Hi,
    I suspect the naive top-down solution you proposed is not right.
    In the case that only one of the subtree is BST, the solution will return the subtree right away. But this is not correct. You still need to traverse the other subtree to find the largest BST subtree. Otherwise, your solution will return the highest BST subtree(with the greatest height), not the largest one.

    VA:F [1.9.22_1171]
    0
    1. aimless

      @codingC: yes you are correct, you may want to check my reply to anonymous above your current post.

      VA:F [1.9.22_1171]
      0
  19. slimboy

    hey 1337coder,
    I did not understand this part of the code

    leftNodes != 0 && p->data <= max

    Why does this condition result in isBST becoming false?

    VA:F [1.9.22_1171]
    0
  20. Nisarg

    I think Min and Max are not getting updated properly..

    We should keep track of max from left subtree and min from right subtree. How is this happening in the above code??

    VA:F [1.9.22_1171]
    0
    1. Prateek Caire

      Yes. Even i think min and max are not getting updated correctly. Possible change in above code is to store min1 and max1 as min and max from left node. And min2 and max2 from right node. Returned min (passed by referenced one) should min = Min(min1, min2). max = Max(max1, max2). rest is correct. great solution..

      VA:F [1.9.22_1171]
      0
  21. Pingback: Largest Subtree Which is a Binary Search Tree (BST) | 口├人人│의 Blog

  22. fzzh24

    For the naive approach, see this counter example

    ______ 30______
    / \
    20 _____60_
    / \ / \
    15 25 ___70 ___ 31
    / \
    __50__ __90__
    / \ / \
    40 60 80 100
    / \ / \
    39 83 95 105

    VA:F [1.9.22_1171]
    0
  23. fzzh24

    For the naive approach, see this counter example

    …………._______30______
    ………../………………………..\
    …..20………………….._____60_
    …./…..\………………./…………….\
    .15…..25……….___70___……….31
    …………………./……………\
    …………….__50__………__90__
    ……………/………..\……./………..\
    ………….40………..60..80………100
    …………./………………….\………./….\
    …………39………………..83…..95….105

    VA:F [1.9.22_1171]
    0
  24. AA

    Original solution does not work for data here..

    http://www.ideone.com/GUGiZ

    BinaryTree *root = NULL;
    root = createNode(20);
    root->left = createNode(50);
    root->right = createNode(40);
    root->left->left = createNode(50);
    root->left->right = createNode(25);
    root->right->left = createNode(35);
    root->right->right = createNode(50);
    root->left->left->left = createNode(5);
    root->left->left->right = createNode(15);
    root->left->right->right = createNode(28);
    root->left->right->left = createNode(23);
    root->right->right->left = createNode(41);

    return root;

    should be 25 , 3
    gives 40, 4

    VA:F [1.9.22_1171]
    0
  25. swathi

    In the else case has to be modified…

    ——7
    —2—10
    -3–8

    if (isBST)
    {
    // as it is.. (explained in the above code)
    }
    else
    {
    // I think we need to set the min and max to p->data?
    min = p->data;
    max = p->data;
    return -1; // This subtree is not a BST
    }

    VA:F [1.9.22_1171]
    0
  26. Balaji

    Looking at the signature of the method can someone tell me what is the significance of “BinaryTree *& largerstBST”… I thought just a pointer should suffice.. what is with “&*”
    int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,
    int &maxNodes, BinaryTree *& largestBST)

    VN:F [1.9.22_1171]
    0
  27. reader

    @1337c0d3r:
    Nice solution.
    One question. This will always return the left-most node as the largest BST for any input that is not a BST.Is this the desired result for this question?

    VA:F [1.9.22_1171]
    0
  28. Eugene

    seems the naive way is not correct, and I can’t get the complexity nlogn either, for complete tree, for every layer the problem size will shrink by half, cuz you can find a full BST in every layer, so it’s actually n+n/2+n/4+n/4+n/8+n/8+…, the result should be n??

    VN:F [1.9.22_1171]
    0
  29. Pingback: Find largest sub-BST in a binary tree « Hey

  30. Prateek Caire

    Slight modification of your code. correcting min , max

    VA:F [1.9.22_1171]
    0
  31. Barney

    grunt explanation of why the above code works from basic pseudo code.

    #if 0

    Logic used:
    ===========
    1. Current node forms a BST if:
    a. left subtree is BST or NULL
    b. right subtree is BST or NULL
    c. root->key > (left subtree).max value
    d. root->key < (right subtree).min value
    2. Leaf node is treated as a BST of size 1
    Leaf node is identified by 2 NULL subtrees.
    3. If current node is a BST, pass it up
    If not pass up the largest BST between left and right subtree

    Data required from each subtree (recursion level):
    1. isBST << is the subtree a BST
    2. max << max value of the subtree
    3. min << min value of the subtree
    4. largestbstsize << size of largest BST contained in the subtree
    5. largestbst << pointer to largest BST contained in the subtree
    6. isNULL << is the subtree a NULL subtree
    Data passed to each subtree (recursion level):
    1. root < input params
    o. => o/p return value right
    l. => left

    (o.isBST, o.min, o.max, o.largestbstsize, o.largestbst, o.isNULL) returned from LBST() taking (i.root)
    {
    if NULL == i.root {
    o.isNULL = true
    o.largestbstsize = 0
    return;
    } else
    o.isNULL = false

    l.(isBST, isNULL, max, min, largestbst, largestbstsize) left)
    r.(isBST, isNULL, max, min, largestbst, largestbstsize) right)

    // Extract Min and Max values
    // if left subtree exists, inherit smallest node, else current node is smallest
    o.min = (l.isNULL)?i.root->key:l.min
    // if right subtree exists, inherit largest node, else current node is largest
    o.max = (r.isNULL)?i.root->key:r.max

    // set o.isBST
    // if we are leaf node mark bst as true
    // if left is bst and right is bst and current node is in order
    // if left is NULL and right is BST
    // if right is NULL and left is BST
    if (l.isNULL || (l.isBST && i.root->key > l.max)) &&
    (r.isNULL || (r.isBST && i.root->key r.largestbstsize)?l.largestbst:r.largestbst;
    }
    }

    pseudo code optimisation (reducing stack usage):
    ===============================================
    Iteration 1 uses approx 3(l,r,o)*6(struct elems) => 18 state variables per stack level.
    Also return stack values => copying entire struct on each return call.

    1) iteration1 flow
    if root==NULL {
    o.isNULL=true;
    o.largestbstsize = 0;
    return;
    }

    l.(isBST, isNULL, max, min, largestbst, largestbstsize) left)
    r.(isBST, isNULL, max, min, largestbst, largestbstsize) right)

    o.min = (l.isNULL)?i.root->key:l.min
    o.max = (r.isNULL)?i.root->key:r.max

    o.isBST = ((l.isNULL || (l.isBST && i.root->key > l.max)) && (r.isNULL || (r.isBST && i.root->key r.largestbstsize)?l.largestbst:r.largestbst;
    }

    2) Rearranging statements to resue same variable for left and right
    step1: rearrange statements to group “l” and “r”
    note
    o.isBST = (x && y)?:true:false;
    is equivalent to
    o.isBST = !(x && y)?:false:true;
    is equivalent to
    o.isBST = (!x || !y)?:false:true;
    is equivalent to
    o.isBST = true;
    if !x o.isBST = false;
    if !y o.isBST = false;

    o.isBST = true;
    if root==NULL {
    o.isNULL=true;
    o.largestbstsize = 0;
    return;
    }

    l.(isBST, isNULL, max, min, largestbst, largestbstsize) left)
    if !(l.isNULL || (l.isBST && i.root->key > l.max))
    o.isBST = false
    o.min = (l.isNULL)?i.root->key:l.min

    r.(isBST, isNULL, max, min, largestbst, largestbstsize) right)
    if !(r.isNULL || (r.isBST && i.root->key key:r.max

    if (o.isBST) {
    // we are the largest subtree @ this level
    o.largestbstsize = l.largestbstsize + r.largestbstsize + 1;
    o.largestbst = i.root;
    } else {
    // pass up the largest subtree so far
    o.largestbstsize = max(l.largestbstsize, r.largestbstsize)
    o.largestbst = (l.largestbstsize > r.largestbstsize)?l.largestbst:r.largestbst;
    }

    step2: replace l and r with same variable “lr”

    if root==NULL {
    o.isNULL=true;
    o.largestbstsize = 0;
    return;
    }
    o.isBST = true;

    lr.(isBST, isNULL, max, min, largestbst, largestbstsize) left)
    if !(lr.isNULL || (lr.isBST && i.root->key > lr.max))
    o.isBST = false
    o.min = (l.isNULL)?i.root->key:l.min

    lr.(isBST, isNULL, max, min, largestbst, largestbstsize) right)
    if !(lr.isNULL || (lr.isBST && i.root->key key:lr.max

    if (o.isBST) {
    // we are the largest subtree @ this level
    o.largestbstsize = l.largestbstsize + r.largestbstsize + 1;
    o.largestbst = i.root;
    } else {
    // pass up the largest subtree so far
    o.largestbstsize = max(l.largestbstsize, r.largestbstsize)
    o.largestbst = (l.largestbstsize > r.largestbstsize)?l.largestbst:r.largestbst;
    }

    reduced 1*6 elems and added 2 new variables (l_xxx) => reduction of 4.
    Total is 14.

    3)use global variable (or top of recursion stack variable) to store the largestbst
    instead of passing up recursion chain purely via stack variables.
    g_largestbst, g_largestbstsize => accumulated across recursions
    so we dont need to store largestbst.
    and we can replace largestbstsize with just size (of the current tree if BST)

    if root==NULL {
    o.isNULL=true;
    o.size = 0;
    return;
    }
    o.isBST = true;

    lr.(isBST, isNULL, max, min, size) left)
    lsize = lr.size;
    if !(lr.isNULL || (lr.isBST && i.root->key > lr.max))
    o.isBST = false
    o.min = (l.isNULL)?i.root->key:l.min

    lr.(isBST, isNULL, max, min, size) right)
    rsize = lr.size;
    if !(lr.isNULL || (lr.isBST && i.root->key key:lr.max

    if (o.isBST) {
    // we are the largest subtree @ this level
    o.size = lsize + rsize + 1;
    if (g_largestbstsize isNULL && isBST
    size == -1 => !isBST
    size >= 1 => isBST
    we dont have to return isBST.
    Please Note
    !(lr.isNULL || (lr.isBST && i.root->key key > lr.min)))

    if root==NULL {
    o.size = 0;
    return;
    }
    isBST = true;

    lr.(max, min, size) left)
    lsize = lr.size;
    if !((lr.size == 0) || ((lr.size>=0) && i.root->key > lr.max))
    isBST = false
    o.min = (lr.size == 0)?i.root->key:l.min

    lr.(max, min, size) right)
    rsize = lr.size;
    if !((lr.size == 0) || ((lr.size>=0) && i.root->key key:lr.max

    if (isBST) {
    // we are the largest subtree @ this level
    o.size = lsize + rsize + 1;
    if (g_largestbstsize tree is not BST)
    Unless at some level of unwinding, we start building recursion again (walking down another subtree)
    We cache the min from left and max from right into local variables before overwriting the global min, max
    with a recursion call.
    Since we use global variables (or top of recursion stack variable), remove max/min from return context
    This way we replace min/max from each side with min/max @ just our level.
    Note
    !((lsize == 0) || ((lsize>=0) && i.root->key > g_max))
    is equivalent to
    (!(lsize == 0) && (!(lsize>=0) || (i.root->key key key key <= g_max))

    if root==NULL {
    return 0;
    }
    isBST = true;

    lsize left)

    if !((lsize == 0) || ((lsize>=0) && i.root->key > g_max))
    isBST = false
    curmin = (lsize == 0)?i.root->key:g_min

    rsize right)
    if !((rsize == 0) || ((rsize>=0) && i.root->key key:g_max

    if (isBST) {
    // we are the largest subtree @ this level
    size = lsize + rsize + 1;
    if (g_largestbstsize 6

    #endif

    //code iteration 1:
    //=================
    // Direct implementation of pseudocode
    // needs large stack space per iteration
    // not all return variables are set at the time
    struct lbst_op {
    int isBST;
    int isNULL;
    int min;
    int max;
    int largestbstsize;
    bnode *largestbst;
    };

    #define true 1
    #define false 0

    struct lbst_op LBST1(bnode *root)
    {
    struct lbst_op o, l, r;

    if (NULL == root) {
    o.isNULL = true;
    o.largestbstsize = 0;
    return o;
    }
    else {
    o.isNULL = false;
    }

    l = LBST1(root->left);
    r = LBST1(root->right);

    // Extract Min and Max values
    // if left subtree exists, inherit smallest node, else current node is smallest
    o.min = (l.isNULL)?root->key:l.min;
    // if right subtree exists, inherit largest node, else current node is largest
    o.max = (r.isNULL)?root->key:r.max;

    // set o.isBST
    // if we are leaf node mark bst as true
    // if left is bst and right is bst and current node is in order
    if((l.isNULL || (l.isBST && (root->key > l.max))) &&
    (r.isNULL || (r.isBST && (root->key r.largestbstsize)?l.largestbstsize:r.largestbstsize;
    o.largestbst = (l.largestbstsize > r.largestbstsize)?l.largestbst:r.largestbst;
    }

    return o;
    }

    //code iteration 2:
    //=================
    // instead of global variable, we are using top of recursion stack variable

    int _LBST2(bnode *root, int *min, int *max, bnode **largestbst, int *largestbstsize)
    {
    int lsize, rsize, isBST, curmin, curmax, size;

    if (root==NULL)
    return 0;
    isBST = true;

    lsize = _LBST2(root->left, min, max, largestbst, largestbstsize);
    if (!((lsize == 0) || ((lsize>=0) && (root->key > *max))))
    isBST = false;
    curmin = (lsize == 0)?root->key:*min;

    rsize = _LBST2(root->right, min, max, largestbst, largestbstsize);
    if (!((rsize == 0) || ((rsize>=0) && (root->key key:*max;

    if (isBST) {
    // we are the largest subtree @ this level
    size = lsize + rsize + 1;
    if (*largestbstsize < size) {
    *largestbstsize = size;
    *largestbst = root;
    }

    *min = curmin;
    *max = curmax;
    return size;
    }
    else
    return -1;
    }

    bnode *LBST2(bnode *root)
    {
    bnode *largestbst;
    int min,max,largestbstsize=INT_MIN;

    _LBST2(root, &min, &max, &largestbst, &largestbstsize);
    return largestbst;
    }

    VN:F [1.9.22_1171]
    0
  32. Barney

    VN:F [1.9.22_1171]
    0
  33. Peter Wang

    The min and max is not correctly used in the solution code. just make a simple tree:

    when it traverse to subtree 3, the min is 1 max is 3, but the code will say it is not BST since p->data >= min

    VN:F [1.9.22_1171]
    0
  34. shivi

    can’t we use postorder traversal and return the max and min up the tree.
    is it necessary to use inorder like u have used…
    can u post a post order solution to the same problem pls!

    VA:F [1.9.22_1171]
    0
  35. luffy88

    int noOfNodes;

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

    VN:F [1.9.22_1171]
    0
  36. luffy88

    Sorry, posted this in a hurry, missed setting noOfNodes in last line. We can change last line ::

    return (leftSubtreeNodes > rightSubtreeNodes) ? leftLargestBST : rightLargestBST;

    to ::

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

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

    VN:F [1.9.22_1171]
    0
      1. luffy88

        Formatted code :

        VN:F [1.9.22_1171]
        +1
  37. Pingback: 自底向上遍历树避免重复计算 | xiangcaohello

Leave a Reply

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

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

*