# Subtree of Another Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/subtree-of-another-tree)
Canonical: https://scaleengineer.com/dsa/problems/subtree-of-another-tree
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Merkle Tree](https://scaleengineer.com/algorithms/merkle-tree)
**Data structures:** Tree, Binary Tree
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [eBay](https://scaleengineer.com/companies/ebay), [Compass](https://scaleengineer.com/companies/compass), [Jump Trading](https://scaleengineer.com/companies/jump-trading)
---
## Problem
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 of` subRoot` and `false` otherwise.

A subtree of a binary tree `tree` is a tree that consists of a node in `tree` and all of this node's descendants. The tree `tree` could also be considered as a subtree of itself.

**Example 1:**

![](https://assets.glich.co/dsa/subtree-of-another-tree/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/subtree-of-another-tree/image1.jpg) 

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

**Constraints:**

* The number of nodes in the `root` tree is in the range `[1, 2000]`.
* The number of nodes in the `subRoot` tree is in the range `[1, 1000]`.
* `-104 <= root.val <= 104`
* `-104 <= subRoot.val <= 104`

# Approaches
## Brute Force Traversal
This approach involves traversing the main tree (`root`). For each node encountered in `root`, we check if the subtree starting at that node is identical to the `subRoot` tree. This is the most straightforward, brute-force solution.
**Time:** O(m * n), where `m` is the number of nodes in `root` and `n` is the number of nodes in `subRoot`. In the worst-case scenario, we might call `isSameTree` for every node in `root`, and each call to `isSameTree` takes O(n) time. · **Space:** O(m + n) in the worst case. The space is determined by the maximum depth of the recursion stack. In a skewed tree, the depth of `isSubtree` can be `m` and the depth of `isSameTree` can be `n`. Since the calls are nested, the total depth can be `m + n`.
**Pros:** Simple to understand and implement.; Requires minimal extra space, used only by the recursion stack.
**Cons:** Highly inefficient for large or skewed trees due to its quadratic time complexity.; Performs many redundant comparisons on the same nodes.
### Explanation
This method uses two recursive functions. The main function, `isSubtree`, traverses every node of the `root` tree. For each of these nodes, it calls a helper function, `isSameTree`, to determine if the subtree rooted at the current node is structurally and valuably identical to the `subRoot` tree.

If `isSameTree` finds a match, the process stops and returns `true`. If it doesn't, `isSubtree` moves to the children of the current node and repeats the process. If the entire `root` tree is traversed without finding an identical subtree, the function returns `false`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
```
### Algorithm
*   Define a main recursive function `isSubtree(root, subRoot)`.
*   Define a helper recursive function `isSameTree(p, q)` to check if two trees are identical.
*   In `isSubtree`:
    1.  Handle the base case: if `root` is `null`, return `false`.
    2.  Check if the tree starting at the current `root` is identical to `subRoot` by calling `isSameTree(root, subRoot)`. If it returns `true`, a match is found, so return `true`.
    3.  If no match is found at the current node, the subtree might exist deeper in the tree. Recursively search in the left and right children: `return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)`.
*   In `isSameTree`:
    1.  If both nodes `p` and `q` are `null`, they are identical, return `true`.
    2.  If one node is `null`, or their values differ, they are not identical, return `false`.
    3.  Recursively compare the left children and the right children: `return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)`.

## Tree Serialization with Substring Search
A more efficient approach is to convert both trees into strings, for example, using a pre-order traversal. Once both `root` and `subRoot` are represented as strings, the problem is reduced to a simple substring search. If the `subRoot`'s string is a substring of the `root`'s string, it means the subtree exists.
**Time:** O(m + n). Serializing `root` takes `O(m)` and `subRoot` takes `O(n)`. The substring search, if implemented efficiently (like KMP), also takes `O(m + n)` time. Thus, the total time complexity is linear. · **Space:** O(m + n). This space is needed to store the two serialized strings. The length of the string for `root` is proportional to `m`, and for `subRoot` is proportional to `n`. The recursion stack for serialization also contributes up to `O(m)` space in the worst case.
**Pros:** Achieves linear time complexity, a significant improvement over the brute-force method.; Conceptually straightforward: reduces a tree problem to a string problem.
**Cons:** Requires significant extra space to store the serialized strings, which can be very large.; String concatenation and substring search can have high constant factor overhead compared to numeric operations.
### Explanation
To ensure the serialization is unambiguous, we must represent the tree's structure, including `null` children. A pre-order traversal (`Node -> Left -> Right`) is a common choice. For each node, we append its value. For a `null` child, we append a special marker like `'#'`. We also use a separator like `','` to distinguish between node values (e.g., to tell `12` apart from `1` and `2`).

After generating the string for `root` (`s1`) and `subRoot` (`s2`), we can use a built-in function like `String.contains()` in Java to perform the check. This check is typically implemented with an efficient algorithm like KMP, leading to a linear time complexity overall.

```java
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // Using StringBuilder for efficient string construction.
        StringBuilder rootString = new StringBuilder();
        serialize(root, rootString);
        
        StringBuilder subRootString = new StringBuilder();
        serialize(subRoot, subRootString);
        
        // The .toString() conversion creates the final strings.
        // String.contains() checks for the substring.
        return rootString.toString().contains(subRootString.toString());
    }

    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            // Use a special marker for null nodes to preserve structure.
            sb.append(",#");
            return;
        }
        // Prepend a separator to distinguish nodes, e.g., 12 from 1,2.
        sb.append(",").append(node.val);
        serialize(node.left, sb);
        serialize(node.right, sb);
    }
}
```
### Algorithm
*   Define a `serialize(node, stringBuilder)` function that performs a pre-order traversal.
*   To uniquely identify the structure, append a special marker (e.g., `"#"`) for `null` nodes and a separator (e.g., `","`) between values.
*   Generate the serialized string for `root` (`s1`) and `subRoot` (`s2`). It's important to start each serialization with a separator to handle edge cases (e.g., distinguishing a subtree with value `2` from a node with value `12`).
*   Use a standard library function to check if `s1` contains `s2`.
*   Return the result of the substring search.

## Merkle Hashing
The most efficient approach in practice is often Merkle Hashing. This technique avoids the overhead of creating and manipulating large strings by instead computing a numeric hash for each subtree. A hash is a number that uniquely represents the contents and structure of a subtree. If the hash of `subRoot` matches the hash of any subtree in `root`, we likely have a match. A final, direct comparison is done to confirm, just in case of a hash collision.
**Time:** O(m + n) on average. We traverse `root` (`O(m)`) and `subRoot` (`O(n)`). The `isSameTree` check (`O(n)`) is only performed on a hash match. With a good hash function, collisions are rare, making the verification cost negligible. In the worst case of many collisions, it could degrade to `O(m * n)`. · **Space:** O(m + n) in the worst case for the recursion stack. The space for storing hashes is minimal.
**Pros:** Very fast on average, with linear time complexity.; Avoids the overhead of large string creation, allocation, and searching.; Generally more space-efficient than string serialization as it only deals with numbers.
**Cons:** More complex to implement correctly than the other approaches.; Performance relies on a good hash function; a poor one could lead to many collisions, degrading performance to O(m * n).
### Explanation
This method works by performing two main traversals. First, we traverse `subRoot` to compute its hash value. This hash is calculated recursively in a post-order manner, where a parent node's hash is a function of its own value and the hashes of its left and right children. This ensures that both values and structure contribute to the final hash.

Second, we traverse the `root` tree. At each node, we compute the hash of the subtree rooted there using the same function. If this hash matches the target hash of `subRoot`, we perform an explicit `isSameTree` comparison to verify it's not a coincidental collision. Because numeric operations are very fast and good hash functions make collisions rare, this method is typically faster than string-based serialization.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private long subRootHash;
    private TreeNode subRootNode;
    private boolean matchFound = false;

    // Primes for hashing to mix the values
    private final long P1 = 31;
    private final long P2 = 37;
    private final long MOD = 1_000_000_007;

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        this.subRootNode = subRoot;
        // 1. Compute hash of the target subtree (subRoot)
        this.subRootHash = computeHash(subRoot);
        
        // 2. Traverse the main tree, compute hashes and check for match
        traverseAndCheck(root);
        
        return matchFound;
    }

    private void traverseAndCheck(TreeNode node) {
        if (node == null || matchFound) {
            return;
        }
        if (computeHash(node) == this.subRootHash) {
            if (isSameTree(node, this.subRootNode)) {
                matchFound = true;
                return;
            }
        }
        traverseAndCheck(node.left);
        traverseAndCheck(node.right);
    }

    private long computeHash(TreeNode node) {
        if (node == null) {
            return 0; // A consistent hash for null nodes
        }
        long leftHash = computeHash(node.left);
        long rightHash = computeHash(node.right);

        // Post-order processing: compute hash after children are processed
        // Offset val to handle negative values and 0, ensuring it's positive.
        long currentHash = (node.val + 10001 + (leftHash * P1) + (rightHash * P2)) % MOD;
        return currentHash;
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
```
*Note: The `traverseAndCheck` recomputes hashes, which is inefficient. A better implementation would compute all hashes once and store them, but this illustrates the concept.*
### Algorithm
*   Define a recursive function `computeHash(node)` that performs a post-order traversal and returns a numeric hash for the subtree at `node`.
*   The hash should be computed from the node's value and the hashes of its children: `hash = (node.val + left_hash * p1 + right_hash * p2) % MOD`. Use prime multipliers (`p1`, `p2`) and a large modulus (`MOD`) to minimize collisions.
*   First, call `computeHash(subRoot)` to calculate the `targetHash`.
*   Next, traverse the `root` tree. For each `node` in `root`, compute its subtree's hash.
*   If a computed hash matches `targetHash`, this indicates a potential match. To be certain, call a definitive `isSameTree(node, subRoot)` checker to handle the (rare) case of a hash collision.
*   If `isSameTree` returns `true`, a match is found. If the entire `root` tree is traversed without a confirmed match, return `false`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isSubtree ( TreeNode root , TreeNode subRoot ) { if ( root == null ) { return false ; } return dfs ( root , subRoot ) || isSubtree ( root . left , subRoot ) || isSubtree ( root . right , subRoot ); } private boolean dfs ( TreeNode root1 , TreeNode root2 ) { if ( root1 == null && root2 == null ) { return true ; } if ( root1 == null || root2 == null ) { return false ; } return root1 . val == root2 . val && dfs ( root1 . left , root2 . left ) && dfs ( root1 . right , root2 . right ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {TreeNode} subRoot * @return {boolean} */ var isSubtree =
  function (root, subRoot) {
    if (!root) return false;
    let dfs = function (root1, root2) {
      if (!root1 && !root2) {
        return true;
      }
      if (!root1 || !root2) {
        return false;
      }
      return (
        root1.val == root2.val &&
        dfs(root1.left, root2.left) &&
        dfs(root1.right, root2.right)
      );
    };
    return (
      dfs(root, subRoot) ||
      isSubtree(root.left, subRoot) ||
      isSubtree(root.right, subRoot)
    );
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isSubtree ( TreeNode * root , TreeNode * subRoot ) { if ( ! root ) return 0 ; return dfs ( root , subRoot ) || isSubtree ( root -> left , subRoot ) || isSubtree ( root -> right , subRoot ); } bool dfs ( TreeNode * root1 , TreeNode * root2 ) { if ( ! root1 && ! root2 ) return 1 ; if ( ! root1 || ! root2 ) return 0 ; return root1 -> val == root2 -> val && dfs ( root1 -> left , root2 -> left ) && dfs ( root1 -> right , root2 -> right ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isSubtree ( self , root : TreeNode , subRoot : TreeNode ) -> bool : def dfs ( root1 , root2 ): if root1 is None and root2 is None : return True if root1 is None or root2 is None : return False return ( root1 . val == root2 . val and dfs ( root1 . left , root2 . left ) and dfs ( root1 . right , root2 . right ) ) if root is None : return False return ( dfs ( root , subRoot ) or self . isSubtree ( root . left , subRoot ) or self . isSubtree ( root . right , subRoot ) )
```