# Union of two binary trees (if they share common nodes)

• e.g

``````Tree 1:                                         Tree 2:
A                                              B
/      \                                       /     \
B         C                                   D            E
/           |                                /    \          \
D           ...                               C     F           G

Union:
A
/      \
B          C
/   \          |
D     E         ...
/   \      \
C     F      G
``````

The union of the two trees should be returned if there is an overlap. We don't know which tree might be a subtree of the other. The result should be a new tree [inputs should not be modified]

I proposed a recursive solution which would work if we knew that Tree2 could be a subtree of the other. If this is not assumed how do I go about it ?

• You can save all the node in Tree1 with a HashTable , then judge whether the root of Tree2 is in the HashTable.
If true then Tree2 is a subtree of tree1 , otherwise you can assume tree1 is a subtree of Tree2.

• @ww884203 I can understand your general idea. But could you elaborate on how you would actually proceed to code it up. I think it would not be easy to find the union nodes.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.