Are these trees isomorphic?

Question

Introduction

In this challenge, your task is to write a program that decides whether two given trees are isomorphic. A tree means a directed acyclic graph where every node has exactly one outgoing edge, except the root, which has none. Two trees are isomorphic if one can be transformed into the other by renaming the nodes. For example, the two trees (where every edge points up)

  0       0
 /|\     /|\
1 3 4   1 2 5
|\       /|
2 5     3 4

are easily seen to be isomorphic.

We encode a tree as a list L of nonnegative integers in the following way. The root of the tree has label 0, and it also has nodes 1,2,...,length(L). Each node i > 0 has an outgoing edge to L[i] (using 1-based indexing). For example, the list (with the indices given under the elements)

[0,0,1,3,2,2,5,0]
 1 2 3 4 5 6 7 8

encodes the tree

  0
 /|\
1 2 8
| |\
3 5 6
| |
4 7

Input

Your inputs are two lists of nonnegative integers, given in the native format or your language. They encode two trees in the manner specified above. You can assume the following conditions about them:

1. They are not empty.
2. They have the same length.
3. Each list L satisfies L[i] < i for all (1-based) indices i.

Output

Your output shall be a truthy value if the trees are isomorphic, and a falsy value if not.

Rules and scoring

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There are no time restrictions, but built-ins that decide tree or graph isomorphism are disallowed.

Test cases

Truthy instances

[0] [0]
[0,1,2,1] [0,1,1,3]
[0,1,1,3,3] [0,1,2,2,1]
[0,1,0,1,2,3,3,0] [0,0,2,1,0,4,2,1]
[0,1,2,3,1,2,3,0,8] [0,1,0,3,3,4,4,7,7]

Falsy instances

[0,0] [0,1]
[0,1,2,0,3,3,4] [0,1,2,3,0,4,3]
[0,1,0,1,2,3,3,0] [0,0,2,1,0,5,2,1]
[0,1,1,0,1,3,2,1,5] [0,1,0,3,3,3,2,5,2]
[0,1,2,3,1,2,3,0,8] [0,1,0,1,4,4,5,6,6]
[0,1,0,2,0,3,0,4,0,5] [0,0,2,1,0,3,4,0,0,9]

Answer 1

Python, 83

The anonymous function on the 2nd line is my solution.

f=lambda l,i=0:sorted(f(l,j+1)for j,e in enumerate(l)if e==i)
lambda a,b:f(a)==f(b)

f returns a canonized form of a subtree which is a sorted list of its canonized children. Then we must simply check if the canonized forms of each tree are equal.

Answer 2

Mathematica, 48 bytes

SameQ@@(Sort//@(0(0//.PositionIndex@#))&/@{##})&

It's even shorter than the solution that uses IsomorphicGraphQ:

IsomorphicGraphQ@@(Graph@*MapIndexed[#->Tr@#2&]/@{##})&