title: Largest Subtree Which is a Binary Search Tree (BST)
body: <blockquote>
    <p>Given a binary tree, I want to find out the largest subtree which is a
    BST in it.</p>
  </blockquote>
  
  <p>This question is duplicate of <a href="https://stackoverflow.com/questions/2336148/finding-the-largest-subtree-in-a-bst">Finding the largest subtree in a BST</a>, where 1337c0d3r gives a O(n) solution by traversing the tree bottom up. There are two lines code confusing me. Can anyone help me explain it?</p>
  
  <pre><code>// Find the largest BST subtree in a binary tree.
  // If the subtree is a BST, return total number of nodes.
  // If the subtree is not a BST, -1 is returned.
  int findLargestBSTSubtree(BinaryTree *p, int &amp;min, int &amp;max,
                     int &amp;maxNodes, BinaryTree *&amp; largestBST) {
    if (!p) return 0;
    bool isBST = true;
    int leftNodes = findLargestBSTSubtree(p-&gt;left, min, max, maxNodes, largestBST);
    int currMin = (leftNodes == 0) ? p-&gt;data : min;
    if (leftNodes == -1 ||
       (leftNodes != 0 &amp;&amp; p-&gt;data &lt;= max))
      isBST = false;
    int rightNodes = findLargestBSTSubtree(p-&gt;right, min, max, maxNodes, largestBST);
    int currMax = (rightNodes == 0) ? p-&gt;data : max;
    if (rightNodes == -1 ||
       (rightNodes != 0 &amp;&amp; p-&gt;data &gt;= min))
      isBST = false;
    if (isBST) {
      min = currMin;
      max = currMax;
      int totalNodes = leftNodes + rightNodes + 1;
      if (totalNodes &gt; maxNodes) {
        maxNodes = totalNodes;
        largestBST = p;
      }
      return totalNodes;
    } else {
      return -1;   // This subtree is not a BST
    }
  }
  
  BinaryTree* findLargestBSTSubtree(BinaryTree *root) {
    BinaryTree *largestBST = NULL;
    int min, max;
    int maxNodes = INT_MIN;   // INT_MIN is defined in &lt;climits&gt;
    findLargestBSTSubtree(root, min, max, maxNodes, largestBST);
    return largestBST;
  }
  </code></pre>
  
  <p>I've confused by the following two lines code. According to my common sense, after recursive traversing left tree, the <code>max</code> variable should be updated, why putting <code>int currMin = (leftNodes == 0) ? p-&gt;data : min;</code> right after recursive traversing left tree?<br>
  The same question for <code>int currMax = (rightNodes == 0) ? p-&gt;data : max;</code></p>
  
  <pre><code>...
  int currMin = (leftNodes == 0) ? p-&gt;data : min;
  ...
  int currMax = (rightNodes == 0) ? p-&gt;data : max;
  </code></pre>