Validate Binary Search Tree
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.
- A single node tree is a BST.
Solution: The in-order traversal of binary search tree is in ascending order. We only need to compare current value with the previous value. The previous value should be initialized with Long.MIN_VALUE, otherwise, this validation won't work with root.val = -2147483648.
Code:
public class Solution {
private long lastValue = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (root.val <= lastValue) {
return false;
}
lastValue = root.val;
return isValidBST(root.right);
}
}