Alg.24 Validate BST

From algoexpert.io

Write a function to check whether a tree is a BST.



For this problem, each node has a minimum and maximum bound, a right node shall be equal to or greater than its parent, a left node shall be smaller than its parent.

Here is the code implementation:

public static boolean validateBst(BST tree) {
    return helper(tree, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
  
public static boolean helper(BST tree, int min, int max) {
    if (tree.value < min || tree.value >= max) return false;

    if (tree.left != null && !helper(tree.left, min, tree.value)) return false;

    if (tree.right != null && !helper(tree.right, tree.value, max)) return false;

    return true;
}

Time complexity: O(n); Space complexity: O(logn).

Donate