GeeksForGeeks - Check if the tree is a binary search tree

link

Problem

Given a binary tree. Check whether it is a BST or not.

Solution

Use recursioin by setting the low and high points

bool helper(Node* root, Node* low, Node* high){
    if(!root){ //ALWAYS base case for tree recursion
        return true;
    }
    if(low && low->data >= root->data){// Base 2 - !low can mean it is left-side node
        return false;
    }
    if(high && high->data <= root->data){
        return false;
    }
    return helper(root->left, low, root) && helper(root->right, root, high);
     // BOTH should be true therefore use &&
     // doesn't need to change low if it moves to the left side (vice versa)
}

bool isBST(Node* root) {
    helper(root, NULL, NULL);
}

Time Complexity : O(logn)