572. Subtree of Another Tree

Return true if some node of root has a subtree identical (in structure and values) to subRoot.

Serialize both trees in pre-order with null markers and a separator before every value. subRoot is a subtree exactly when its string occurs inside root's string. (Use KMP for guaranteed linear time.)

1function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
2  const ser = (n: TreeNode | null): string =>
3    n ? "^" + n.val + ser(n.left) + ser(n.right) : "#";
4  const a = ser(root), b = ser(subRoot);
5  return a.includes(b);
6}

root

subRoot

Serialize in pre-order. '^' marks the start of each value and '#' marks a null child.

1 / 0

Space: play/pause · ←/→: step