Ac solution code


  • 0

    Validate Binary Search Tree:

    1) Check if all nodes in root's left branches are less than root.val
    2) Check if all nodes in root's right branches are greater than root.val
    

    Time complexity = O(n) - (n is the amount of nodes in the tree)

    As each node is checked once, so time complexity = O(n).

    JAVA Code:

    public boolean isValidBST(TreeNode root)  {
    	return isValidBST(root, Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY);
    } 
    boolean isValidBST(TreeNode root, double max, double min) {
    	if (root == null) return true;
    	if (root.val >= max || root.val <= min) return false;
    	return isValidBST(root.left, root.val, min)   // Check if all nodes in root's left branches are less than root.val
    		&& isValidBST(root.right, max, root.val); // Check if all nodes in root's right branches are greater than root.val
    }

  • 1
    E

    Any chance do you know why it didn't work out if the input is int max, int min
    and when you call function, correspondingly call Integer.MAX_VALUE and Integer.MIN_VALUE?


  • 0
    K

    It's because the value of Integer.MAX_VALUE which is 2147483647 is an input in one of the test cases.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.