# Refactoring code finding if Binary Tree is BST

I have written an code to find if a given tree is a BST. Need help in refactoring it. Some of the things I am looking are.

1. Getting Rid of temp variables (As suggested by Martin Fowler)
2. Combining leftTreeMax and RighTreeMin methods
3. Better naming of methods.

Also it will be great if someone can suggest other refactorings which i can do.

``````package com.cc.bst;

import com.cc.queue.Queue;
import com.cc.trees.BinaryTreeNode;

public class IsBinaryTreeBST {

public static boolean binaryTreeBST ( BinaryTreeNode root) {

if (root == null) {
return false;
}
int maxVal = leftTreeMax(root.getLeft());
int minVal = rightTreeMin(root.getRight());
int rootVal = root.getData();

if (maxVal == 0 || minVal == 0 ) {
return false;
}

if (rootVal > maxVal && rootVal < minVal) {
return true;
}

return false;

}

private static int leftTreeMax (BinaryTreeNode node) {

if (node == null) {
return 0;
}
Queue nodeQueue = new Queue();
nodeQueue.enqueue(node);
int maxValue = node.getData();

while (!nodeQueue.isEmpty()) {
BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();
BinaryTreeNode left = tempNode.getLeft();
BinaryTreeNode right = tempNode.getRight();

if (left != null ) {
if (left.getData() > tempNode.getData()) {
return 0;
}
nodeQueue.enqueue(left);
}
if (right != null) {
if ( tempNode.getData() > right.getData()) {
return 0;
}
nodeQueue.enqueue(right);
}
if (tempNode.getData() > maxValue) {
maxValue = tempNode.getData();
}
}
System.out.println("---------- maxVal -------->" +  maxValue);
return maxValue;
}

private static int rightTreeMin(BinaryTreeNode node) {

if (node == null) {
return 0;
}
Queue nodeQueue = new Queue();
nodeQueue.enqueue(node);
int minValue = node.getData();

while (!nodeQueue.isEmpty()) {
BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();
BinaryTreeNode left = tempNode.getLeft();
BinaryTreeNode right = tempNode.getRight();
System.out.println("---------- tempNode -------->" + tempNode.getData());

if (left != null ) {
System.out.println("---------- left -------->" + left.getData());

if (left.getData() > tempNode.getData()) {
return 0;
}
nodeQueue.enqueue(left);
}
if (right != null) {
if ( tempNode.getData() > right.getData()) {
return 0;
}
System.out.println("---------- right -------->" + right.getData());

nodeQueue.enqueue(right);
}
if (tempNode.getData() < minValue) {
minValue = tempNode.getData();
}
}
System.out.println("---------- minVal -------->" +  minValue);

return minValue;
}

}
``````
-
You're returning 0 as a flag that the level failed (and thus the tree is not a BST). That's problematic though since 0 is a possible value. –  Corbin Sep 21 '12 at 7:27

1) You would like to get rid of the `System.out.println()` inside methods. Noone expects a method to write to the console unless the method has `print` in the name.

2) Just comparing the `root` with `left tree max` and `right tree min` can lead to wrong result. Consider,

``````    12
/  \
9    15
/ \
3   5
``````

Here the left sub-tree is not a BST but `12 > 9` and `15 > 12`. You must also ensure that `left-subtree` and `right-subtree` of `root` are also `BST`.

3) `BinaryTreeBST` is kind of redundant. Consider naming the class `IsBSTCheck` or `IsBinarySearchTreeCheck`. Also change the method name `binaryTreeBST` to `isBST` or `isBinarySearchTree` to reflect what the method does.

-