Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

i'm understanding the question but wanna make sure if my implementation is correct or not =|

The Q is :

Write a method that accepts as its argument a BinaryTree object and returns true if the argument tree is a binary search tree. Examine each node in the given tree only once

This is my implementation java code :

public boolean isBST (BinaryTree<String> tree)
{
    BinaryNode Node = new BinaryNode (tree.getRootData);
    if(tree == null || Node.isLeaf() ) 
        return true;

    if(Node.getData > Node.getLeftChild && Node.getData < Node.getRightChild)
    {
        boolean leftTree = isBST(new BinaryTree(Node.getLeftChild));
        boolean rightTree = isBST(new BinaryTree(Node.getRightChild));
        return leftTree && rightTree ;
    } 
    else return false ; 
}
share|improve this question

2 Answers

up vote 0 down vote accepted

As mariosangiorgio already said, the concept looks good, with some small improvements possible.

You should write some tests to test it. You would easily find out the mentioned problems with some good tests.

To get you an idea of a fixed version, a typical implementation could look like:

public boolean isBinarySearchTree(BinaryTree tree)
{
    if (tree == null)
        throw new IllegalArgumentException("Tree is null");
    return isBinarySearchTree(tree.getRootNode());
}

private boolean isBinarySearchTree(Node node) // note: the name is not completely correct, because we investigate a node now. But for private and together with the other method, it would be fine
{
    if(node == null || node.isLeaf() ) //hint: node == null can only happen in one case, we could remove it here, if we change the other method
        return true;

    if (!(node.getLeftChild().getData().compareTo(node.getData()) <= 0 && 
                         node.getData().compareTo(node.getRightChild().getData()) <= 0))
        return false; // not sorted

    return isBinarySearchTree(node.getLeftChild()) && isBinarySearchTree(node.getRightChild()); 
}

A final suggestion: Avoid abbreviations.

share|improve this answer
Oh @tb- Thank You So Much you helped a lot really i do appreciate it :) , so clear and look so improved . Sure i'll submit this additionally to my code as better extra implementation .. Thanks again ! :) – Sara Apr 12 at 18:31
up vote 1 down vote

Your implementation looks good but I can spot a some flaws in it.

To begin, you check that tree == null after having already dereferenced it at BinaryNode Node = new BinaryNode (tree.getRootData);.

Moreover I'd like more to see an IllegalArgumentException in the case of a null tree rather than getting the true answer.

I don't even get why you create a new BinaryNode. Why can't you use the nodes you already have in the original tree? In your implementation you try to access the left and right children but you never set them before in Node.

share|improve this answer
Thank You so much @mariosangiorgio for your helpful comments :) , and about the last point it's cuz i'm doing the code for a specific ADT classes i got where i cannot access the Node of the Tree unless by calling a getter method which is in BinaryNode class , and for that i need to create an object of BinaryNode class so i can call the getter method and start work on it .. Hope i could explain clear and well !~ – Sara Apr 12 at 18:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.