Timeline for Determining whether two binary search trees have the same set of values
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2011 at 3:54 | history | migrated | from stackoverflow.com (revisions) | ||
| Dec 19, 2011 at 20:53 | comment | added | Lee Louviere | Actually, you'd get better time by testing the terminal nodes first. | |
| Dec 19, 2011 at 20:51 | comment | added | Lee Louviere | First, your algorithm is O(1) space, since you're not consuming space to compare. Second, your algorithm is already average O(log n) because you'll get exponential increasing time for each correct node. | |
| Dec 19, 2011 at 20:34 | comment | added | DeadMG | @TedHopp: I had an idea about testing the "balance" of the tree. However, I realized it would only work if you made a change to the values in the tree that would actually require a restructure. If you changed a value which didn't require a node restructuring, there would be no way to find it except to compare every node. | |
| Dec 19, 2011 at 20:32 | comment | added | Ted Hopp | @DeadMG O(1) time? really? You can test two billion-node trees for equality of values in the same time as you can test two 1-node trees? | |
| Dec 19, 2011 at 20:28 | comment | added | DeadMG | @Shahbaz: I think it might be doable in O(1) time. | |
| Dec 19, 2011 at 20:28 | comment | added | Ted Hopp | @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. | |
| Dec 19, 2011 at 20:26 | comment | added | Shahbaz |
How do you expect to compare two trees of size n in O(logn) time?!
|
|
| Dec 19, 2011 at 20:25 | answer | added | Daniel Fischer | timeline score: 4 | |
| Dec 19, 2011 at 20:23 | comment | added | chrisaycock | 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. | |
| Dec 19, 2011 at 20:20 | answer | added | Jamie Hutton | timeline score: 0 | |
| Dec 19, 2011 at 20:20 | comment | added | hackartist | 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... | |
| Dec 19, 2011 at 20:14 | history | asked | user1002288 | CC BY-SA 3.0 |