Given two binary trees, return true if they have same elements (irrespective of tree structure)

Question

Jerry · Accepted Answer

traverse 1st tree and add all node data into hash table of 
traverse 2nd tree and foreach node:
  if data not in hashtable return false;
  otherwise, decrease count by 1, remove the key if count is 0
return hashtable.ItemCount == 0;

Anonymous · Answer

add all elements of one tree to a hashtable
for the other tree, add them to the same hashtable and if it's empty, return false, and if there is a collision, erase the entry from the table
if nothing's left in the table after, we're good

Anonymous · Answer

If the trees are binary search trees, it is possible to compare them quickly by calling repeatedly getSuccessor();

Endymion · Answer

The above algorithm is totally wrong. Let's take a look at this counter example:
Tree A:
 1
2 2

Tree B:
 1
1 2

Your algorithm will return "we are good" in this case.

Anonymous · Answer

traverse each tree into an array, sort them, compare

Meta

Meta Interview Question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?