Complexity of Validation of Binary Search Tree

Question

The complexity of checking the validity of binary search tree is $O(\log{n})$, but I see here that at each node we check left and right subtrees. Since we have a total nodes of $n$, we should have worst-case of $O(n\log{n})$. Please correct me if I am wrong:

IsBinarySearchTree(None *node){ 
if(root == Null) then return true; 
if (IsSubtreeLesser(root->left, root->data) && IsSubtreeGreater(root->right, root->data) && IsBinarySearchTree(root->left) &&IsBinarySearchTree(root->right)) then return true; 
else 
  return false; 
}

For each root below in the figure, we should check (Fig. taken from web):

Answer 1

The complexity of checking the validity of binary search tree is $O(\log{n})$,

If the question is, given a binary tree with $n$ nodes, are the nodes in sorted order, then the solution can't possibly be $O(\log n)$. You need at least time $O(n)$ just to look at the values in the $n$ nodes, so it's impossible that the worst-case time could be less than this.

(Or consider for example the case where the tree is maximally unbalanced. Then it is actually a linked list and we are effectively checking whether the list is in sorted order. This is obviously $O(n)$.)

I think you can achieve this bound of $O(n)$, if you build a single function that reports whether a tree is sorted, and, if it is, that also yields its minimum and maximum values. If you do this you only need to traverse the tree a single time.