Problem Description

You are given two binary trees with roots called root and subRoot. Your task is to determine if subRoot appears as a subtree anywhere within root.

A subtree is defined as a tree that consists of a node and all of its descendants. For a tree to be considered a subtree of another, it must have:

• The exact same structure
• The exact same node values at corresponding positions

The main tree root is also considered a subtree of itself.

Return true if subRoot exists as a subtree within root, and false otherwise.

For example, if you have a tree root with nodes arranged in a certain pattern, and another smaller tree subRoot, you need to check if you can find a node in root where starting from that node, the structure and values exactly match subRoot.

The solution uses a depth-first search approach with two key components:

1. A helper function same(p, q) that checks if two trees are identical by comparing their root values and recursively checking their left and right subtrees
2. The main function that traverses through each node in root and checks if the subtree starting from that node matches subRoot

The algorithm works by:

• First checking if the current node's subtree matches subRoot completely
• If not, recursively checking if subRoot exists in either the left or right subtree of the current node
• Returning true if any match is found, false if no match exists after checking all possibilities

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While not explicitly a graph problem, a binary tree is a special type of graph (specifically, a connected acyclic graph). Binary trees have nodes connected by edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly deals with binary trees. We have two binary tree structures (root and subRoot) and need to check if one appears as a subtree within the other.

DFS

• Yes: Since we're working with trees and need to explore each node to check if it could be the starting point of a matching subtree, DFS is the appropriate approach.

Conclusion: The flowchart leads us directly to using DFS (Depth-First Search) for this problem. This makes sense because:

1. We need to traverse through each node in the main tree
2. At each node, we need to check if the subtree rooted at that node matches subRoot
3. The checking itself requires comparing entire tree structures recursively
4. DFS allows us to systematically explore each path in the tree and perform the necessary comparisons

The DFS pattern manifests in two ways in the solution:

• The main traversal through root to find potential starting points
• The recursive comparison of tree structures using the same() helper function

Intuition

When we need to check if one tree is a subtree of another, the natural approach is to think about what makes two trees identical. If we can identify when two trees are the same, then we can check every possible starting position in the main tree to see if any of them match our target subtree.

Think of it like searching for a specific pattern in a larger structure. We need to:

1. Know how to verify if two patterns match exactly
2. Check every possible position where the pattern could start

For the first part, two trees are identical when:

• Their root values are the same
• Their left subtrees are identical
• Their right subtrees are identical

This naturally leads to a recursive comparison function that checks these three conditions.

For the second part, since subRoot could appear anywhere within root, we need to check:

• Could subRoot match starting from the current root node?
• If not, could it be found in the left subtree?
• If not there either, could it be in the right subtree?

This is where DFS comes in naturally - we're systematically exploring each node as a potential starting point for our match. At each node we visit, we ask "Does the subtree starting here match subRoot?" If yes, we're done. If no, we continue searching in the children.

The beauty of this approach is that it breaks down a complex problem into two simpler recursive problems:

1. Checking if two trees are identical (the same function)
2. Searching through all nodes to find where to apply that check (the main isSubtree function)

Both naturally fit the DFS pattern because trees have a recursive structure - each subtree is itself a tree with the same properties as the whole.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a DFS approach with two key functions working together:

Helper Function: same(p, q)

This function determines if two trees are identical:

• Base case: If either p or q is None, they're only identical if both are None (checked with p is q)
• Recursive case: Trees are identical if:
  • Root values match: p.val == q.val
  • Left subtrees are identical: same(p.left, q.left)
  • Right subtrees are identical: same(p.right, q.right)

All three conditions must be true, so we use the and operator to combine them.

Main Function: isSubtree(root, subRoot)

This function traverses the main tree looking for a matching subtree:

1. Base case: If root is None, return False (an empty tree cannot contain a non-empty subtree)

2. Check current position: Call same(root, subRoot) to check if the tree rooted at the current node matches subRoot

3. Recursive search: If the current position doesn't match, recursively search:

   • Left subtree: self.isSubtree(root.left, subRoot)
   • Right subtree: self.isSubtree(root.right, subRoot)

4. Return result: Use the or operator to return True if any of the three checks succeed

Algorithm Flow

The algorithm works by:

1. Starting at the root of the main tree
2. At each node, checking if the subtree rooted there matches subRoot completely
3. If not, recursively checking both left and right children
4. Propagating True up the call stack as soon as any match is found

Time and Space Complexity

• Time Complexity: 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, we check every node in root (m nodes) and for each check, we might compare all nodes in subRoot (n nodes).

• Space Complexity: O(h) where h is the height of root, due to the recursive call stack. In the worst case (skewed tree), this could be O(m).

The elegance of this solution lies in its simplicity - by separating the "matching" logic from the "searching" logic, we create two clean, recursive functions that each handle one specific responsibility.

Example Walkthrough

Let's walk through a concrete example to see how the solution works.

Consider these two trees:

root:           subRoot:
      3              4
     / \            / \
    4   5          1   2
   / \
  1   2

We want to check if subRoot appears as a subtree within root.

Step 1: Start at root node (3)

• Call same(node_3, subRoot_root_4)
• Compare values: 3 ≠ 4, so these trees aren't identical
• Since they don't match, continue searching

Step 2: Check left subtree of root

• Call isSubtree(node_4, subRoot)
• Now at node 4, call same(node_4, subRoot_root_4)
• Compare values: 4 = 4 ✓
• Recursively check left children: same(node_1, subRoot_node_1)
  • Values match: 1 = 1 ✓
  • Both have no children (null = null) ✓
• Recursively check right children: same(node_2, subRoot_node_2)
  • Values match: 2 = 2 ✓
  • Both have no children (null = null) ✓
• All checks pass! Return true

The algorithm finds that the left subtree of root (starting at node 4) exactly matches subRoot, so it returns true.

Let's trace through what would happen if subRoot was NOT in the tree:

root:           subRoot:
      3              7
     / \            / \
    4   5          1   2
   / \
  1   2

Step 1: Check root (3) - doesn't match subRoot root (7) Step 2: Check left subtree (4) - doesn't match subRoot root (7) Step 3: Recursively check node 4's children:

• Node 1 doesn't match (1 ≠ 7, and node 1 has no children while subRoot has children)
• Node 2 doesn't match (2 ≠ 7, and node 2 has no children while subRoot has children) Step 4: Check right subtree (5) - doesn't match subRoot root (7) Step 5: Node 5 has no children to check

Since no position matched, return false.

The key insight is that at each node, we perform a complete tree comparison using same(). If that fails, we keep searching deeper in the tree using DFS until we either find a match or exhaust all possibilities.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × m)

The algorithm checks if subRoot is a subtree of root by:

1. For each node in the main tree root (which has n nodes), we potentially call the same function
2. The same function compares two trees for equality, which in the worst case needs to traverse all m nodes of subRoot
3. In the worst case, we check every node in root as a potential match, and for each check, we traverse up to m nodes in subRoot
4. Therefore, the time complexity is O(n × m)

Space Complexity: O(n)

The space complexity comes from the recursion stack:

1. The isSubtree function recursively traverses the main tree root, which can go as deep as the height of the tree
2. In the worst case (a skewed tree), the height equals n, so the recursion stack for isSubtree uses O(n) space
3. The same function also uses recursion, but its stack depth is bounded by min(height of root subtree, height of subRoot), which is at most O(n)
4. Since these recursive calls don't happen simultaneously (we finish one same call before moving to the next node in isSubtree), the maximum stack depth is O(n)
5. Therefore, the space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Subtree with Substructure

A critical pitfall is misunderstanding what constitutes a valid subtree. A subtree must include all descendants of a node, not just a partial match.

Incorrect Understanding:

    root:        subRoot:
       1            1
      / \            \
     1   3            3
      \
       3

Many think subRoot matches the left portion of root, but it doesn't!
The left "1" in root has a child "3", while subRoot's "1" has no left child.

Correct Understanding: A subtree match requires the entire structure from a node downward to be identical, including where nodes are absent (None values matter!).

2. Incorrect Base Case Handling

Pitfall Code:

def is_same_tree(tree1, tree2):
    if not tree1 and not tree2:
        return True
    if not tree1 or not tree2:  # Redundant after first check
        return False
    # ... rest of logic

Better Approach:

def is_same_tree(tree1, tree2):
    if tree1 is None or tree2 is None:
        return tree1 is tree2  # Elegant one-liner handling all None cases

3. Missing Edge Case: Empty SubRoot

The problem statement typically assumes subRoot is not None, but if it could be:

Problematic Scenario:

# If subRoot is None, should this return True or False?
isSubtree(root, None)  

Solution: Add explicit handling:

def isSubtree(self, root, subRoot):
    if subRoot is None:
        return True  # Empty tree is subtree of any tree
    if root is None:
        return False  # Non-empty subRoot can't be in empty root
    # ... rest of logic

4. Performance Degradation with Repeated Values

When the tree has many nodes with the same value as subRoot's root, the algorithm repeatedly performs full tree comparisons:

Worst Case Example:

    root:           subRoot:
       1                1
      / \              /
     1   1            2
    / \ / \
   1  1 1  1

Every node with value "1" triggers a full comparison with subRoot.

Optimization Strategy: Consider using tree serialization or hashing for large trees with many repeated values:

def isSubtree(self, root, subRoot):
    def serialize(node):
        if not node:
            return "#"
        return f",{node.val},{serialize(node.left)},{serialize(node.right)}"
  
    tree_str = serialize(root)
    subtree_str = serialize(subRoot)
    return subtree_str in tree_str

5. Stack Overflow with Deep Trees

For extremely deep trees, the recursive approach can cause stack overflow.

Solution for Production Code: Implement an iterative version using explicit stack:

def isSubtree(self, root, subRoot):
    def is_same_tree_iterative(p, q):
        stack = [(p, q)]
        while stack:
            node1, node2 = stack.pop()
            if not node1 and not node2:
                continue
            if not node1 or not node2 or node1.val != node2.val:
                return False
            stack.append((node1.left, node2.left))
            stack.append((node1.right, node2.right))
        return True
  
    if not root:
        return False
  
    stack = [root]
    while stack:
        node = stack.pop()
        if is_same_tree_iterative(node, subRoot):
            return True
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return False

Key Takeaway

The most common mistake is assuming partial structural matches count as subtrees. Remember: a subtree must be an exact copy of a node and all its descendants - no additions, no omissions, no reorderings.