// Link: http://www.ardendertat.com/2011/10/10/programming-interview-questions-7-binary-search-tree-check/

// Problem: Given a binary tree, check whether it’s a binary search tree or not.

// Notes:

//    - It's not enough to check if left < root < right. Root shoud be less (or greater) that ALL its left (right) nodes.

​

using System;

public class BT

{

    public int data;

    public BT left;

    public BT right;

    public BT(int root){

        this.data = root;

        this.left = null;

        this.right = null;

    }

    public BT(int root, int left, int right){

        this.data = root;

        this.left = new BT(left);

        this.right = new BT(right);

    }

    public string PrintBT(){

        string leftStr = "";

        if (left != null)

            leftStr = left.PrintBT();

        string rightStr = "";

        if (right != null)

            rightStr = right.PrintBT();

        return  leftStr + "-" + data + "-" + rightStr;

    }

}

​

public class Program

{

    public static void Main()

    {

        BT t = new BT(3);

        t.left = new BT(2,1,4);

        t.right = new BT(5);

        Console.WriteLine(t.PrintBT());

        Console.WriteLine(IsBST(t, int.MinValue, int.MaxValue));

        BT t2 = new BT(40);

        t2.left = new BT(30,25,35);

        t2.right = new BT(50,45,60);

        Console.WriteLine(t2.PrintBT());

        Console.WriteLine(IsBST(t2, int.MinValue, int.MaxValue));

    }

    public static bool IsBST(BT tree, int min, int max){

        if (tree == null)

            return true;

        if (tree.data < min || tree.data > max)

            return false;

        return IsBST(tree.left, min, tree.data-1) && IsBST(tree.right, tree.data+1, max);

    }

}