CareerCup

Good move, Peter!

I think this is the best you can do as far as run-time complexity. It's linear time and linear memory. You can't do better than linear time.

Let's assume that it's a COMPLETE BINARY TREE.

BFS - we have to maintain a QUEUE and the algorithm is iterative. The largest this QUEUE would ever get is 2^(H-1) (H is the height of the tree), which is the last level in the binary tree.

DFS - It can be implemented Iterative or Recursive. If we implement it Iteratively, we need a STACK and at most H elements are in the stack at any given time.

For COMPLETE BINARY TREE, DFS is better. We can generalize this into a B-Tree.

If the tree is deformed and becomes a something like a linked list, BFS is better.

As mentioned in question tree is not binary tree, if we try to insert into second tree then search complexity will increase.

Use the DFS search algorithm as space complexity is much lesser than BFS.

As Joe mentioned:
By using DFS traverse first tree and create a hash table, now while traversing the second tree look into hash table.

Use BFS to traverse the first tree and put the data as a key to a hash table with 0 in the value part. Then traverse the second tree and look through the hash table if the data already exists in the table. If found make the value part as 1 iff 0 and increment your counter. If the value part is 1 then do nothing.

I am wondering which algo BFS/DFS will be efficient here.

Any coments/suggestions are most welcome.

Take the second tree and try to insert that node in the second tree.. If element matching to that is found then don't insert and u just found similar element. Mark the node in first tree as visited. OR maintain a hash table of visited nodes. Even an array can be maintained.