Subtree of Another Tree

• 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).

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean isSubtree(TreeNode root, TreeNode subRoot) {18        if (root == null) {19            return false;20        }21        if (isSameTree(root, subRoot)) {22            return true;23        }24        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);25    }26 27    private boolean isSameTree(TreeNode p, TreeNode q) {28        if (p == null && q == null) {29            return true;30        }31        if (p == null || q == null || p.val != q.val) {32            return false;33        }34        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);35    }36}

• 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.

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.

1class Solution {2    public boolean isSubtree(TreeNode root, TreeNode subRoot) {3        // Using StringBuilder for efficient string construction.4        StringBuilder rootString = new StringBuilder();5        serialize(root, rootString);6        7        StringBuilder subRootString = new StringBuilder();8        serialize(subRoot, subRootString);9        10        // The .toString() conversion creates the final strings.11        // String.contains() checks for the substring.12        return rootString.toString().contains(subRootString.toString());13    }14 15    private void serialize(TreeNode node, StringBuilder sb) {16        if (node == null) {17            // Use a special marker for null nodes to preserve structure.18            sb.append(",#");19            return;20        }21        // Prepend a separator to distinguish nodes, e.g., 12 from 1,2.22        sb.append(",").append(node.val);23        serialize(node.left, sb);24        serialize(node.right, sb);25    }26}

• 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.

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    private long subRootHash;6    private TreeNode subRootNode;7    private boolean matchFound = false;8 9    // Primes for hashing to mix the values10    private final long P1 = 31;11    private final long P2 = 37;12    private final long MOD = 1_000_000_007;13 14    public boolean isSubtree(TreeNode root, TreeNode subRoot) {15        this.subRootNode = subRoot;16        // 1. Compute hash of the target subtree (subRoot)17        this.subRootHash = computeHash(subRoot);18        19        // 2. Traverse the main tree, compute hashes and check for match20        traverseAndCheck(root);21        22        return matchFound;23    }24 25    private void traverseAndCheck(TreeNode node) {26        if (node == null || matchFound) {27            return;28        }29        if (computeHash(node) == this.subRootHash) {30            if (isSameTree(node, this.subRootNode)) {31                matchFound = true;32                return;33            }34        }35        traverseAndCheck(node.left);36        traverseAndCheck(node.right);37    }38 39    private long computeHash(TreeNode node) {40        if (node == null) {41            return 0; // A consistent hash for null nodes42        }43        long leftHash = computeHash(node.left);44        long rightHash = computeHash(node.right);45 46        // Post-order processing: compute hash after children are processed47        // Offset val to handle negative values and 0, ensuring it's positive.48        long currentHash = (node.val + 10001 + (leftHash * P1) + (rightHash * P2)) % MOD;49        return currentHash;50    }51 52    private boolean isSameTree(TreeNode p, TreeNode q) {53        if (p == null && q == null) return true;54        if (p == null || q == null || p.val != q.val) return false;55        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);56    }57}

Note: The traverseAndCheck recomputes hashes, which is inefficient. A better implementation would compute all hashes once and store them, but this illustrates the concept.