Question

CAN SOMEONE HELP!

The following problem is to design an algorithm which check if a binary tree is a binary search tree. The following code was given. There exists a bug in this code for the variable last printed. (20 points) 6. Find the bug and provide a way to fix this bug: public static Integer last printed-null: public static boolean checkBST (TreeNode n) if (nnull) return true // check/ recurse left if (checkBST (n.left)) return false; /I check current íf( last-printed !ㅡ null “ n.data <-last-printed) { return false; //check / recurse right if (checkBST (n.right)) return false; return true

Answer 1

Without passing minimum value and maximum value you can't do it in an efficient manner. So by passing this one you can do it efficiently.

boolean isBST() {

        return isBSTUtil(root, Integer.MIN_VALUE,

                               Integer.MAX_VALUE);

    }

  

    /* Returns true if the given tree is a BST and its

      values are >= min and <= max. */

    boolean isBSTUtil(Node node, int min, int max)

    {

        /* an empty tree is BST */

        if (node == null)

            return true;

  

        /* false if this node violates the min/max constraints */

        if (node.data < min || node.data > max)

            return false;

  

        /* otherwise check the subtrees recursively

        tightening the min/max constraints */

        // Allow only distinct values

        return (isBSTUtil(node.left, min, node.data-1) &&

                isBSTUtil(node.right, node.data+1, max));

    }