Binary Search Tree Problem

Given a binary tree, check if it is a binary search tree (BST). A valid BST does not have to be complete or balanced.

Consider the below definition of a BST:

1. All nodes values of left subtree are less than or equal to parent node value
2. All nodes values of right subtree are greater than or equal to parent node value
3. Both left subtree and right subtree must be a BST
4. By definition, NULL tree is a BST
5. By definition, trees having a single node or leaf nodes are BST.

‍Example One

Input:

Output: false

Left child value 200 is greater than the parent node value 100; violates the definition of BST.

Example Two

Input:

Output: true

Notes

Input Parameters: There is only one argument named root denoting the root of the input tree.

Output: Return true if the input tree is a BST or false otherwise

Constraints:

• 0 <= number of nodes <= 100000
• -10^9 <= values stored in the nodes <= 10^9
• Return value must be boolean

Solutions

We provided two solutions, both are optimal in terms of time and space complexity, though algorithms are different.

1) other_solution.cpp:

In the following three examples, tree A and B is a BST, where tree C is not:

In other_solution.cpp we use the definition of BST quite literally. For every node, recursively, we check that all values in the left subtree are <= current node value and all values in the right subtree are >= current node value. We also propagate all the “<=” and “>=” conditions down the recursion tree (they get more specific, more narrow as we go down the tree), effectively forming a valid range for every node we check. For example, in the following tree,

the requirements for X are both X>=1 and X<=4. Further, valid range for Y is Y>=X and Y<=4. Notice that because X>=1 holds true (X is checked before Y, higher up in the recursion tree), the effective valid range for Y is narrower than one for X; that way the range gets narrower as we go deeper down the tree. For better understanding please look at the solution.

Time Complexity:

O(n) where n denotes the number of nodes.

As we are traversing all the nodes of the tree to check if the node value lies within a range or not, hence we have to iterate through all the nodes and edges of the tree. A tree with n nodes have (n-1) edges. So, we have to iterate  n + (n-1) → 2n-1 times can be represented as O(n) complexity.

Auxiliary Space:

O(n) where n denotes the number of nodes.

As we are calling functions in recursion, so in the worst case functional stack can have n number of function calls which is equal to the number of nodes of the given tree. Hence auxiliary space for that is O(n)

Space complexity:

O(n).

// -------- START --------

bool isBSTHelper(TreeNode *root, int min, int max){
    // NULL node check
    if(root == NULL){
        return true;
    }
    // current node value is not within valid range
    if(root->val>max || root->val<min){    return false;  } true when both left and right subtrees are valid bst isbsthelper(root->left_ptr, min, root->val) && isBSTHelper(root->right_ptr, root->val, max);
}

bool isBST(TreeNode* root){
    // empty or null tree check
    if(root==NULL){
        return true;
    }
    int min = INT_MIN;
    int max = INT_MAX;
    return isBSTHelper(root, min, max);
}

// -------- END --------
</min){>

2) optimal_solution.cpp:

In optimal_solution.cpp solution we have used in-order traversal property of a BST to validate whether it is a BST or not. If we store the values in an array during in-order traversal, it will be a sorted array if the given tree is BST. To check if an array is sorted or not, we just need to compare an element with the previous element of the array. We can do this while traversing the tree instead of storing the values in an array which will reduce space complexity. To achieve this, we have used a variable which stores the last visited nodes value at any time. So, when we are in a node, we can compare if the current node value is greater or equal to the previous node value. If this condition fails for any node then the given tree is not a BST. Otherwise it is.

Time Complexity:

O(n) where n denotes the number of nodes.

As we are traversing all the nodes of the tree to check if the current node value is greater or equal to the previous node value, hence we have to iterate through all the nodes and edges of the tree. A tree with n nodes have (n-1) edges. So, we have to iterate  n + (n-1) → 2n-1 times can be represented as O(n) complexity.

Auxiliary Space:

O(n) where n denotes the number of nodes.

As we are calling functions in recursion, so in the worst case functional stack can have n number of function calls which is equal to the number of nodes of the given tree. Hence auxiliary space for that is O(n)

Space Complexity:

O(n).

// -------- START --------

bool isBSTHelper(TreeNode *root, int &prev){
    // NULL node check
    if(root == NULL){
        return true;
    }

    // check if left subtree is bst or not
    bool isLeftSubtreeBST = isBSTHelper(root->left_ptr, prev);

    // Check if current node value is greater or equal to the max value of left subtree nodes
    if(root->val < prev){        return false;    }    // update the prev variable by current node value as each value of right subtree must be greater or equal    // to the current root value    prev = root->val;
    // true when both left and right subtrees are valid BST
    bool isRightSubtreeBST = isBSTHelper(root->right_ptr, prev);

    // Bitwise AND operation to return true only when both subtree is BST, otherwise false
    return (isLeftSubtreeBST && isRightSubtreeBST);
}

bool isBST(TreeNode* root){
    // empty or null tree check
    if(root==NULL){
        return true;
    }
    int min = INT_MIN;
    return isBSTHelper(root, min);
}

// -------- END --------