Subtree of Another Tree Easy 0 attempts
LeetCode ↗

Subtree of Another Tree

Easy TreeBinary TreeDFS LeetCode

You're given the roots of two binary trees. Determine whether the second tree appears somewhere within the first — that is, whether some node in the first tree has exactly the same structure and values as the entire second tree.

Input Format
Implement isSubtree(root, subRoot). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
root = [3,4,5,1,2,null,null,null,null,0]
subRoot = [4,1,2]
Output
false
Constraints
  • 1 <= number of nodes <= 2000
  • -10^4 <= Node.val <= 10^4
Test Cases (2)
Case 1
Args: [[3,4,5,1,2],[4,1,2]] Expected: true
Case 2
Args: [[3,4,5,1,2,null,null,null,null,0],[4,1,2]] Expected: false
Topics
TreeBinary TreeDFS

DFS + Same Tree

javascript
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