Subtree of Another Tree Easy 0 attempts
LeetCode ↗

Subtree of Another Tree

Easy TreeBinary TreeDFS LeetCode

Given roots of two binary trees, check if the second tree is a subtree of the first.

Example: root = [3,4,5,1,2], subRoot = [4,1,2] → true

Sample Input
—
Sample Output
—
Constraints
  • 1 <= number of nodes <= 2000
  • -10^4 <= Node.val <= 10^4
Topics
TreeBinary TreeDFS

DFS + Same Tree

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 || a.val !== b.val) return false;
  return isSame(a.left, b.left) && isSame(a.right, b.right);
}

Time: O(m × n) | Space: O(h)

Saved in this browser only. Private to you.

JavaScript