Check if all internal nodes of BST have only one child without building tree.

OneChildNodesBST.java

// http://www.ideserve.co.in/learn/check-if-all-internal-nodes-have-one-child-bst
/*
  If a node - 'currentNode' in BST has only one child then that means all the nodes in BST are either in the left sub-tree of that node or in the right sub-tree. This further implies that all nodes would have values either greater than currentNode or all nodes would have values less than currentNode. Therefore in preorder traversal array all elements appearing after the currentNode would all be either greater than currentNode or less than currentNode. If this condition holds true for all elements of preorder array(except the last element: since that would be element for leaf node) then we can say that all internal nodes of BST have only one child.
*/
class OneChildNodesBST 
{
    private int minimum(int a, int b)
    {
        if (a < b) return a;
        return b;
    }
 
    private int maximum(int a, int b)
    {
        if (a > b) return a;
        return b;
    }
 
    public boolean checkOneChildNodesBST(int[] preorder)
    {
        int maxSoFar = preorder[preorder.length - 1], minSoFar = preorder[preorder.length - 1];
         
        /*
         *  check if all elements in the sub-array from [i+1 to end] of the array 
         *  are less than current element - preorder[i]. If not, all these elements should
         *  be greater than the current element.  
         */
        for (int i = preorder.length - 2; i >= 0; i--)
        {
            System.out.println(" min= " +minSoFar + " max= " + maxSoFar + " array = " + preorder[i]);
            if( !(      
                        ((preorder[i] > maxSoFar) && (preorder[i] > minSoFar)) 
                     || ((preorder[i] < maxSoFar) && (preorder[i] < minSoFar))
                 )
              )
            {
                System.out.println(" Break min= " +minSoFar + " max= " + maxSoFar + " array = " + preorder[i]);
                System.out.println(" First " + ((preorder[i] > maxSoFar) && (preorder[i] > minSoFar)));
                System.out.println(" Second " + ((preorder[i] < maxSoFar) && (preorder[i] < minSoFar)));
                System.out.println(" Final " + (((preorder[i] > maxSoFar) && (preorder[i] > minSoFar)) 
                     || ((preorder[i] < maxSoFar) && (preorder[i] < minSoFar))));
                return false;
            }
            maxSoFar = maximum(preorder[i], maxSoFar);
            minSoFar = minimum(preorder[i], minSoFar);
        }
        return true;
    }
 
    public static void main(String[] args)
    {
        OneChildNodesBST solution = new OneChildNodesBST();
         
        //int[] preorderTree1 = {20, 10, 11, 13, 12};
        //int[] preorderTree1 = {9, 8, 5, 7, 6};
        int[] preorderTree1 = {8, 5, 4, 7, 6};
         
        System.out.println("Check if evry internal node of this BST has only one child:\n" + solution.checkOneChildNodesBST(preorderTree1));
    }
}