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?
2 Answers 2
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.
-
Recursion depth can be O(n) worst case for unbalanced trees. Storing parent pointers is also O(n) space.Ted Hopp– Ted Hopp2011年12月19日 20:43:38 +00:00Commented Dec 19, 2011 at 20:43
-
1Hence "provided the trees are sufficiently balanced". If the trees contain parent pointers, I wouldn't count that memory for the algorithm, because it's already there. If you count that, you'll need O(n) memory for the two trees anyway.Daniel Fischer– Daniel Fischer2011年12月19日 20:49:50 +00:00Commented Dec 19, 2011 at 20:49
Could you not just generate a md5 hash for each binary tree object and compare them. If the binary trees are the same the md5 hash should also be the same.
-
How would you hash them except by touching every element?DeadMG– DeadMG2011年12月19日 20:22:06 +00:00Commented Dec 19, 2011 at 20:22
-
How would you md5 the tree without traversing it all the way?John Humphreys– John Humphreys2011年12月19日 20:22:16 +00:00Commented Dec 19, 2011 at 20:22
-
3Different binary trees can produce the same md5 hash.Ted Hopp– Ted Hopp2011年12月19日 20:24:19 +00:00Commented Dec 19, 2011 at 20:24
-
@Ted Hopp - If they have the same values they would be the same, if there balanced differently that's another problem. His question is about the same values.Jamie Hutton– Jamie Hutton2011年12月19日 20:27:10 +00:00Commented Dec 19, 2011 at 20:27
-
I wasn't disputing that if they have the same values they will be the same (although you bring up the interesting issue of balance). I was noting that trees with different values can (in theory) produce the same md5 hash. Hashing is generally a lossy conversion.Ted Hopp– Ted Hopp2011年12月19日 20:31:11 +00:00Commented Dec 19, 2011 at 20:31
n
inO(logn)
time?!