Check if Array is in BST PreOrder Form in JAVA

This is my recursive implementation of the algorithm that checks if a given Array is in BinarySearchTree PreOrder form. The idea behind this algorithm is to start with the first element, let that element be the root, and let the next immediate element greater than the current element be the right child. This means that all elements between the current element and the right child element belong in the left subtree. This also tells us that anything to the right of the right child has to be less than the current element and would break the PreOrder structure otherwise. These conditions are recursively checked with the divide and conquer technique.

public static boolean isPreOrderForm(int[] arr, int i, int j) {
    int n = arr.length;
    if (n == 0) return true;
    if (j - i == 1) return true;

    int k = i;
    int m = i;

    while (k < j) {
        if (k <= m && arr[k] <= arr[i])
            m++;

        if (k > m && arr[k] < arr[i])
            return false;

        k++;
    }

    return isPreOrderForm(arr, i + 1, m) && isPreOrderForm(arr, m, j);
}

This article is my 16th oldest. It is 154 words long, and it’s got 0 comments for now.