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:

1
2
3
4
5
    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:

1
2
3
4
[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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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:

1
2
3
4
5
6
7
8
9
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}

Comment