[LeetCode] 98. Validate Binary Search Tree

Posted on | In

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:

1
2
3
4
5
6
    2
   / \
  1   3

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

Example 2:

1
2
3
4
5
6
7
8
9
    5
   / \
  1   4
     / \
    3   6

Input: [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.

Explanation

  1. We can use recursive method to solve this problem. To know if the current node is the valid BST, we check the left child’s value cannot be greater or equal than the current node value and the right child cannot be smaller or equal to the current node’s value. So, we can recursivly call the left child’s node and call the right child’s node with this same method with the correct min and max value.

  2. The base case is when the current node is NULL, we return true.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean helper(TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        if (max != null && root.val >= max) return false;
        if (min != null && root.val <= min) return false;

        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
}