Check if a Binary Tree <String> is aBinary Search Tree

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 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 ; 
}

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 ` 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  boolean isBST(BinaryTree tree) {
        ...
    }
}

Alternatively,

public class BSTVerifier {
    public boolean isBST(BinaryTree tree) {
        ...
    }
}

StackExchange Code Review Q#25036, answer score: 4