JAVA simple recursive in-order traversal

  • 0

    If we traverse the TreeNodes in order, then we can check the validity of BST by only testing whether each element is strictly greater than the previously visited element. Hence we need just one variable to keep the value of the previously visited TreeNode value, and we initialize it with Long.MIN_VALUE, to make sure no node in the tree will be of that value.

    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null)
            return true;
        boolean lr = isValidBST(root.left);
        if(root.val <= pre) 
            return false;
        pre = root.val; //keep this value to compare it with value of the next in order element
        boolean rr = isValidBST(root.right);
        return lr && rr;

Log in to reply

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