Tree Edit Distance Small

Problem

Compute the ordered tree edit distance with unit costs for insertion, deletion, and renaming.

A tree is represented as [label, [children]] recursively, and None is the empty tree. Match child sequences with dynamic programming: skip a child subtree at the cost of its size, or recursively align two children. Return the total cost, an integer.

Hint

Subtree deletion costs the number of nodes being removed.

Test cases

case 1

in: [[1,[[2,[]]]],[1,[[2,[]]]]]

expected: 0

case 2

in: [[1,[[2,[]]]],[1,[[3,[]]]]]

expected: 1

case 3

in: [[1,[[2,[]],[3,[]]]],[1,[[2,[]]]]]

expected: 1

case 4

in: [[1,[]],null]

expected: 1

Starter codePython

def tree_edit_distance(a, b):
    # Your code here
    pass

4 test cases · run your code against them in the editor