Tree Copy Optimization — Hash Old to New

When structure is large but overlapping subproblems appear (DAG-shaped “trees”), memoize copies by node identity.

Try this in Python

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def clone_with_memo(root: TreeNode | None, memo: dict[int, TreeNode] | None = None) -> TreeNode | None:
    if memo is None:
        memo = dict()
    if not root:
        return None
    if id(root) in memo:
        return memo[id(root)]
    copy = TreeNode(root.val)
    memo[id(root)] = copy
    copy.left = clone_with_memo(root.left, memo)
    copy.right = clone_with_memo(root.right, memo)
    return copy

r = TreeNode(1, TreeNode(2), TreeNode(3))
c = clone_with_memo(r)
print(c.right.val if c.right else None)

Key takeaways

• id keys are fine for single-threaded contest code; production uses explicit handles.
• Random-pointer clone is the famous two-pass + map pattern.
• Time O(n), space O(n) for the memo.