Tree copy optimization

DAG shape — memo by node id.

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 contest use.
• Random pointer — map pattern.
• O(n) time/space.