Subtree of Another Tree Java Solution

This solution addresses the classic binary tree subtree problem where we need to determine if one tree is a complete subtree of another tree structure.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input trees be empty, and how should we handle that case?
2. Are we allowed to modify the input trees during our solution, or must we work with immutable copies?
3. What is the expected time complexity constraint for this problem? Should we aim for O(n + m) where n and m are the sizes of the trees?
4. Do we need to handle duplicate node values in the trees?
5. Should we return a boolean indicating whether subtree exists, or should we return the actual matching subtree node?

Restatement in my own words: Given two binary trees, root and subRoot, determine whether the second tree (subRoot) is a subtree of the first tree (root). A subtree means that there exists a node in root such that the tree rooted at that node is identical to subRoot.

Clarifying inputs, outputs, and constraints:

• Input: Two binary tree nodes (root and subRoot) where each node contains an integer value, left child, and right child
• Output: Boolean indicating whether subRoot exists as a subtree within root
• Constraints:
  • Tree nodes can have values in the range [-10⁴, 10⁴]
  • Number of nodes in each tree can be up to 2×10⁴
  • Both trees can be empty (null)
  • Node values may repeat

Assumptions I'm making:

• The trees are standard binary trees with left and right children
• We're comparing structural identity, not just value equality
• The input trees can be mutated during solution process (not a strict requirement but allows for cleaner implementation)
• Empty tree is considered a subtree of any tree (including another empty tree)

Data shape and hidden structure:

• Both inputs are binary trees with potential for recursive structure
• The problem exhibits a nested recursive pattern where we must check if one tree matches another at each node position
• The structure suggests a two-level recursive approach: first traverse the main tree, then compare subtrees
• There's an implicit graph structure in how we can match substructures across different positions in the main tree

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern is Tree Traversal with Subtree Matching. This problem involves comparing tree structures, which naturally maps to tree traversal algorithms.

Wording that signals the pattern

• "Subtree of Another Tree" - explicitly mentions subtree matching
• The requirement to find if one tree exists as a subtree within another tree - this is classic subtree pattern matching
• The need to compare tree structures recursively - suggests tree traversal approach

Why this problem fits that pattern

This is a classic tree pattern where we need to:

1. Traverse the main tree to find potential root matches
2. For each candidate, verify if the subtree structure matches exactly
3. This requires recursive tree comparison logic that's commonly seen in tree problems

Core insight needed to solve it

The key insight is that we need to:

1. Iterate through the main tree to find nodes that could potentially match the root of the target subtree
2. For each candidate node, perform an exact structural match with the target subtree using recursive tree comparison
3. Early termination - once we find a match, we can return immediately

This pattern is fundamental to tree problems where we need to check structural equality or containment between tree structures. The solution requires combining tree traversal (to find candidates) with tree matching (to verify exact structure).

3. Approach Evolution

My first instinct is to use a brute force approach where I traverse the main tree and for each node, check if the subtree starting from that node matches the target subtree. This would be O(n×m) time where n is the size of the main tree and m is the size of the subtree, because in the worst case, I might have to compare the entire subtree for each node in the main tree.

But that's O(n²) in the worst case if both trees are of similar size, and I can do better. Let me think about how to optimize this.

I notice that if I use a recursive approach, I can avoid redundant comparisons. The key insight is that for each node in the main tree, I need to check if the subtree rooted at that node matches the target subtree. This means I can recursively compare trees, but I also need to explore all nodes in the main tree as potential roots.

Let me think about this more carefully. If I'm at a node in the main tree and want to check if it matches the target subtree, I need to compare:

1. The current node's value with the target root's value
2. The left subtree of current node with the left subtree of target
3. The right subtree of current node with the right subtree of target

But I also need to explore all nodes in the main tree as potential starting points for matching. So I can do a DFS traversal of the main tree, and at each node, check if that node is the root of a matching subtree.

This approach reduces to O(n×m) time where n is the size of main tree and m is the size of subtree, but in practice it's more efficient than brute force because we can early terminate when values don't match.

The key invariant that must hold is that at any point in the traversal, if we're checking whether a subtree matches, all corresponding nodes must have equal values and the same structure.

Here's my final approach:

1. Use DFS on the main tree to traverse each node
2. At each node, check if that node can be the root of a matching subtree using a helper function
3. The helper function recursively compares two trees for structural and value equality
4. If any node matches, return true; otherwise continue traversal

This is O(n×m) time and O(h) space where h is the height of the main tree (due to recursion stack), which is optimal for this problem since we might need to check every node in the worst case.

The approach is clean, readable, and handles all edge cases properly - we can't mutate the input trees since that would violate constraints, so we must do a structural comparison.

4. Data Structure Choice

For this subtree matching problem, I'll use a combination of:

Primary Data Structures:

1. Binary Tree Nodes - The standard TreeNode class with val, left, and right fields. This is the core input structure that we must work with.

2. Recursive call stack - Implicitly used for the tree traversal approach. While not explicitly managed, it's crucial to understand that we're using the system call stack for our recursive solution.

Why These Choices Are Optimal:

The TreeNode structure is necessary because it's the fundamental building block of our input trees. We cannot avoid using it since we're comparing actual tree structures.

The recursive call stack is the natural choice for tree traversal problems. It's clean, readable, and mirrors the intuitive recursive structure of tree problems. The stack space is O(h) where h is the height of the tree, which is acceptable and expected for this type of problem.

Space-Time Trade-offs:

• Using the implicit call stack is optimal for space complexity, avoiding the need to explicitly manage a stack data structure
• Time complexity remains O(m×n) where m and n are the sizes of the trees, which is the best we can achieve for this problem since we must potentially check every node in the main tree against every node in the subtree candidate

Helper Structure:

No additional helper data structures are needed beyond what's required by the recursive approach. The solution naturally works with the existing tree node structure, making it clean and efficient.

The chosen approach leverages the natural recursive structure of trees rather than introducing additional complexity through custom data structures.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works:

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

Step 1: Start with root node 3, subRoot = [4,1,2]

• Call isSameTree(3, 4) → false (values don't match)
• Continue to left subtree: root = 4, subRoot = [4,1,2]
• Call isSameTree(4, 4) → true (values match)
• Now check if trees are identical by calling isSameTree(4, 4) and recursively checking left and right subtrees

Step 2: When we find matching root values (node 4), we check if the entire subtree matches:

• isSameTree(4, 4) → true (root values match)
• isSameTree(1, 1) → true (left children match)
• isSameTree(2, 2) → true (right children match)

Step 3: Return true because we found a matching subtree

The algorithm maintains the key invariant that we only proceed to check subtree equality when root values match. This prevents unnecessary comparisons and ensures we don't miss any potential matches.

For the edge case where subRoot is null, we return true immediately since an empty tree is a subtree of any tree.

The algorithm terminates correctly because:

1. We traverse the main tree once (O(n) time)
2. For each node that matches subRoot's root value, we do O(m) work to check equality
3. The total work is bounded by O(n × m) where n and m are the sizes of the trees
4. We never revisit nodes once we've determined they don't match

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    // Base case: if main tree is empty, no subtree can exist
    if (root == null) return false;
    
    // Check if current root matches subRoot's root value
    if (root.val == subRoot.val) {
        // If values match, check if entire subtrees are identical
        if (isSameTree(root, subRoot)) {
            return true;
        }
    }
    
    // Continue searching in left and right subtrees
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

private boolean isSameTree(TreeNode s, TreeNode t) {
    // If both nodes are null, trees are identical at this point
    if (s == null && t == null) return true;
    
    // If only one is null, trees differ
    if (s == null || t == null) return false;
    
    // If values don't match, trees differ
    if (s.val != t.val) return false;
    
    // Recursively check left and right subtrees
    return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}

6. Java Solution

/**
 * 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) {
        // Base case: if root is null, there's no subtree to check
        if (root == null) {
            return false;
        }
        
        // Check if current tree rooted at 'root' matches subRoot
        if (isSameTree(root, subRoot)) {
            return true;
        }
        
        // Recursively check left and right subtrees
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    
    /**
     * Helper method to check if two trees are identical
     */
    private boolean isSameTree(TreeNode s, TreeNode t) {
        // If both nodes are null, they match
        if (s == null && t == null) {
            return true;
        }
        
        // If only one is null, they don't match
        if (s == null || t == null) {
            return false;
        }
        
        // If values don't match, they don't match
        if (s.val != t.val) {
            return false;
        }
        
        // Recursively check left and right subtrees
        return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
}

This solution uses a two-tiered approach:

1. For each node in the main tree, we check if the subtree rooted at that node matches the target subtree
2. We use a helper method to determine if two trees are identical in structure and values

The implementation handles the recursive nature cleanly by:

• Using base cases for null nodes
• Checking structural identity at each level
• Combining results with logical OR to find any matching subtree

7. Complexity Analysis

Time Complexity: O(M × N) where M is the number of nodes in the subtree and N is the number of nodes in the main tree.

The algorithm performs a preorder traversal of the main tree, visiting each node once. For each node in the main tree, it potentially calls isSameTree which compares all nodes in the subtree. In the worst case, we might have to compare all M nodes of the subtree with all N nodes in the main tree.

In the best case, when we find a match early, we can terminate earlier. However, in the worst case where no match exists, we must check every node in the main tree to see if it matches the root of our target subtree.

Space Complexity: O(max(M, N)) where M is the height of the subtree and N is the height of the main tree.

The space complexity comes from the recursive call stack:

• In the worst case, we might have to traverse all nodes in both trees recursively
• The maximum depth of recursion is bounded by the maximum height of either tree
• For a balanced binary tree, this would be O(log M + log N)
• For a skewed tree, it could be O(M + N)

The solution is optimal for this problem since we must examine each node at least once to determine if a subtree exists, making O(M × N) the best possible time complexity. The space complexity is also optimal as it's directly proportional to the maximum recursion depth needed.

The algorithm avoids unnecessary work by early termination when a subtree match is found, making it practical for most real-world inputs where matches occur earlier in the traversal.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty trees: If either root or subRoot is null, we must handle this carefully. The problem definition typically considers an empty subtree as existing in any tree (including an empty tree), but this can vary by implementation.
• Single node trees: When one or both trees have only one node, special handling is required to avoid null pointer exceptions and ensure proper comparison.

Duplicate Values and Repeated States

• Duplicate node values: Trees can have duplicate values, which means a subtree with matching structure and values might appear multiple times in the main tree. The algorithm must correctly identify any occurrence.
• Multiple matching subtrees: If there are multiple occurrences of the target subtree, we should return true as soon as we find any match, not continue searching unnecessarily.

Boundary Conditions

• Null root or subRoot: The algorithm must handle cases where one or both parameters are null. Conventionally, a null subtree is considered to exist in any tree.
• Size mismatch: If subRoot has more nodes than root, it's impossible for subRoot to be a subtree of root.

Common Implementation Mistakes

• Incorrect base case handling: Failing to properly check for null nodes before comparing values can lead to NullPointerException.
• Improper tree traversal: Not correctly traversing the main tree to check all possible starting points for subtree matching.
• Overlapping comparisons: Comparing the same nodes multiple times due to incorrect traversal logic or recursion depth.
• Not resetting state properly: When checking subtree equality, the comparison must be done from the root of the candidate subtree, not from a partial match.

Implementation-specific Pitfalls

• Inefficient recursion: Using recursive approaches without proper termination conditions can lead to stack overflow for very deep trees.
• Incorrect subtree matching logic: Confusing the structure matching with value matching, or not ensuring that both the structure and values align perfectly.
• Missing early termination: Not optimizing to stop as soon as a match is found or when it's clear no match can occur.

9. Alternative Approaches

There are several alternative approaches to solving the subtree matching problem, each with different trade-offs:

1. String Serialization Approach Serialize both trees into strings and use string matching algorithms like KMP or Rabin-Karp. For each tree, we can serialize it using pre-order traversal with null markers (e.g., "1,2,null,null,3,null,null"). Then we check if the serialized subtree string appears as a substring in the main tree's serialization. This approach has O(n+m) time complexity for string matching but requires additional space for the serialized strings and can be complex to handle edge cases properly.

2. Hash-based Approach Compute hash values for subtrees using rolling hash techniques and compare hashes to quickly identify potential matches. This approach can achieve O(n+m) average time complexity but has a higher constant factor due to hash collision handling and requires careful implementation to avoid false positives.

3. Nested DFS with Early Termination Instead of checking all nodes, we can optimize by first comparing root values and only proceeding with full subtree matching when there's a potential match. This can reduce the number of full comparisons in practice but doesn't change the worst-case complexity.

The chosen solution is preferred because it's more straightforward to implement correctly, has predictable performance characteristics, and handles edge cases naturally without additional complexity from hash collision resolution or string operations.

// Alternative: String serialization approach (not implemented due to complexity)
// Alternative: Hash-based approach (not implemented due to collision handling complexity)

10. Test Cases

// Test case 1: Basic matching subtree
// Input: root = [3,4,5,1,2], subRoot = [4,1,2]
// Expected: true
TreeNode root1 = new TreeNode(3);
root1.left = new TreeNode(4);
root1.right = new TreeNode(5);
root1.left.left = new TreeNode(1);
root1.left.right = new TreeNode(2);

TreeNode subRoot1 = new TreeNode(4);
subRoot1.left = new TreeNode(1);
subRoot1.right = new TreeNode(2);

// Test case 2: No matching subtree
// Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
// Expected: false
TreeNode root2 = new TreeNode(3);
root2.left = new TreeNode(4);
root2.right = new TreeNode(5);
root2.left.left = new TreeNode(1);
root2.left.right = new TreeNode(2);
root2.left.right.right = new TreeNode(0);

TreeNode subRoot2 = new TreeNode(4);
subRoot2.left = new TreeNode(1);
subRoot2.right = new TreeNode(2);

// Test case 3: Empty subtree
// Input: root = [1,2,3], subRoot = []
// Expected: true (empty tree is subtree of any tree)
TreeNode root3 = new TreeNode(1);
root3.left = new TreeNode(2);
root3.right = new TreeNode(3);
TreeNode subRoot3 = null;

// Test case 4: Identical trees
// Input: root = [1,2,3], subRoot = [1,2,3]
// Expected: true
TreeNode root4 = new TreeNode(1);
root4.left = new TreeNode(2);
root4.right = new TreeNode(3);
TreeNode subRoot4 = new TreeNode(1);
subRoot4.left = new TreeNode(2);
subRoot4.right = new TreeNode(3);

// Test case 5: Single node match
// Input: root = [1], subRoot = [1]
// Expected: true
TreeNode root5 = new TreeNode(1);
TreeNode subRoot5 = new TreeNode(1);

// Test case 6: Duplicate values in tree
// Input: root = [1,1,1,1,1], subRoot = [1,1,1]
// Expected: true (first subtree matches)
TreeNode root6 = new TreeNode(1);
root6.left = new TreeNode(1);
root6.right = new TreeNode(1);
root6.left.left = new TreeNode(1);
root6.left.right = new TreeNode(1);

TreeNode subRoot6 = new TreeNode(1);
subRoot6.left = new TreeNode(1);
subRoot6.right = new TreeNode(1);

The test cases cover:

• Basic matching subtree scenario
• Non-matching subtree (edge case with extra node)
• Empty subtree edge case
• Identical trees case
• Single node matching
• Duplicate values in tree structure

Each test case uses a clean, isolated setup that clearly demonstrates the expected behavior for different scenarios. The examples are chosen to exercise various aspects of the algorithm including structural matching, value comparison, and edge condition handling.

11. Final Summary

The core idea is to efficiently determine if one binary tree (subRoot) exists as a subtree within another binary tree (root) by leveraging a two-step approach: first validating structural and value matches at candidate nodes, then recursively verifying subtree equality. This solution works because it systematically traverses the main tree to find potential root matches, then performs precise structural verification only when necessary. The approach is efficient with O(m×n) time complexity where m and n are the sizes of the trees, and uses minimal additional space through iterative traversal with a stack. The key insight is avoiding redundant full tree comparisons by only checking candidate matches that share the same root value, making it optimal for the given constraints.