Hi, I have a question here:

imagine we want to write a function that checks if a given binary tree is a valid binary search tree ( the tree is in the form of objects/embedded references). What is the best time complexity possible for such a function?

I'm new to this Big-Oh stuff; I'm not sure how to apply Big-Oh to algorithms and programs. If there are n nodes, to check if a binary tree is a BST, you will have to do n comparisons. So, if you put 4 more nodes into the tree, you will have to do 4 more comparisons. So would it have to be O(n)?

Thanks