This is an interview question:
Given two Binary Search Trees, write a program to determine whether they contain the same set of values. Assume there are no duplicates.
My idea is to perform an in-order traversal for both trees and compare each element one by one. It takes O(n) time and O(n) space.
How could I do it in O(lg(n)) time and O(1) space?
Best Answer
You can't have an algorithm with lower complexity than O(n) because you may need to look at all elements. Regarding space, you can lazily produce the list of elements, so you don't need O(n) space, only O(log n) (recursion depth), provided the trees are sufficiently balanced. It's doable in O(1) space if nodes contain parent pointers.