easy Subtree of Another Tree

Problem Statement

Given the roots of two binary trees, root and subRoot, return true if subRoot is a subtree of root. Otherwise, return false.

A subtree of a binary tree is a part of the tree that includes a node and all of its descendants. The tree tree could also be considered as a subtree of itself.

Examples

Example 1

• Input: root = [3, 6, 5, 1, 4], subRoot = [6, 1, 4]

• Expected Output: true
• Explanation: The subtree starting at node 6 in root has the same structure and values as subRoot.

Example 2

• Input: root = [3, 4, 5, null, 2, null, 1], subRoot = [4, null, 2]

• Expected Output: true
• Explanation: The subtree rooted at node 4 in root matches the structure and values of subRoot.

Example 3

• Input: root = [3, 4, 5, 1, 2, null, null, 0], subRoot = [4, 1, 2]

• Expected Output: false
• Explanation: While node 4 exists in root, its subtree structure is different because of the extra node 0.

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].
• -10⁴ <= root.val <= 10⁴
• -10⁴ <= subRoot.val <= 10⁴

Solution

In this problem, the goal is to check whether subRoot is a subtree of root. We use a recursive algorithm that traverses the entire root tree, comparing each node's subtree with subRoot. The algorithm checks if the trees rooted at the current node of root and subRoot are identical. If they are, the function returns true. If not, the algorithm recursively checks the left and right subtrees of root. This method ensures that all possible subtrees of root are examined to see if they match subRoot.

We use a helper function to compare two trees. It determines if both trees have the same structure and node values. It recursively checks the left and right children of both trees. The algorithm relies on this helper function to determine if two trees are identical. If at any point the current subtree of root matches subRoot, we return true, otherwise, we continue searching the rest of root.

Step-by-step Algorithm

1. Base Case: Check if subRoot is null:

   • If subRoot is null, return true. This is because an empty tree is always a subtree of any tree.

2. Base Case: Check if root is null:

   • If root is null and subRoot is not null, return false. This is because a non-empty tree cannot be a subtree of an empty tree.

3. Check if the current subtree rooted at root matches subRoot:

   • Call the helper function isSameTree(root, subRoot) to check if the subtree rooted at the current node of root is identical to subRoot. This comparison involves:
     • If both nodes are null, return true (both are identical).
     • If one of the nodes is null and the other is not, return false (they cannot be identical).
     • If the values of the current nodes are different, return false (the trees cannot be identical).
     • If the values of the current nodes are the same, recursively check if the left and right subtrees of both trees are identical by calling isSameTree on their respective left and right children.

4. Recursively check the left and right subtrees of root:

   • If the current subtree rooted at root does not match subRoot, recursively call isSubtree(root.left, subRoot) and isSubtree(root.right, subRoot) to check the left and right subtrees of root.

5. Return the result:

   • If at any point the trees match, return true. If no subtree matches subRoot, return false.

Algorithm Walkthrough

Input: root = [3, 6, 5, 1, 4], subRoot = [6, 1, 4]):

1. Starting at the root node of root (node 3):

   • Current Node in root: 3
   • Comparing with subRoot (node 6):
     • Node values are different (3 != 6), so we move forward to check the left and right subtrees of root.

2. Checking the left subtree of root:

   • Current Node in root: 6 (left child of node 3)

   • Comparing with subRoot (node 6):

     • Node values are the same (6 == 6), so we now check the left and right subtrees of this node to see if they also match.

   • Comparing the left subtrees of node 6 in root and subRoot:

     • Left child of node 6 in root: 1
     • Left child of node 6 in subRoot: 1
     • Comparison:
       • Node values are the same (1 == 1), and both nodes have no further children (both left and right children are null).
     • Result: The left subtrees are identical.

   • Comparing the right subtrees of node 6 in root and subRoot:

     • Right child of node 6 in root: 4
     • Right child of node 6 in subRoot: 4
     • Comparison:
       • Node values are the same (4 == 4), and both nodes have no further children (both left and right children are null).
     • Result: The right subtrees are identical.

3. Conclusion

   • Since both the left and right subtrees of node 6 in root match those in subRoot, the trees are identical.
   • The helper function isSameTree(root, subRoot) returns true.

4. Final Step

   • The isSubtree function also returns true, confirming that subRoot is indeed a subtree of root.

Code

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     // Constructor for creating a new node
//     TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//     }
// }

public class Solution {

  public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    // If subRoot is null, it is always a subtree (an empty tree is a subtree of any tree)
    if (subRoot == null) {
      return true;
    }

    // If root is null but subRoot is not, return false (no subtree can exist in an empty tree)
    if (root == null) {
      return false;
    }

    // Check if the current node's subtree matches subRoot
    if (isSameTree(root, subRoot)) {
      return true;
    }

    // Otherwise, recursively check left and right subtrees of root
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
  }

  private boolean isSameTree(TreeNode s, TreeNode t) {
    // If both trees are null, they are identical
    if (s == null && t == null) {
      return true;
    }

    // If one is null and the other is not, they are not identical
    if (s == null || t == null) {
      return false;
    }

    // If the values of the current nodes are not equal, they are not identical
    if (s.val != t.val) {
      return false;
    }

    // Recursively check if both left and right subtrees are identical
    return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
  }

  public static void main(String[] args) {
    // Example 1
    // Creating root tree: [3, 6, 5, 1, 4]
    TreeNode root = new TreeNode(3);
    root.left = new TreeNode(6);
    root.right = new TreeNode(5);
    root.left.left = new TreeNode(1);
    root.left.right = new TreeNode(4);

    // Creating subRoot tree: [6, 1, 4]
    TreeNode subRoot = new TreeNode(6);
    subRoot.left = new TreeNode(1);
    subRoot.right = new TreeNode(4);

    // Creating a Solution object to test the method
    Solution solution = new Solution();

    // Testing the isSubtree method with the example
    boolean result = solution.isSubtree(root, subRoot);

    // Print the result (Expected: true)
    System.out.println("Is subRoot a subtree of root? " + result);
  }
}

Complexity Analysis

Time Complexity

• In the worst case, for every node in the root tree, we call the isSameTree() method to compare it with the subRoot. This results in a time complexity of , where:
  • n is the number of nodes in the root tree.
  • m is the number of nodes in the subRoot tree.
• The isSameTree() method itself takes time as it compares all nodes in subRoot with the corresponding nodes in root.
• Therefore, the overall time complexity is .

Space Complexity

• The space complexity is determined by the depth of the recursion, which depends on the height of the trees.
• In the worst case (for a completely unbalanced tree), the height of the tree could be for root and for subRoot.
• Thus, the space complexity is , where h1 and h2 are the heights of the root and subRoot trees, respectively. In the worst case, this could be if both trees are skewed.

An Alternate Approach Using Tree Hash

In the first approach, the time complexity was , where N is the number of nodes in root and M is the number of nodes in subRoot. To optimize this, we use a hashing-based approach.

In this approach, we calculate the hash value for each subtree in root and store it. Then, we calculate the hash for subRoot and compare it with the stored hashes from root. If a match is found, we can immediately conclude that subRoot is a subtree of root. This optimization reduces the comparison time and improves efficiency by leveraging hashing techniques.

The overall approach is efficient because:

• Instead of comparing entire subtrees at each node, we convert subtrees into hashes, reducing the need for full comparisons.
• We use two prime numbers to generate unique hashes, minimizing the chances of collisions and ensuring correctness.

Step-by-step Algorithm

1. Initialize constants and data structures:

   • Set two prime constants MOD_PRIME_1 and MOD_PRIME_2 for hashing to minimize hash collisions.
   • Create a list hashStore to store the hashes of all subtrees in root.

2. Define the calculateHashForSubtree function:

   • Base Case: If the current node is null, return a default hash value {3, 7} to handle empty subtrees. Here, you can return any pair of prime numbers.

   • Recursively calculate the hashes for the left and right subtrees of the current node by calling calculateHashForSubtree on both.

   • Hash Calculation For the First Hash of the Pair:

     • Left Shift the Left Subtree Hash: Take the first hash of the left subtree and left shift it by a fixed value (e.g., 5). This gives more weight to the left subtree.

     • Left Shift the Right Subtree Hash: Take the first hash of the right subtree and left shift it by 1 (or another fixed value). This adds the right subtree’s contribution with slightly less weight.

     • Add Node’s Value: Add the shifted values of the left and right subtree hashes to the current node's value. This combines the contributions of the subtrees and the current node.

     • Take MOD_1: Apply MOD_PRIME_1 to the result to avoid overflow and keep the hash value within a manageable range.

   • Hash Calculation For the Second Hash of the Pair:

     • Left Shift the Left Subtree Hash: Take the second hash of the left subtree and left shift it by a different fixed value (e.g., 7). This gives a different weight to the left subtree for the second hash.

     • Left Shift the Right Subtree Hash: Take the second hash of the right subtree and left shift it by 1 (or another fixed value). This adds the right subtree’s contribution with a slight weight.

     • Add Node’s Value: Add the shifted values of the left and right subtree hashes to the current node's value to compute the second part of the hash.

     • Take MOD_2: Apply MOD_PRIME_2 to the result to avoid overflow and ensure the second hash value remains within the bounds of the prime.

3. Hash all subtrees in root:

   • Call calculateHashForSubtree(root, true) to compute and store the hashes of all subtrees in root.

4. Hash the subRoot tree:

   • Call calculateHashForSubtree(subRoot, false) to compute the hash for subRoot. We do not store this hash.

5. Compare the subRoot hash with stored hashes:

   • Loop through the hashStore list and compare the hash of subRoot with each stored hash.
   • If a match is found (both hash parts are equal), return true because subRoot is a subtree of root.

6. Return false if no match is found:

   • If no matching hash is found in hashStore, return false as subRoot is not a subtree of root.

Algorithm Walkthrough

Input: root = [3, 6, 5, 1, 4], subRoot = [6, 1, 4]

1. Step 1: Initialize Constants and Data Structures:

   • Initialize MOD_PRIME_1 = 1000000007 and MOD_PRIME_2 = 2147483647.
   • Initialize an empty list hashStore to store hashes of subtrees.

2. Step 2: Compute Hash for root:

   • Start at the root node of root (node 3).
   • Call calculateHashForSubtree on node 3:
     • Compute hashes for left and right subtrees of node 3.

   Left Subtree of Node 3:

   • Node 3's left child is node 6.

   • Call calculateHashForSubtree on node 6:

     • Compute hashes for left and right subtrees of node 6.

     Left Subtree of Node 6:

     • Node 6's left child is node 1.
     • Node 1 has no children, so return default hash {3, 7} for both left and right children.
     • Compute the hash for node 1 using the left and right subtree hashes:
       • Hash for node 1: ( (3 << 5) + (3 << 1) + 1 ) % MOD_PRIME_1 = 101, ( (7 << 7) + (7 << 1) + 1 ) % MOD_PRIME_2 = 897.
     • Store this hash {101, 897} in hashStore.

     Right Subtree of Node 6:

     • Node 6's right child is node 4.
     • Node 4 has no children, so return default hash {3, 7} for both left and right children.
     • Compute the hash for node 4 using the left and right subtree hashes:
       • Hash for node 4: ( (3 << 5) + (3 << 1) + 4 ) % MOD_PRIME_1 = 104, ( (7 << 7) + (7 << 1) + 4 ) % MOD_PRIME_2 = 900.
     • Store this hash {104, 900} in hashStore.

   • Compute the hash for node 6 using the left and right subtree hashes (hashes of nodes 1 and 4):

     • Hash for node 6: ( (101 << 5) + (104 << 1) + 6 ) % MOD_PRIME_1 = 3338, ( (897 << 7) + (900 << 1) + 6 ) % MOD_PRIME_2 = 115841.
     • Store this hash {3338, 115841} in hashStore.

   Right Subtree of Node 3:

   • Node 3's right child is node 5.

   • Node 5 has no children, so return default hash {3, 7} for both left and right children.

   • Compute the hash for node 5:

     • Hash for node 5: ( (3 << 5) + (3 << 1) + 5 ) % MOD_PRIME_1 = 105, ( (7 << 7) + (7 << 1) + 5 ) % MOD_PRIME_2 = 901.
     • Store this hash {105, 901} in hashStore.

   • Compute the hash for node 3 using the left and right subtree hashes (hashes of nodes 6 and 5):

     • Hash for node 3: ( (3338 << 5) + (105 << 1) + 3 ) % MOD_PRIME_1 = 107899, ( (115841 << 7) + (901 << 1) + 3 ) % MOD_PRIME_2 = 14826435.
     • Store this hash {107899, 14826435} in hashStore.

3. Step 3: Compute Hash for subRoot:

   • Call calculateHashForSubtree on subRoot (node 6):
     • The process is the same as when we computed the hash for the left subtree of node 3 in root.
     • Hash for subRoot: {3338, 115841}.

4. Step 4: Compare Hashes:

   • Loop through hashStore and check if any hash matches {3338, 115841} (the hash of subRoot).
   • A match is found in hashStore, confirming that subRoot is a subtree of root.

5. Step 5: Return true:

   • Since a matching hash was found, return true.

Code

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

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     // Constructor to create a new node
//     TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//     }
// }

public class Solution {

    // CONSTANTS for hashing calculations
    final int MOD_PRIME_1 = 1000000007;
    final int MOD_PRIME_2 = 2147483647;

    // List to store hash values of all subtrees in the main tree
    List<long[]> hashStore = new ArrayList<>();

    // Method to compute hash for each subtree and store in hashStore if needed
    long[] calculateHashForSubtree(TreeNode currentNode, boolean storeHash) {
        // If node is null, return default hash values for null nodes
        if (currentNode == null) {
            return new long[] { 3, 7 }; // Default hashes for null nodes
        }

        // Recursively calculate hashes for the left and right subtrees
        long[] leftHash = calculateHashForSubtree(currentNode.left, storeHash);
        long[] rightHash = calculateHashForSubtree(currentNode.right, storeHash);

        // Compute the hash values for the current node using the left and right subtree hashes
        long left1 = (leftHash[0] << 5) % MOD_PRIME_1; // Shift and mod for first prime
        long right1 = (rightHash[0] << 1) % MOD_PRIME_1; // Shift and mod for first prime
        long left2 = (leftHash[1] << 7) % MOD_PRIME_2; // Shift and mod for second prime
        long right2 = (rightHash[1] << 1) % MOD_PRIME_2; // Shift and mod for second prime

        // Compute final hash values for the current node
        long[] currentHash = {
                (left1 + right1 + currentNode.val) % MOD_PRIME_1,
                (left2 + right2 + currentNode.val) % MOD_PRIME_2 };

        // If storeHash is true, add this hash to the hashStore list
        if (storeHash) {
            hashStore.add(currentHash);
        }

        // Return the hash pair for the current subtree
        return currentHash;
    }

    // Method to check if subRoot is a subtree of root
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        // First, calculate and store hashes for all subtrees in the root tree
        calculateHashForSubtree(root, true);

        // Now calculate the hash for the subRoot tree
        long[] subRootHash = calculateHashForSubtree(subRoot, false);

        // Check if any hash in hashStore matches the subRoot hash
        for (long[] storedHash : hashStore) {
            // Compare both parts of the hash
            if (storedHash[0] == subRootHash[0] && storedHash[1] == subRootHash[1]) {
                return true; // Match found, subRoot is a subtree of root
            }
        }

        // If no match was found, return false
        return false;
    }

    public static void main(String[] args) {
        // Example 1
        // Creating root tree: [3, 6, 5, 1, 4]
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(6);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(4);

        // Creating subRoot tree: [6, 1, 4]
        TreeNode subRoot = new TreeNode(6);
        subRoot.left = new TreeNode(1);
        subRoot.right = new TreeNode(4);

        // Creating a Solution object to test the method
        Solution solution = new Solution();

        // Testing the isSubtree method with the example
        boolean result = solution.isSubtree(root, subRoot);

        // Print the result (Expected: true)
        System.out.println("Is subRoot a subtree of root? " + result);
    }
}

Complexity Analysis

Time Complexity

• n is the number of nodes in the root tree, and m is the number of nodes in subRoot.
• We traverse each node in both root and subRoot trees to compute their hash values. This takes for root and for subRoot.
• After computing the hashes, we compare the hash of subRoot with all stored hashes from root, which takes . Thus, the total time complexity is .

Space Complexity

• We store the hashes of all subtrees in root, which requires space.
• Additionally, the recursive depth (call stack) for the calculateHashForSubtree function depends on the height of the trees, which is for root and for subRoot. Therefore, the total space complexity is .