Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
2  
does your solution really take O(n) space? Since they are both binary search trees if they have the same set of values they will be identical so you can do the inorder traversals in parallel and compare as you go just needing O(1) space unless I am missing something... –  hackartist Dec 19 '11 at 20:20
    
The whole purpose of this question during an interview is to see how you think. And if your natural inclination is to post on StackOverflow without the slightest bit of effort, then the interviewer knows exactly what type of employee you'd be. –  chrisaycock Dec 19 '11 at 20:23
1  
How do you expect to compare two trees of size n in O(logn) time?! –  Shahbaz Dec 19 '11 at 20:26
1  
@hackartist - O(1) space only if you don't count the stack of function calls for a recursive algorithm (which really isn't fair). An iterative algorithm will also need O(n) space worst case. –  Ted Hopp Dec 19 '11 at 20:28
    
@Shahbaz: I think it might be doable in O(1) time. –  DeadMG Dec 19 '11 at 20:28
show 4 more comments

migrated from stackoverflow.com Dec 21 '11 at 3:54

This question came from our site for professional and enthusiast programmers.

2 Answers

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.

share|improve this answer
    
Recursion depth can be O(n) worst case for unbalanced trees. Storing parent pointers is also O(n) space. –  Ted Hopp Dec 19 '11 at 20:43
1  
Hence "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 Dec 19 '11 at 20:49
add comment

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.

share|improve this answer
    
How would you hash them except by touching every element? –  DeadMG Dec 19 '11 at 20:22
    
How would you md5 the tree without traversing it all the way? –  w00te Dec 19 '11 at 20:22
3  
Different binary trees can produce the same md5 hash. –  Ted Hopp Dec 19 '11 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 Dec 19 '11 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 Dec 19 '11 at 20:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.