Why is this BST validation algorithm O(n) in the case of a balanced tree?-CodePudding

I was trying to write an algorithm which, given a complete binary tree, tells me whether it's a binary search tree (BST) or not. I am required to provide an algorithm with O(n) time complexity, where n is the number of nodes in the tree.

I came up with this solution (pseudo code):

def isBST(x):
    if x=NIL: return True
    if min(x.right) < x.value or max(x.left) > x.value: return False
    isBST(x.left)
    isBST(x.right)
    return True

where min(X.right) is the minimum value in the right subtree defined by x:

def min(x):
    while x.left:
        x = x.left
    return x.value

And max(X.left) gets the maximum value in the left subtree.

I read online that this kind of solution has a running time of O(N) in the case of balanced/full tree, because the recursive equation will be:

T(n) = T(n/2) O(logn)

Is it true that this represents O(n) time complexity? If yes, why? if not, then how can I make it O(n)?

CodePudding user response：

First, I should mention there is a bug in your function: it does not do anything with the booleans that are returned by the recursive calls, so that even if one of those returns false, the execution continues and returns true.

The correct code would process the recursive calls like this:

    return isBST(x.left) and isBST(x.right)

The time complexity is O(