98. Validate Binary Search Tree

Reference: LeetCode EPI 7.1
Difficulty: Medium

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:

    2
   / \
  1   3
Input: [2,1,3]
Output: true

Follow up: $O(1)$ Space? No. Iteration methods need stacks too.

Analysis

Methods:

The naive approach would be to calculate the lower and upper values when visiting each node, but it turns out to be very inefficient because it does a lot of repeated calculation. In the worst case, time complexity would be $O(N^2)$.

One alternative might be to cache the largest and smallest keys at each node using a HashMap, which requires $O(N)$ additional storage for the cache.

1. Recursion
   • For a node $x$, all nodes in its left subtree should be satisfy the constraint [L, x.val) and all nodes in the other side should be satisfy (x.val, R].
   • Time: $O(N)$ since we visit each node exactly once.
   • Space:
     • Best: $O(\log{N})$ when the tree is bushy.
     • Worst: $O(N)$
2. Iteration
   • The above recursion could be converted into iteration with the help of three stacks.
   • Time: $O(N)$
   • Space: $O(N)$
3. Inorder Traversal
   • We can use the fact that an inorder traversal visits keys in sorted order. We can compare each node we visit with the previous node during the inorder traversal.
     • Recursion
     • Iteration
   • Time: $O(N)$
   • Space: $O(N)$ or $O(\log{N})$
4. BFS Manner
   • When the property is violated at a node whose depth is small (close to the root), we can use this manner. Specifically, we use a queue, where each queue entry contains a node, as well as an upper bound and a lower bound on the keys.
   • Time: $O(N)$
   • Space: $O(N)$

Code

Test Case:

[2,1,3]
true
[1,1]
false

Recursion

Note:

• Use Long.MIN_VALUE rather than Integer.MAX_VALUE. But it’s better to use null.
• Be careful of the traversal order. When invalidity is detected, we should return immediately.
• Notice the condition of the problem description: Equality is not allowed.

My original bad code:

It is not efficient because it is a postorder traversal. If isValid is false, we should return immediately.

public boolean isValidBST(TreeNode root) {
  return isBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBST(TreeNode x, long lower, long upper) {
  if (x == null) {
    return true;
  }
  boolean isValid = (x.val < upper && x.val > lower);
  boolean isLeftValid = isValidBST(x.left, lower, x.val);
  boolean isRightValid = isValidBST(x.right, x.val, upper);
  
  return isValid && isLeftValid && isRightValid; 
}

Improvement:

private boolean isBSTHelper(TreeNode x, long lower, long upper) {
  if (x == null) {
    return true;
  } else if (x.val <= lower || x.val >= upper) {
    return false;
  } else {
    return isBSTHelper(x.left, lower, x.val) && isBSTHelper(x.right, x.val, upper);
  }
}

More Improvement:

Note: Rather than using extreme constants, we can use null and modify the conditions.

public boolean isValidBST(TreeNode root) {
  return isBSTHelper(root, null, null);
}

private boolean isBSTHelper(TreeNode x, Integer lower, Integer upper) {
  if (x == null) {
    return true;
  } else if (lower != null && x.val <= lower) {
    return false;
  } if (upper != null && x.val >= upper) {
    return false;
  } else {
    return isBSTHelper(x.left, lower, x.val) && isBSTHelper(x.right, x.val, upper);
  }
}

Iteration

Note:

• Check the stack before pushing values into it.

Stack<TreeNode> stack = new Stack<>();
Stack<Long> lowers = new Stack<>();
Stack<Long> uppers = new Stack<>();

public boolean isValidBST(TreeNode root) {
  if (root == null) {
    return true;
  }
  // Init Stack
  update(root, Long.MIN_VALUE, Long.MAX_VALUE);
  while (!stack.isEmpty()) {
    TreeNode p = stack.pop();
    long lower = lowers.pop();
    long upper = uppers.pop();
    if (p.val <= lower || p.val >= upper) {
      return false;
    }
    if (p.right != null) {
      update(p.right, p.val, upper);
    }
    if (p.left != null) {
      update(p.left, lower, p.val);
    }
  }
  return true;
}

private void update(TreeNode x, long lower, long upper) {
  stack.add(x);
  lowers.add(lower);
  uppers.add(upper);
}

Inorder Traversal

Recursion

public boolean isValidBST(TreeNode root) {
  prev = Long.MIN_VALUE;
  return inorder(root);
}

private TreeNode prev = null;

private boolean inorder(TreeNode x) {
  if (x == null) {
    return true;
  }
  // go left
  if (inorder(x.left) == false) return false;
  // check x
  if (prev != null && x.val <= prev.val) return false;
  prev = x;
  // go right
  if (inorder(x.right) == false) return false;
  
  return true;
}

Iteration

private boolean inorderItr(TreeNode root) {
  if (root == null) {
    return true;
  }

  TreeNode prev = null;

  Stack<TreeNode> stack = new Stack<>();
  TreeNode p = root;
  while (p != null || stack.size() > 0) {
    while (p != null) {
      stack.push(p);
      p = p.left;
    } // when p reaches the leftmost
    // visit
    p = stack.pop();
    if (prev != null && p.val <= prev.val) return false;
    prev = p;
    // go right
    p = p.right;
  }
  return true;
}