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

Question

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)?

Answer 1

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(𝑛) in the worst case, i.e. when the given tree is indeed a BST.

The best case is O(log𝑛) when the given tree is not a BST and the first execution of the if-condition is true and the execution ends. One call of min(𝑛) is made which is responsible for that O(log𝑛).

When the given tree is a BST, all nodes take a turn to become the argument of the function, and it is also called O(𝑛) times with NIL as argument, twice for every leaf node (left and right).

The more difficult part of the analysis concerns the calls of min(𝑛) and max(𝑛). These visit ℎ nodes where ℎ is the height of the given node. At first glance this looks like it would make the time complexity worse than O(𝑛), but for leaves, the value of ℎ is 0, and that is true for half of the nodes, while the other extreme (the root) will have ℎ equal to the height of the tree, but there is just one root.

This is similar to how a heap can be built with O(𝑛) time complexity, using Floyd's heap construction algorithm which -- just like here -- involves a logℎ step for each node. This turns out to still make the overall operation O(𝑛). I refer to How can building a heap be O(n) time complexity? for lots of answers that explain why this still is O(𝑛). The reasoning is the same for this algorithm.