Subtree of Another Tree Algorithm Solution

The subtree of another tree problem requires determining whether one binary tree exists as a subtree within another binary tree. This classic tree traversal problem tests understanding of tree comparison algorithms and efficient subtree detection techniques.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that both trees will have at most 10⁴ nodes, or should we consider larger inputs?
2. Can the input trees be modified during our solution (i.e., can we mutate node references)?
3. Should we return a boolean indicating whether subtree exists, or should we return the actual matching subtree node?
4. Do we need to handle null inputs gracefully (e.g., if either root is null)?
5. What is the expected time complexity for follow-up optimization (e.g., O(n + m) where n and m are tree sizes)?

Restatement of the pattern in my own words: This is a canonical tree matching problem where we're tasked with determining whether one tree (the "subtree") exists as a subtree within another tree (the "main tree"). A subtree includes all descendants of a node, including the node itself. The challenge involves traversing and comparing tree structures to find an exact match.

Signal words and constraint shape that point to this pattern:

• "Subtree", "contains", "matches exactly", "identical structure"
• Tree node values and structure comparison
• Problems asking to find a specific tree pattern within a larger tree structure

Assumptions I am making:

• Both inputs are valid binary trees (not null unless explicitly handled)
• The comparison requires exact structural and value matching
• We're not modifying the input trees during traversal

Pattern suitability for different scenarios: This pattern is best suited for static tree comparison problems where we have complete access to both trees and need to verify structural inclusion. It's not ideal for streaming or online scenarios where tree structures change dynamically, as it requires full traversal of both trees to establish containment relationships.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Check if one tree is a subtree of another"
• "Is the structure and values of one tree contained within another?"
• "Find if a given tree exists as a subtree in a larger tree"
• Trees with potentially large size (up to 2000 nodes)
• Need for structural matching between two tree data structures

Why this pattern fits better than alternatives: This is fundamentally a tree matching problem that requires checking if one tree structure exists as a subtree within another. Unlike array-based problems, we're dealing with hierarchical structures where:

• We must match both structure and values recursively
• The subtree can appear at any level in the parent tree
• We need to handle tree traversal and structural comparison simultaneously

The key insight that makes this pattern work is that we can solve this by:

1. Traversing the parent tree to find potential root matches
2. For each candidate node, checking if the subtree structure matches exactly
3. This is fundamentally different from array substring matching where we only need to check linear containment

Conditions where variations apply:

• If we're looking for a subtree with specific properties (e.g., same sum, same height), this becomes a constrained subtree search
• If we're looking for any occurrence of a pattern (not necessarily exact subtree), it becomes a tree pattern matching problem
• If we're dealing with multiple trees or streams of trees, it becomes a tree matching in streaming scenario

Core insight: The solution requires two levels of recursion - one to traverse the parent tree and find potential matches, another to validate if the structure matches exactly at that point. This is fundamentally about tree isomorphism checking where we're looking for a specific subtree structure within a larger tree structure.

3. Approach Evolution

Interview communication script:

My first instinct is to solve this by checking if one tree is a subtree of another, which seems like a natural recursive problem. But let me think about the brute force approach first - I could traverse every node in the main tree and for each node, check if the subtree starting from that node matches the target subtree. That would be O(n×m) where n is the number of nodes in the main tree and m is the number of nodes in the target subtree. But that's inefficient because we're doing redundant comparisons.

Let me think about how to optimize this. I notice that if I can somehow compare trees efficiently and maintain some invariants, I might be able to reduce redundant work. Actually, let me think more carefully - the key insight is that I can use a two-step approach: first, I need to identify if any node in the main tree has the same structure and values as the target subtree. This means I need to traverse the main tree and for each node, check if that node's subtree matches the target.

The optimization comes from recognizing that I can do this in one pass by checking if two trees are identical, then recursively applying that check to each node. The key invariant I need to maintain is that for any node in the main tree, if its subtree matches the target subtree, then the structure and values must be identical.

My approach will be:

1. First check if two trees are identical (helper function)
2. Then recursively check every node in the main tree to see if its subtree matches the target
3. The base case is when either tree is null - we handle that carefully

This reduces to O(n×m) worst case but in practice, many comparisons will be short-circuited.

Brute-force approach and why it is not ideal:

The brute force approach would be to traverse every node in the main tree and for each node, check if the subtree rooted at that node matches the target subtree. For each such comparison, we'd need to check if two trees are identical, which takes O(m) time where m is the size of the target subtree.

This approach has O(n×m) time complexity, where n is the number of nodes in the main tree. The problem with this approach is that we're doing redundant work - many subtree comparisons will involve comparing nodes that are clearly not matching, and we're not leveraging any structural properties to prune the search space.

Improved approach and the key optimization:

The improved approach is to use a two-step recursive process:

1. Create a helper function that checks if two trees are identical
2. For each node in the main tree, check if that node's subtree matches the target subtree using the helper function

The key optimization is that we can short-circuit early - if at any point the current node's value doesn't match the target subtree root, we can immediately return false without doing further comparisons. Also, once we find a matching subtree, we can return early from the main search.

Final approach with step-by-step reasoning:

1. Define a helper function isSameTree(TreeNode s, TreeNode t) that checks if two trees are identical
2. In the main function isSubtree(TreeNode s, TreeNode t):
   • If main tree is null, return false (no subtree possible)
   • If target tree is null, return true (empty tree is subtree of any tree)
   • Check if current node matches target tree using helper function
   • If not matching, recursively check left and right subtrees
3. The key invariant is that we only proceed to check subtrees when the current node value matches the target root value, which reduces unnecessary comparisons

Important invariants that must hold:

• If the target subtree is null, we should return true (empty tree is a subtree of any tree)
• If the main tree is null but target isn't, return false (can't find subtree in empty tree)
• When comparing trees, we must check both structure and values match exactly
• We can only consider a subtree matching if the root values are identical, otherwise we continue searching in left/right subtrees

4. Data Structure Choice

For the Subtree of Another Tree problem, the primary data structure is a TreeNode class to represent the binary tree nodes.

Primary Data Structures Used

1. TreeNode:

   • Represents each node in the binary tree with val, left, and right fields
   • Essential for traversing and comparing tree structures
   • Time complexity: O(1) for node operations, Space complexity: O(1) per node

2. Recursive call stack:

   • Used implicitly during tree traversal and comparison operations
   • Space complexity: O(h) where h is the height of the tree (for recursion depth)
   • In worst case (skewed tree), this becomes O(n) where n is the number of nodes

Why Each Data Structure Is Needed

The TreeNode structure is fundamental because:

• It enables us to navigate and compare tree structures recursively
• It provides the necessary node information (value and children) for subtree matching
• It allows us to traverse both trees in a natural, intuitive way

The recursive call stack is needed because:

• Tree comparison naturally lends itself to recursive algorithms
• It maintains the state of current nodes being compared in both trees
• It enables backtracking when subtree matching fails at a particular node

Time and Space Impact

• Time Complexity: O(n × m) where n is the number of nodes in the main tree and m is the number of nodes in the subtree
• Space Complexity: O(h₁ + h₂) where h₁ and h₂ are the heights of the two trees, due to recursive call stacks

Helper Structures

No additional helper structures are required for the core algorithm. The solution uses only the existing TreeNode structure and leverages recursion for traversal, which is clean and efficient.

The chosen approach avoids additional data structures like hash maps or queues that would complicate the solution unnecessarily for this specific problem pattern.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example:
Tree s = [3,4,5,1,2]
Tree t = [4,1,2]

Step 1: Start with root of s (node 3).
We check if the subtree rooted at node 3 matches tree t.
Since 3 ≠ 4, we continue to explore.

Step 2: Move to left child of s (node 4).
Check if subtree rooted at node 4 matches tree t.
Node 4 has value 4, which matches the root of t.
Now we recursively check if the left subtree of node 4 (value 1) matches left subtree of t (value 1).
And if the right subtree of node 4 (value 2) matches right subtree of t (value 2).
Both match, so we return true.

Step 3: If no match found in the traversal, continue checking other nodes.
We would continue with node 5 and its subtrees.

Key Points:

• The algorithm uses a recursive helper function to check if two trees are identical.
• For each node in s, we attempt to match it with t as the root of a subtree.
• The recursion ensures that we explore all possible matching positions in s.
• We handle null nodes correctly by checking for null before accessing properties.

Edge Case Handling: If tree t is null, we return true (empty tree is a subtree of any tree). If tree s is null but t is not, we return false. If both are null, we return true.

The algorithm terminates correctly because:

1. We explore every node in s as a potential root of matching subtree.
2. For each candidate, we do an exact match check using the helper function.
3. The recursion naturally handles all possible subtree configurations.
4. Base cases (null nodes) ensure proper termination without infinite loops.

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-tier approach:

1. Main method isSubtree recursively traverses the main tree and checks if any subtree matches the target
2. Helper method isSameTree performs exact tree comparison between two nodes

The solution handles the recursive structure cleanly by checking if the current root matches, then recursively searching in left/right subtrees. The helper method ensures we're comparing identical tree structures rather than just matching values.

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 and for each node, it calls isSameTree which traverses the entire subtree. In the worst case, we might have to check every node in the main tree against the target subtree. Each isSameTree call takes O(M) time in the worst case, where M is the size of the subtree. Therefore, the overall time complexity becomes O(N × M).

Space Complexity: O(max(H₁, H₂)) where H₁ is the height of the main tree and H₂ is the height of the subtree.

The space complexity is dominated by the recursion stack depth. In the worst case, when both trees are skewed (like a linked list), the recursion depth can reach O(N) for the main tree and O(M) for the subtree. Therefore, the space complexity is O(max(H₁, H₂)).

Why these bounds are correct:

• The time complexity is tight because in the worst case, we must compare every node of the main tree with the target subtree
• The space complexity reflects the maximum recursion depth, which occurs when trees are unbalanced
• These bounds represent the optimal solution for this problem as we must examine each node at least once to determine subtree matching

Optimality: This solution is optimal for the general case where we cannot make assumptions about tree structure. The algorithm achieves the best possible time complexity for this problem since we must potentially inspect every node in both trees to verify subtree matching. Any improvement would require additional constraints on the tree structure (e.g., balanced trees, sorted properties) that aren't provided in the problem statement.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty trees: If either root or subRoot is null, the result should be handled properly. Specifically, if subRoot is null, we typically return true (an empty tree is a subtree of any tree), but if root is null and subRoot is not null, we return false.
• Single node trees: Edge case where one or both trees have only one node. Must verify that node values match exactly.

Duplicate Values and Repeated States

• Duplicate node values: The algorithm must compare entire subtree structures, not just root values. A tree with duplicate values can still be a subtree of another tree if structure matches.
• Identical trees: When root and subRoot are identical, the function should return true.

Boundary Conditions

• Deeply nested trees: Large depth differences between root and subRoot can cause stack overflow in recursive solutions.
• Unbalanced trees: Performance degrades with very unbalanced structures, though time complexity remains the same.

Common Implementation Mistakes

• Incorrect null checks: Not checking for null before accessing node properties, leading to NullPointerException.
• Comparing only root values: A naive approach might compare just the root node values, missing structural differences.
• Inefficient tree traversal: Using nested loops instead of proper recursive or iterative traversal, resulting in O(n²) complexity.
• Not handling all node types: Missing to consider that a subtree can be any portion of the tree, not just the left or right child.

// Example edge case handling:
if (root == null && subRoot == null) return true;
if (root == null || subRoot == null) return false;

The solution must explicitly handle these boundary conditions to ensure correctness across all inputs.

9. Alternative Approaches

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

1. String-based serialization approach: Serialize both trees into strings using pre-order traversal with null markers (e.g., "1,2,null,null,3,null,null" for a tree with root 1, left child 2, right child 3). Then check if the serialized subtree string is a substring of the main tree's serialized string. This approach works but has issues with duplicate values and requires additional space for serialization.

2. Hash-based approach: Compute rolling hash values for subtrees of the main tree and compare against the target subtree's hash. This can be faster in practice but introduces collision risks and requires careful handling of hash functions.

3. Brute force tree matching: For each node in the main tree, check if the subtree rooted at that node matches the target subtree by comparing all nodes recursively. This is O(n×m) where n and m are the sizes of the trees, which is worse than our optimized solution but simpler to implement.

4. KMP-based pattern matching: Convert both trees into sequences and use KMP algorithm for pattern matching. This is theoretically interesting but adds unnecessary complexity for this specific problem.

The chosen solution using recursive tree matching with early termination is preferred because it's:

• More intuitive and readable
• Has optimal time complexity O(n×m) in worst case but often better in practice due to early termination
• Uses minimal additional space (just recursion stack)
• Handles edge cases naturally without special serialization logic

The string-based approach has the advantage of being able to use existing substring search algorithms but suffers from the complexity of handling tree serialization and potential value collisions. The hash-based approach may have better average performance but introduces the risk of hash collisions that need to be handled carefully.

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 trees
// Input: root = [1], subRoot = [1]
// Expected: true
TreeNode root5 = new TreeNode(1);
TreeNode subRoot5 = new TreeNode(1);

The test cases cover:

• Basic matching subtree scenario
• Non-matching subtree case with extra nodes
• Edge case of empty subtree (null)
• Identical trees case
• Minimal single-node trees

Each test case uses a clean tree construction pattern with explicit node creation to ensure clarity and test the specific scenarios that could break a naive implementation. The boundary case of empty subtree is particularly important since it's often overlooked in initial implementations.

11. Final Summary

The core idea is to efficiently determine if one binary tree (subtree) exists as a subtree within another binary tree by leveraging a two-step approach: first, traversing the main tree to find potential root matches, then validating whether the subtree structure matches at each candidate position. This solution works by combining tree traversal with structural validation, making it both intuitive and efficient.

The key insight is that while a brute force approach of checking every node as a potential root would work, it's inefficient. By carefully structuring the validation logic to handle null cases properly and using early termination when mismatches are detected, we achieve optimal performance. The solution's efficiency comes from avoiding redundant comparisons and ensuring that each structural check is meaningful.

This approach is optimal for the problem constraints, with O(m × n) time complexity where m and n are the sizes of the main and subtree respectively, and O(h) space complexity where h is the height of the main tree due to recursion stack depth. The solution handles all edge cases gracefully and provides clean, readable code that's ready for production use.