Subtree of Another Tree: LeetCode 572 Walkthrough

Some LeetCode problems test whether you can solve a single task. Others test whether you can combine two ideas into one solution. Subtree of Another Tree (LeetCode 572) falls squarely in the second category — it asks you to compose the Same Tree check with a full DFS traversal, and the result is more elegant than either piece alone.

If you have already solved Same Tree (#100), you are halfway to solving this problem. The key insight is that checking whether one tree is a subtree of another is really just asking: does any node in the main tree serve as the root of a tree identical to the target? That single reframe turns a seemingly complex problem into a clean recursive composition.

This walkthrough covers the approach, implementation, and edge cases for subtree of another tree leetcode so you can recognize and apply this composition pattern in interviews.

Given two binary trees s and t, determine whether t is a subtree of s. A subtree of s is a tree consisting of a node in s and all of its descendants. The subtree must include every descendant — you cannot prune leaves or skip children.

For example, if s = [3,4,5,1,2] and t = [4,1,2], the answer is true because the left subtree rooted at node 4 in s is structurally identical to t with matching values at every position. However, if t = [4,1,2,null,null,0], the answer is false because t has an extra node that does not appear in the corresponding subtree of s.

This distinction matters: a subtree must match exactly, not approximately. Every node, every null child, every value must line up. That is precisely what Same Tree checks — and why it becomes our building block.

The strategy is straightforward once you see it. Walk through every node in tree s using DFS. At each node, ask: is the subtree rooted here identical to t? If yes, return true. If you exhaust all nodes without finding a match, return false.

This decomposes into two functions. The first is isSameTree(p, q), which recursively checks whether two trees are identical by comparing values and structure at each node. The second is isSubtree(s, t), which traverses s and calls isSameTree(node, t) at every node it visits.

The time complexity is O(m * n), where m is the number of nodes in s and n is the number of nodes in t. In the worst case, you call isSameTree (an O(n) operation) for each of the m nodes in s. The space complexity is O(h) where h is the height of tree s, due to the recursion stack.

The isSameTree helper is the foundation. It takes two nodes and returns true only if both are null (base case), or both are non-null with equal values and recursively identical left and right children. If one is null and the other is not, or the values differ, it returns false immediately.

The isSubtree function is equally concise. If s is null, return false — an empty tree cannot contain a non-empty subtree. Otherwise, check if isSameTree(s, t) is true for the current node. If not, recurse on s.left and s.right, returning true if either subtree contains t.

In Python, the complete solution is roughly ten lines of code. In JavaScript or Java, it is similarly compact. The beauty of this subtree of another tree leetcode solution is that each function has a single responsibility, and composing them yields the full answer.

Here is the logic in pseudocode: isSubtree(s, t) returns isSameTree(s, t) OR isSubtree(s.left, t) OR isSubtree(s.right, t). That single line captures the entire algorithm — check the current node, then recurse left and right.

Let us trace through the example where s = [3,4,5,1,2] and t = [4,1,2]. Tree s has root 3, left child 4, right child 5, and node 4 has children 1 and 2. Tree t has root 4 with children 1 and 2.

We start at root 3 of s. Call isSameTree(3-node, 4-node): values 3 and 4 differ, so this returns false. We then recurse left to node 4 in s.

At node 4 in s, call isSameTree(4-node, t-root-4): values match (4 == 4). Recurse to children — left children are both 1 (match), right children are both 2 (match). Both subtrees bottom out at null simultaneously. isSameTree returns true, so isSubtree returns true.

We never need to visit node 5 in s because we already found a match. The DFS short-circuits as soon as any path returns true, which is a useful optimization in practice even though it does not change the worst-case complexity.

Edge cases for subtree matching are worth memorizing because interviewers frequently probe them. If t is null, the answer is true — a null tree is a subtree of any tree (including a null tree). If s is null but t is not, the answer is false — a non-empty tree cannot be a subtree of nothing.

When s and t are identical trees, the answer is true — the entire tree is trivially a subtree of itself. When t is a single node, you are essentially searching for that value in s, which reduces to a simple tree search.

A tricky case arises when values match partially but structure diverges. For example, s = [1,2,3] and t = [1,2] returns false because t only has a left child while s has both children. The isSameTree check catches this — it verifies structure as well as values, so partial matches are correctly rejected.

Subtree of Another Tree is one of the cleanest examples of algorithm composition in the LeetCode canon. You take a solved problem (Same Tree) and use it as a subroutine inside a larger traversal. This pattern appears again and again in tree problems — checking path sums, finding duplicate subtrees, and validating BST properties all follow the same compose-and-traverse structure.

The brute force O(m * n) solution is the expected approach in interviews. There exists an O(m + n) solution using tree serialization combined with KMP string matching, but it trades clarity for complexity and is rarely expected. Focus on explaining the composition clearly and handling edge cases confidently.

If you found this problem approachable, try Symmetric Tree (#101), Count Univalue Subtrees (#250), and Find Duplicate Subtrees (#652) — they all exercise the same muscle of composing recursive tree checks. Review these patterns with YeetCode flashcards to build the recall speed you need for timed interviews.