current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite
1

I'm understanding the question, but I want to know whether or not my implementation is correct.

The question 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:

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

4 Answers 4

up vote -2 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
up vote 2 down vote

There are some serious problems with this function.

Issues of correctness

  • Code won't compile: If BinaryNode indeed has fields named getData, getLeftChild, and getRightChild that are of type String, then you can't use operators < and > on them. For strings, as with any object, you have to use a.compareTo(b).
  • No consideration for unbalanced or incomplete trees: If a node has only one child, what happens?
  • Check for tree == null after tree.getRootData: There's no point in checking for tree == null, since it would have crashed on tree.getRootData with a NullPointerException already if that were the case.
  • Recursive check is insufficient: As @user2668926 points out, you have to verify that all nodes within a subtree fall within a range of values.

Serious violations of style conventions

  • Using an uppercase variable name: In Java, variable names should be lowerCase, except constants, which should be ALL_CAPS. By naming a variable Node, you hurt readability tremendously by making it look like the name of a class.
  • Using getSomething as field names: The convention is that getSomething() is the name of a getter method (i.e., a member function), usually corresponding to an instance variable named something. Instead, you seem to have instance variables named getRootData, getData, getLeftChild, and getRightChild in your BinaryTree and BinaryNode classes, which is exceedingly weird.

I consider these two issues to be extremely serious, even if the compiler accepts the code and the algorithm runs. These are not "merely" conventions — they are major traps for anyone else who works with your code, enough for every programmer to go facepalm.

Less serious issues of style

  • Distinction between BinaryTree and BinaryNode: Wrapping nodes as trees and unwrapping the tree's root node is cumbersome. Do you really have to make a distinction between trees and nodes? Could you not just treat any node as a tree rooted there?

  • Use of generics: The BinaryTree class is genericized, so your code should also aim to be generic. The method signature should look something like

    public class BSTVerifier {
    public static <T extends Comparable> boolean isBST(BinaryTree<T> tree) {
        ...
    }
}

    Alternatively,

    public class BSTVerifier<T extends Comparable> {
    public boolean isBST(BinaryTree<T> tree) {
        ...
    }
}
share|improve this answer
    
I think that having separate BinaryTree can make sense. You can for example keep Count there and it also means empty collection can work nicely. –  svick Nov 13 '13 at 0:43
    
If there are to be BinaryTree and BinaryNode classes, then I would suggest that the function be made private, and accept a BinaryNode argument. The public function, accepting a BinaryTree, can unwrap the tree's root just once and call the private version. –  200_success♦ Nov 13 '13 at 0:53
up vote 2 down vote

The answers above are very wrong as it is NOT enough to just compare the node data with its left child's and right child's. It should compare the node data with the MAX of the left subtree and compare with the MiN of the right subtree.

The so-called improved one is still very wrong. It should have some way to record the max and min. Check the correct answer from leetcode.

share|improve this answer
2  
Could you provide a link to that correct answer? –  svick Nov 12 '13 at 20:47
    
this is almost a low-quality answer, please elaborate on the information in the first paragraph and please don't point fingers in an answer because you can't down vote, your behavior borders on childish, please provide the better answer and we will up vote the crap out of it. –  Malachi Nov 12 '13 at 23:56
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
1  
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 '13 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.