98. Validate Binary Search Tree

Problem¶

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

Solve¶

Recursion - bottom up¶

If we want a valid BST, then all tree node it self is a valid BST. With each tree node check, I try to remember:

• Is it a valid Tree
• What is it coverage range

This then helping us when it come to their parent node, we:

• If its left, right node isn’t a valid Tree, then the parent node isn’t a valid Tree. Quickly return False
• If the coverage range not match: [Left range] < Parent.val < [Right range] then the Parent isn’t a valid Tree. Quickly return False
• If both above pass, we have a valid parent tree node. Return it coverage range [l,r] and its valid Tree stage True

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def represent(root):
            l = root.val
            r = root.val
            if root.left:
                l_left, l_right, l_check = represent(root.left)
                if not l_check or root.val <= l_right:
                    return 0, 0, False
                l = l_left

            if root.right:
                r_left, r_right, r_check = represent(root.right)

                if not r_check or r_left <= root.val:
                    return 0, 0, False
                r = r_right

            return l, r, True

        _, _, result = represent(root)
        return result

While some how this return a accepted, this shouldn’t work:

• The stack will be deallocated, all Rep object that we define will free the memory after return to the original parent function.
• So the return function which trying to return a pointer to Rep object, return to a free position in stack. Which then maybe be overridden, and make not so good behavior.
  

  typedef struct {
      int l;
      int r;
      bool valid;
  } Rep;
  
  Rep check(struct TreeNode* root){
      int l = root->val;
      int r = root->val;
      if (root->left != NULL) {
          Rep left = check(root->left);
          if (!left.valid || l <= left.r) {
              Rep wrong = {0, 0, false};
              return wrong;
          }
          l = left.l;
      }
      if (root->right != NULL) {
          Rep right = check(root->right);
          if (!right.valid || right.l <= r) {
              Rep wrong = {0, 0, false};
              return wrong;
          }
          r = right.r;
      }
      Rep result = {l, r, true};
      return result;
  }
  
  bool isValidBST(struct TreeNode* root) {
      return check(root).valid;
  }
  

Recursion - top down¶

If we want a valid BST, then all tree node it self is a valid BST. Start from the top root tree node, with a range of [left, right] = [-MAX_INT, MAX_INT], to check our if root a valid BTS:

• All tree node in the Left should be covered by [-MAX_INT, root.val -1]
• All tree node in the Right should be covered by [root.val +1, MAX_INT]

We push it down until checking all the node possible, any node that have value outside of it desirable range will return us with a False valid BTS root

Memory limit¶

The MAX_INT should large than - -2**31 <= Node.val <= 2**31 - 1, which may require you to give a bigger memory

While there is some (??) moments here. Here is Leetcode C memory allocate:
int = 4 bytes
long = long long = 8 bytes

My memory. Here is C memory allocate:
int = 2 bytes
long = 4 bytes
long long = 8 bytes

Implementation¶

By using long (8 bytes) integer:

bool check(struct TreeNode* root, long l, long r){
    if (root->left != NULL) {
        if (! check(root->left, l, root->val))
            return false;
    }
    if (root->right != NULL) {
        if (! check(root->right, root->val, r))
            return false;
    }
    return l < root->val && root->val < r;
}

bool isValidBST(struct TreeNode* root) {
    return check(root, LLONG_MIN, LLONG_MAX);
}

or by using a boolean as our representative to MAX_INT number, instead of real value:

bool check(struct TreeNode* root, int l, int r, bool haveL, bool haveR){
    if (root->left != NULL) {
        if (! check(root->left, l, root->val, haveL, true))
            return false;
    }
    if (root->right != NULL) {
        if (! check(root->right, root->val, r, true, haveR))
            return false;
    }
    if (haveL){
        if (! (l < root->val))
            return false; 
    }
    if (haveR){
        if (! (root->val < r)) {
            return false;
        }
    }
    return true;
}

bool isValidBST(struct TreeNode* root) {
    return check(root, 0, 0, false, false);
}