Subtree of Another Tree

Difficulty: Easy

You're given the roots of two binary trees, called root and subRoot. Determine whether subRoot appears somewhere inside root as an exact subtree - meaning there's some node in root such that the tree hanging below it (that node plus everything beneath it) is structurally identical, value for value, to subRoot.

Return true if such a node exists, and false otherwise.

Examples

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

The subtree hanging below the node valued 4 (with children 1 and 2) matches subRoot exactly.

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

The node valued 4 now has an extra node (0) hanging further below it, so its subtree no longer matches subRoot exactly.

Input: root = [1,1], subRoot = [1]
Output: true

The second node valued 1 (a leaf) by itself matches subRoot, which is just a single node valued 1.

Constraints

  • The number of nodes in root is in the range [1, 2000].

  • The number of nodes in subRoot is in the range [1, 1000].

  • -10^4 <= Node.val <= 10^4

Approach

This builds directly on the "are two trees identical" check: instead of comparing exactly two trees, walk through every node of root and, at each one, ask whether the subtree starting there is identical to subRoot. As soon as one position matches, the answer is true; if no position ever matches, the answer is false.

Solutions

DFS — Same-Tree Check at Every Node

Reuse an identical-trees helper. Recursively visit every node of root; at each one, check if the subtree rooted there is identical to subRoot. If root itself runs out (null) before a match is found, there's nowhere left to check.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isSameTree(a, b) {
  if (a === null && b === null) return true;
  if (a === null || b === null) return false;
  if (a.val !== b.val) return false;

  return isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
}

function isSubtree(root, subRoot) {
  if (root === null) return false;
  if (isSameTree(root, subRoot)) return true;

  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

Time: O(n * m) — where n is the number of nodes in root and m is the number of nodes in subRoot, since up to n positions are each checked in O(m) · Space: O(h) — recursion stack depth, where h is the height of root

Serialize and Search

Convert both trees into unique string encodings (using sentinels for null children and separators so values never accidentally merge), then just check whether subRoot's encoding appears as a substring of root's encoding.

function serialize(node, out) {
  if (node === null) {
    out.push("#");
    return;
  }
  out.push("^" + node.val);
  serialize(node.left, out);
  serialize(node.right, out);
}

function isSubtree(root, subRoot) {
  const rootParts = [];
  const subParts = [];

  serialize(root, rootParts);
  serialize(subRoot, subParts);

  return rootParts.join(",").includes(subParts.join(","));
}

Time: O(n + m) for building the strings, plus the cost of the substring search (typically O(n + m) with a good algorithm, O(n * m) naively) · Space: O(n + m) — for the serialized strings