CareerCup

Just check it for BST ..

public boolean isBST() {
        return isBST(root, null, null);
    }

   private boolean isBST(Node x, Key min, Key max) {
        if (x == null) return true;
        if (min != null && x.key.compareTo(min) <= 0) return false;
        if (max != null && x.key.compareTo(max) >= 0) return false;
        return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
    }

Or you could do a inorder traversal, if all the nodes are in ascending order, then it is sorted. Here prev is used to record the node visited previously.

private TreeNode prev = null;
public boolean isSorted(TreeNode head){
    if(head == null){
        return true;
    }
    if(!isSorted(head)){
        return false;
    }
    if(prev == null){
        prev = head;
    }else{
        if(head.val < prev.val){
            return false;
        }
        prev = head;
    }
    if(!isSorted(head)){
        return false;
    }
    return true;
    
}

Use recursion.

Base case: Leaf is always sorted.
Recursive case: return true if: left subtree is sorted and right subtree is sorted and that root_of_left_subtree < root < root_of_rightsubtree.

Do a Inorder traversal. maintain the prev number and check if current is greater than prev.

//object level variable: int prev = Integer.MIN_VALUE; before this call
	public boolean isSortedAsc(Node root){
		if(root == null)
			return true;
		if(!isSortedAsc(root.lchild))
			return false;
		if(root.value < prev)
			return false;
		prev = root.value;
		return isSortedAsc(root.rchild);
	}

The solution is that each node in BST needs to be in certain range [min, max]

Wikipedia has good solution for this:

public static boolean isBST(TreeNode node, int maxData, int minData) {
    if (node == null)
        return true;
 
    if (node.getData() >= maxData || node.getData() <= minData)
        return false;
 
    return (isBST(node.left, node.getData(), minData) && isBST(node.right, maxData, node.getData()));
}


The initial call to this function can be something like this:


if (isBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE))
    System.out.println("This is a BST.");
else
    System.out.println("This is NOT a BST!");

Essentially we keep creating a valid range (starting from [ MIN_VALUE, MAX_VALUE]) and keep shrinking it down for each node as we go down recursively.

static int max = Integer.MIN_VALUE;
    static boolean sorted = true;
    
    public static void inOrder(BTree t){
        if(t==null) return;
        inOrder(t.left);
        System.out.println(t.num);
        if(t.num<BTree.max){
            sorted = false;
            System.out.println("Out of order at "+t.num);
        }
        BTree.max = t.num;
        inOrder(t.right);
    }

sassdf

do a InOrder Traversal and at every node check the value of previous node. If prev val is greater then this val it means BTree is not sorted.

In-order and then check current with next value. If current is greater then next then not sorted or else it is.

EDIT: Corrected. Thank you ravio.

public class BSTCheck {

static class TreeNode<T> {
    public T val;
    public TreeNode<T> left;
    public TreeNode<T> right;

    public TreeNode() {

    }
    public TreeNode(T x) {
        val = x;
    }
}
    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<Integer>(4);
        root.left = new TreeNode<Integer>(2);
        root.left.left = new TreeNode<Integer>(1);
        root.left.right = new TreeNode<Integer>(3);
        root.right = new TreeNode<Integer>(6);
        root.right.left = new TreeNode<Integer>(5);
        root.right.right = new TreeNode<Integer>(7);
        boolean sorted = isSorted(root);
        System.out.println("Sorted[" + sorted + "]");
    }

    private static boolean isSorted(TreeNode<Integer> root) {
        boolean sorted = isLeftSorted(root);
        sorted &= isRightSorted(root);
        return sorted;
    }

    private static boolean isLeftSorted(TreeNode<Integer> root) {
        return root.left == null || root.left.val < root.val && isSorted(root.left);
    }

    private static boolean isRightSorted(TreeNode<Integer> root) {
        return root.right == null || root.right.val > root.val && isSorted(root.right);
    }
}

Recurse left and make sure left child is less than current node. If the left child is null the default case is to return true since any false will negate the expression as a whole. Do the same to the right children except verifying that the right child is greater than the current node. Same handling of the null right child; return true.

WTF does tree is sorted mean?