Binary Tree Subtree

Implement binaryTreeSubtree(root, subRoot) — return a boolean: does the tree rooted at root contain a subtree that is structurally identical to the tree rooted at subRoot? "Identical" means same shape and same values, matched from some node in root all the way down to its leaves. This is the shape of question a code-search tool answers when it asks "does this file contain this exact expression tree?" — a structural match, not a values-somewhere-in-there match.

Signature

// A binary tree node. Leaves have left === null and right === null.
type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};

// root:    the tree to search inside (may be null for an empty tree)
// subRoot: the pattern tree to look for (may be null)
// returns: true if some node in root begins a subtree identical to subRoot
function binaryTreeSubtree(
  root: TreeNode | null,
  subRoot: TreeNode | null
): boolean;

A match must extend from a node in root all the way down: that node's value equals subRoot.val, its left child's whole subtree equals subRoot.left's whole subtree, and the same on the right. A node whose value happens to match but whose children differ is not a match.

Examples

// root:           subRoot:
//      3              4
//     / \            / \
//    4   5          1   2
//   / \
//  1   2
const root = {
  val: 3,
  left: { val: 4, left: { val: 1, left: null, right: null },
                  right: { val: 2, left: null, right: null } },
  right: { val: 5, left: null, right: null },
};
const subRoot = {
  val: 4,
  left: { val: 1, left: null, right: null },
  right: { val: 2, left: null, right: null },
};
binaryTreeSubtree(root, subRoot); // → true  (the node 4 and everything below it match exactly)

// Same root, but subRoot now has an extra node under the 1.
// root's node 4 has 1 as a leaf; subRoot's 1 has a left child 0.
// They agree at the top but differ deeper, so this is NOT a match.
const subRoot2 = {
  val: 4,
  left: { val: 1, left: { val: 0, left: null, right: null }, right: null },
  right: { val: 2, left: null, right: null },
};
binaryTreeSubtree(root, subRoot2); // → false  (differs at a deep leaf)

Notes

• A subtree match runs from a node all the way down. It is not enough for subRoot to appear embedded inside root. The matching node's entire subtree — every descendant — must equal subRoot's entire subtree. An embedded fragment that has extra children hanging off it in root is not a subtree match.
• Shape and value both matter. Two trees match only if they have the same structure (left/right placement included) and equal values at every corresponding node. Left-vs-right is significant: a 1 on the left is not the same as a 1 on the right.
• An empty subRoot returns true. An empty tree is a subtree of every tree (including an empty root) — there is nothing to find, so the search trivially succeeds. This is the documented policy for this question.
• A non-empty subRoot against a null root returns false. There is no node to start a match from.
• Values can repeat. The same value may appear at many nodes in root. Finding a node whose value matches subRoot.val is only the start — you still have to verify the full subtree below it. Only the location that matches all the way down counts.
• Don't worry about balancing, BST ordering, parent pointers, or duplicate-key semantics beyond plain equality. Node values are compared with ===.