java-algorithm-2010/PuzzleCoding/src/IsBST.java at master · xiaoningning/java-algorithm-2010 · GitHub

Repository navigation

History

/**

* determine if a given binary tree is a binary search tree.

public class IsBST {

public static void main(String[] args) {

Node root = new Node(10);

Node node5 = new Node(5);

Node node15 = new Node(15);

Node node6 = new Node(6);

Node node20 = new Node(20);

Node node3 = new Node(3);

Node node12 = new Node(12);

root.insert(node5);

root.insert(node6);

root.insert(node15);

root.insert(node20);

root.insert(node3);

root.insert(node12);

System.out.println(isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));

System.out.println(isBST1(root, Integer.MIN_VALUE));

BTreeIterator treeIterator = new BTreeIterator(root);

while (treeIterator.hasNext()){

Node next = treeIterator.inOrderNext();

System.out.print(next.value + " ");

}

System.out.println();

while (treeIterator.hasNextPostOrder()){

Node next = treeIterator.postOrderNext();

System.out.print(next.value + " ");

}

System.out.println();

treeIterator.reset();

while (treeIterator.hasNextPreOrder()){

Node next = treeIterator.preOrderNext();

System.out.print(next.value + " ");

}

System.out.println();

}

public static boolean isBST(Node node, int min, int max) {

if (node == null) {

return true;

}

if ((min < node.value) && (node.value < max)) {

return isBST(node.left, min, node.value) &&

isBST(node.right, node.value, max);

} else {

return false;

}

public static boolean isBST1(Node node, int prev) {

if (node == null) {

return true;

}

if (isBST1(node.left, prev)) {

if (node.value > prev) {

prev = node.value;

return isBST1(node.right, prev);

} else {

return false;

}

} else {

return false;

}

java-algorithm-2010/PuzzleCoding/src/IsBST.java at master · xiaoningning/java-algorithm-2010 · GitHub

Repository navigation

Expand file tree

Breadcrumbs

IsBST.java

Latest commit

History

Breadcrumbs

IsBST.java

File metadata and controls