Binary Search Tree     Binary Tree     Depth-First Search     Medium     Tree    

Problem Statement:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

 

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

Solution:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode *> st;
        TreeNode *prev; prev = NULL;
        while (root || !st.empty())
        {
            while (root)
            {
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();
            if (prev && root->val <= prev->val) return false;
            prev = root;
            root = root->right;
        }
        return true;
    }
};

The above is the best solution for this as it requires O(1) space.

A simpler O(N) space solution is to just do recursive inorder traversal, store all elements in array and check that the array is sorted. But this is not so impressive though it still does the job.

class Solution {
public:
    void inOrderTraversal(TreeNode *root, int *arr, int *n){
        if (root==NULL) return;
        inOrderTraversal(root->left, arr, n);
        *(arr+*n) = root->val;
        *n = *n+1;
        inOrderTraversal(root->right, arr, n);
    }
    bool isSorted(int arr[], int n){
        for (int i=1; i<n; i++){if (arr[i]<=arr[i-1]) return 0;} return 1; 
    }
    bool isValidBST(TreeNode* root) {
        int *arr = new int[10000000];
        int n=0;
        inOrderTraversal(root, arr, &n);
        return isSorted(arr, n);
    }
};