/* A binary tree is a binary search tree, if and only if: - The left subtree of a node contains only nodes with keys less than the node's key. - The right subtree of a node contains only nodes with keys greater than the node's key. - Both the left and right subtrees must also be binary search trees. - There must be no duplicate nodes. */ public boolean isBinarySearchTree() { HashMap map = new HashMap(); return !hasDuplicateItem(map) && this.isBinarySearchTreeRecursive(); } private boolean isBinarySearchTreeRecursive() { if (this.left != null) { if ((this.left.value > this.value) || (this.left.max() > this.value)) { return false; } if (!this.left.isBinarySearchTreeRecursive()) { return false; } } if (this.right != null) { if ((this.right.value map) { if (map.containsKey(this.value)) { return true; } map.put(this.value, null); return ((this.left != null && this.left.hasDuplicateItem(map)) || (this.right != null && this.right.hasDuplicateItem(map))); } public int max() { int leftMax = (this.left == null) ? Integer.MIN_VALUE : this.left.max(); int rightMax = (this.right == null) ? Integer.MIN_VALUE : this.right.max(); return Math.max(this.value, Math.max(leftMax, rightMax)); } public int min() { int leftMin = (this.left == null) ? Integer.MAX_VALUE : this.left.min(); int rightMin = (this.right == null) ? Integer.MAX_VALUE : this.right.min(); return Math.min(this.value, Math.max(leftMin, rightMin)); }