LeetCode - Algorithms - 98. Validate Binary Search Tree

The solution of wikipedia is the elegant answer to this question. It finally passed on LeetCode after I modified and submited six times.

Sometimes we already have a binary tree, and we need to determine whether it is a BST. This problem has a simple recursive solution.

Essentially we keep creating a valid range (starting from [MIN_VALUE, MAX_VALUE]) and keep shrinking it down for each node as we go down recursively.

Problem

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

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long minKey, long maxKey) {
    	if (root==null) return true;
    	if (root.val<=minKey || root.val>=maxKey) return false;
    	return isValidBST(root.left,minKey,root.val) && isValidBST(root.right,root.val,maxKey);
    }   
}

Submission Detail

  • 75 / 75 test cases passed.
  • Runtime: 0 ms
  • Your runtime beats 100.00 % of java submissions.

ref