Check whether a binary tree contains an identical subtree
Implement hasSubtree(root, candidate). It returns true if root contains a node whose subtree is identical to candidate, and false otherwise.
Each tree node is a plain object:
{ value: any, left: Node | null, right: Node | null }
===) and their left subtrees and right subtrees are identical.null trees are identical. A null tree and a node are not.candidate but has extra children below does not count.candidate (null) is a subtree of every tree, including an empty one.root contains no non-empty subtree.// root: candidate:
// 8 3
// / \ / \
// 3 10 1 6
// / \ \
// 1 6 14
const n = (value, left = null, right = null) => ({ value, left, right });
const root = n(8, n(3, n(1), n(6)), n(10, null, n(14)));
hasSubtree(root, n(3, n(1), n(6))); // => true
hasSubtree(root, n(10, null, n(14))); // => true
hasSubtree(root, n(3, n(1))); // => false (node 3 also has a right child, 6)
hasSubtree(root, n(10, n(14))); // => false (14 is on the right, not the left)
hasSubtree(root, n(14)); // => true
hasSubtree(root, null); // => true
hasSubtree(null, n(8)); // => false