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.