algorithm - How to find if two binary trees are identical in terms of content? -

i see several posts around how determine if 2 trees same in terms of structure have not found answer on how find if 2 trees same in terms of content.

say, tree node defined follows.

treenode {     string data;     treenode* left;     treenode* right }; 

now have 2 binary tree , need find out if 2 trees same in terms of content. these 2 may not structurally identical nor cannot assume data string identical in words.

for instance, might have following 2 trees. these 2 trees can treated identical in terms of content when inorder walk. clear, when concatenate node strings these 2 trees, same. i.e. abcdedfg

 (abc)  |   \  (d) (efg)   (a)  |  \  (b) (cdefg) 

i know can inorder walk collect string of both trees , can compare resulting 2 strings want know if there more efficient way of comparing 2 trees either somehow walking 2 trees in parallel or creating iterator. none of these seemed obvious me wanted feedback , maybe code snippet better ideas.

thanks in advance.

you can iterate through both trees using dfs (depth first search) comparing character character. combined two-finger algorithm iterate through nodes of each tree @ different speeds depending on element to.

as example. tree 1 , tree, node x-y row x, element y. e.g. tree 1 node 2-2 "efg":

tree 1 (abc)  |   \  (d) (efg)  tree 2  (a)  |  \  (b) (cdefg) 

the algorithm walk through nodes of each tree in turn, comparing character character.

1. start tree 1 node 1-1
2. start tree 2 node 1-1
3. compare a1 a2
4. advance tree 2 node 2-1
5. compare b1 b2
6. advance tree 2 node 2-2
7. compare c1 c2
8. advance tree 1 node 2-1
9. compare d1 d2
10. advance tree 1 node 2-2
11. compare e1 e2
12. compare f1 f2
13. compare g1 g2
14. return identical!