How do you solve Subtree of Another Tree on LeetCode?

Subtree of Another Tree (LeetCode #572) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Understanding tree traversal is crucial for solving tree-related problems.

What is the brute force solution for Subtree of Another Tree?

The brute force approach for Subtree of Another Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every subtree of the main tree to see if it matches the smaller tree. This is simple to understand but can be inefficient for larger trees. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Subtree of Another Tree?

Always clarify the definition of a subtree before starting. Consider edge cases and how they might affect your solution. Practice writing helper functions for clarity and modularity.

What are common mistakes when solving Subtree of Another Tree?

Not handling edge cases, like when one tree is null. Confusing subtree checks with tree equality checks.

#572

Subtree of Another Tree

Easy

TreeDepth-First SearchString MatchingBinary TreeHash FunctionDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach uses a single traversal of the main tree while checking for subtree matches. This reduces the number of checks significantly compared to the brute force method.

⚙️

Algorithm

4 steps

1Step 1: Traverse the main tree using a depth-first search (DFS).
2Step 2: For each node, check if it matches the root of subRoot.
3Step 3: If it matches, check if the entire subtree matches using a helper function.
4Step 4: If a match is found, return true; otherwise, continue searching.

solution.py21 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
10        if not root:
11            return False
12        if self.isSameTree(root, subRoot):
13            return True
14        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
15
16    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
17        if not p and not q:
18            return True
19        if not p or not q:
20            return False
21        return (p.val == q.val) and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

ℹ

Complexity note: The time complexity is O(n) because we traverse each node in the main tree once. The space complexity is O(h) due to the recursive call stack, where h is the height of the tree.

1Understanding tree traversal is crucial for solving tree-related problems.
2Recognizing when to use helper functions for subtree comparisons can simplify code.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.