Check If Tree is BST

Check If Tree is BST

  July 23, 2017    

---

Solution:

If inorder traversal of tree is in an ascending order then it is bst else not.

Here we are checking data with previous node's data instead of saving them in array and compare to save space and execute in O(1) space O(n) time .

Looping with left-root-right as inorder.

Code:

/*  A Binary Search Tree node
class Node
{
    int data;
    Node left, right;
    Node(int item)
    {
        data = item;
        left = right = null;
    }
} */
class hackerranksolutionc
{
    private Node tmp;
    boolean bst(Node root)
    {
        if(root!=null)
        {
            if(!bst(root.left))
            return false;
            if(tmp!=null && root.data<=tmp.data)
            return false;
            tmp=root;
           return bst(root.right);
        }
        return true;
    }
    int isBST(Node root)  
    {
        Node tmp=null;
        return (bst(root)==true)?1:0;
    }
}