Amazon Interview Question

Write a function to validate a binary search tree. Assume there are supporting classes and functions already. Try to prioritise speed - don't worry too much about memory. - What other test cases would you use? - How to do it without recursion?