Overview

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values as subRoot, and false otherwise.

A subtree of a binary tree is a tree that consists of a node in the original tree and all of its descendants.

Constraints

• Both trees have 1 to 2,000 nodes.
• Node values are integers in range [-10000, 10000].
• A tree is always a subtree of itself.

Examples

// root:          subRoot:
//       3           4
//      / \         / \
//     4   5       1   2
//    / \
//   1   2

isSubtree(root, subRoot); // => true

// root:          subRoot:
//       3           4
//      / \         / \
//     4   5       1   2
//    / \
//   1   2
//      /
//     0

isSubtree(root, subRoot); // => false (extra node 0)

Solution

function isSubtree(root, subRoot) {
  if (!root) return false;
  if (isSame(root, subRoot)) return true;
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

function isSame(a, b) {
  if (!a && !b) return true;
  if (!a || !b) return false;
  return a.val === b.val && isSame(a.left, b.left) && isSame(a.right, b.right);
}

Resources

• Subtree of Another Tree — LeetCode
• Tree Comparison — Wikipedia