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 or root2 is null, then they are equivalent if and only if they are both null.

  • Else, if root1 and root2 have different values, they aren't equivalent.

  • Else, let's check whether the children of root1 are equivalent to the children of root2. There are two different ways to pair these children.

Complexity Analysis

  • Time Complexity: , where are the lengths of root1 and root2.

  • Space Complexity: , where are the heights of the trees of root1 and root2.


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 depth-first 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 and root2. (In Python, this is .)

  • Space Complexity: . (In Python, this is , where are the heights of the trees of root1 and root2.)


Analysis written by: @awice.