CODEWITHSUNDEEP
javarecursionbooleanbinary-treebinary-search-tree
TomTom
TomTom

Reputation: 2930

Alternative to boolean recursion

I can't seem to think of a way to solve this. At least not an elegant way. The function should determine if a given tree is a binary search tree. It seems to work (no duplicates are allowed now though).

This is where the function starts:

isBinarySearchTree(root)

Function:

public static boolean isBinarySearchTree(Node node) {

    if (node.leftchild != null) {
        if (node.leftchild.key < node.key)
            isBinarySearchTree(node.leftchild);
        else {
            System.out.println("false: " + node + " -> " + node.leftchild);
            return false;
        }
    }

    if (node.rightchild != null) {
        if (node.rightchild.key > node.key)
            isBinarySearchTree(node.rightchild);
        else {
            System.out.println("false: " + node + " -> " + node.rightchild);
            return false;
        }
    }

    return true;
}

Obviously there is something wrong with the way I want to return. This would work if all the boolean return values would be in a logical && chain. The return value should only be true if all return values are true.

How would I have to rewrite the function to work like that? Or is it even possible?

Upvotes: 2

Views: 351

Answers (3)

rakesh99
rakesh99

Reputation: 1266

        public static boolean isBinarySearchTree(Node node) {

         if(node==null)
            return false;
         if(node.left!=null &&node.key <node.left||node.right!=null &&node.key >node.right)
        return false;
    if((getMax(node.left)>getMin(node.right)) //Left subtree should not have a value which larger than min in right subtree
     return false;
//check recurisvely left and right subtrees
     if(!(isBinarySearchTree(node.left)&&isBinarySearchTree(node.right)))
     return false;

     return true;

Upvotes: 0

Edward Doolittle
Edward Doolittle

Reputation: 4100

You need to logically AND the results of your test on the left and test on the right, and return the result, something like return (leftnode == null || (leftnode.key < key && isBinarySearchTree(leftnode))) && (rightnode == null || (key < rightnode.key && isBinarySearchTree(rightnode)));. It might be clearer to break that into several lines, though.

Upvotes: 0

Neumann
Neumann

Reputation: 761

This should work, I guess :

public static boolean isBinarySearchTree(Node node, int key) {
    if (node.leftchild != null && node.leftchild.key < key || node.rightchild != null && node.rightchild.key > key) {
        return false;
    } else {
        return (node.leftchild != null ? isBinarySearchTree(node.leftchild, node.leftchild.key) : true) && (node.rightchild != null ? isBinarySearchTree(node.rightchild, node.rightchild.key) : true);
    }
}

Upvotes: 1

Related Questions