Serialise trees to find duplicate subtrees

"""Matching subtrees by brute force: compare at every node, and write out every subtree on its own; work counted."""
from collections import Counter, deque


class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def build(values):
    """The tree of a level-order list, where None marks a missing child."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    waiting = deque([root])
    i = 1
    while i < len(values):
        node = waiting.popleft()
        for side in ("left", "right"):
            if i < len(values) and values[i] is not None:
                child = Node(values[i])
                setattr(node, side, child)
                waiting.append(child)
            i += 1
    return root


def nodes_of(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node)
        stack += [c for c in (node.right, node.left) if c]
    return out


compared = 0


def same(a, b):
    """Shape and codes compared node by node; stops at the first difference."""
    global compared
    pairs = [(a, b)]
    while pairs:
        x, y = pairs.pop()
        compared += 1
        if x is None or y is None:
            if x is not y:
                return False
            continue
        if x.val != y.val:
            return False
        pairs += [(x.right, y.right), (x.left, y.left)]
    return True


def is_subtree(menu, part):
    return any(same(node, part) for node in nodes_of(menu))


def written_out(node):
    """A subtree as text, built fresh for every subtree: preorder, '#' for a missing child."""
    if node is None:
        return "#"
    return f"{node.val},{written_out(node.left)},{written_out(node.right)}"


def duplicates(root):
    texts = [written_out(node) for node in nodes_of(root)]
    counts = Counter(texts)
    return sorted((t for t, c in counts.items() if c >= 2), key=len), sum(map(len, texts))


menu = build([7, 3, 8, 5, 9, 3, 9, None, None, 5, None, 5, 9, None, 5, None, None, None, None, 5])
for part in ([3, 5, 9, None, None, 5], [9, None, 5], [9, 5, 5]):
    compared = 0
    print(f"part {part} in the menu: {is_subtree(menu, build(part))}, {compared} comparisons")
kinds, chars = duplicates(menu)
print(f"subtrees that repeat: {kinds}, after writing {chars} characters")


def a_line(codes):
    """A line of first children with these codes, top first."""
    root = node = Node(codes[0])
    for code in codes[1:]:
        node.left = Node(code)
        node = node.left
    return root


compared = 0
print(f"equal codes, a line of 1,000 and a part of 500: {is_subtree(a_line([1] * 1000), a_line([1] * 499 + [2]))}, "
      f"{compared:,} comparisons")
print(f"a line of 900 codes: {duplicates(a_line(list(range(900))))[1]:,} characters written for 900 subtrees")

part [3, 5, 9, None, None, 5] in the menu: True, 10 comparisons
part [9, None, 5] in the menu: True, 17 comparisons
part [9, 5, 5] in the menu: False, 21 comparisons
subtrees that repeat: ['5,#,#', '9,5,#,#,#', '3,5,#,#,9,5,#,#,#'], after writing 164 characters
equal codes, a line of 1,000 and a part of 500: False, 375,749 comparisons
a line of 900 codes: 2,428,495 characters written for 900 subtrees