CC_4_5

BinarySearchTree.java

// Cracking the Coding Interview
// 4.5 Implement a function to check if a binary tree is a binary search tree.

class Node {
	public int val;
	public Node left;
	public Node right;
	Node(int v) {
		val = v;
		left = null;
		right = null;
	}
}

class BinarySearchTree {
	public static boolean isBST(Node root) {
		return isBSTNonRecursive(root);
	}
	private static boolean isBSTNonRecursive(Node root) {
		Node cur = root;
		int prev = Integer.MIN_VALUE;
		while(cur != null) {
			Node predecessor = findPredecessor(cur);
			if (predecessor == null) {
				if (cur.val < prev) {
					return false;
				} else {
					prev = cur.val;
				}
				cur = cur.right;
			} else {
				if (predecessor.right == cur) {
					prev = predecessor.val;
					if (cur.val < prev) {
						return false;
					} else {
						prev = cur.val;
					}
					predecessor.right = null;
					cur = cur.right;
				} else {
					predecessor.right = cur;
					cur = cur.left;
				}
			}
		}
		return true;
	} 
	private static Node findPredecessor(Node root) {
		if (root == null || root.left == null) return null;
		Node cur = root.left;
		while(cur.right != null && cur.right != root) {
			cur = cur.right;
		}
		return cur;
	}
	public static void main(String[] args) {
		Node root = new Node(0);
		assert isBST(root);
		root.left = new Node(1);
		assert !isBST(root);
		root.left.val = -2;
		assert isBST(root);
		root.right = new Node(1);
		root.right.right = new Node(-1);
		assert !isBST(root);
		root.right.right.val = 10;
		assert isBST(root);
		root.right.right.right = new Node(12);
		root.right.right.left = new Node(9);
		root.left.right = new Node(-1);
		assert isBST(root);

		System.out.println("Tests Passed");


	}
}