[LeetCode] Problem 98 - Validate Binary Search Tree

Posted on | In ,

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

No.1

Input:

1
2
3
  2
 / \
1   3

Output: true

No.2

Input:

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

O(n) runtime, O(n) stack space – Top-down recursion

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isValidBST(TreeNode root) {
    return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBSTHelper(TreeNode root, long low, long high) {
    if (root == null)
        return true;

    if (root.val <= low || root.val >= high)
        return false;

    return isValidBSTHelper(root.left, low, root.val) && isValidBSTHelper(root.right, root.val, high);
}

O(n) runtime, O(n) stack space – In-order traversal

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private TreeNode prev = null;

public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;

    if (isValidBST(root.left)) {
        if (prev == null || root.val > prev.val) {
            prev = root;
            return isValidBST(root.right);
        }
    }

    return false;
}