98. Validate Binary Search Tree.md

98. Validate Binary Search Tree

• Difficulty: Medium.
• Related Topics: Tree, Depth-first Search.
• Similar Questions: Binary Tree Inorder Traversal, Find Mode in Binary Search Tree.

Problem

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

Assume a 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:
    2
   / \
  1   3
Output: true

Example 2:

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

Solution 1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
};

var helper = function (root, min, max) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return helper(root.left, min, root.val) && helper(root.right, root.val, max);
};

Explain:

nope.

Complexity:

• Time complexity : O(n). n 为节点数。
• Space complexity : O(1).

Solution 2

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  var prev = null;
  var now = root;
  var stack = [];
  
  while (now || stack.length) {
    while (now) {
      stack.push(now);
      now = now.left;
    }
    
    now = stack.pop();
    
    if (prev && prev.val >= now.val) return false;
    
    prev = now;
    now = now.right;
  }
  
  return true;
};

Explain:

nope.

Complexity:

• Time complexity : O(n). n 为节点数。
• Space complexity : O(n).