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.

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.