Solution
Approach 1: Recursion
Intuition
If root1
and root2
have the same root value, then we only need to check if their children are equal (up to ordering.)
Algorithm
There are 3 cases:

If
root1
orroot2
isnull
, then they are equivalent if and only if they are bothnull
. 
Else, if
root1
androot2
have different values, they aren't equivalent. 
Else, let's check whether the children of
root1
are equivalent to the children ofroot2
. There are two different ways to pair these children.
Complexity Analysis

Time Complexity: , where are the lengths of
root1
androot2
. 
Space Complexity: , where are the heights of the trees of
root1
androot2
.
Approach 2: Canonical Traversal
Intuition
Flip each node so that the left child is smaller than the right, and call this the canonical representation. All equivalent trees have exactly one canonical representation.
Algorithm
We can use a depthfirst search to compare the canonical representation of each tree. If the traversals are the same, the representations are equal.
When traversing, we should be careful to encode both when we enter or leave a node.
Complexity Analysis

Time Complexity: , where are the lengths of
root1
androot2
. (In Python, this is .) 
Space Complexity: . (In Python, this is , where are the heights of the trees of
root1
androot2
.)
Analysis written by: @awice.