Introduction to the Subtree Problem
The "Subtree of Another Tree" problem is a classic algorithmic challenge frequently encountered in coding interviews and real-world tree manipulation scenarios. Given two binary trees — a root tree and a subRoot tree — the task is to determine whether the subRoot tree is an exact structural and value match of any subtree within the root tree. This means every node, edge, and value in subRoot must appear identically somewhere inside root, with no extra children dangling off the matching portion.
This problem matters because it tests two fundamental skills simultaneously: tree traversal and deep equality checking. It appears in contexts like document comparison, DOM diffing, syntax tree analysis, and hierarchical data validation. Mastering it sharpens your ability to reason recursively about nested structures, a skill that transfers directly to more complex tree and graph problems.
Understanding the Problem Statement
Before writing any code, let's clarify exactly what qualifies as a subtree. A subtree of a binary tree is a node in that tree plus all of its descendants. The entire tree is also considered a subtree of itself. Crucially, the match must be complete — if subRoot has no left child at a particular node, then the corresponding node in root must also have no left child.
Consider this example:
Root tree: SubRoot tree:
3 4
/ \ / \
4 5 1 2
/ \
1 2
Here, the subtree rooted at node 4 in the root tree exactly matches subRoot, so the answer is true. However, if the root tree had an extra child under node 2, the match would fail because subRoot does not contain that child.
Defining the Tree Structure in Go
Go does not have built-in tree types, so we define our own. The standard representation uses a struct with a value and pointers to left and right children:
package main
import "fmt"
// TreeNode represents a node in a binary tree.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
This minimal struct is sufficient. The Val field holds integer data, while Left and Right are pointers that may be nil, indicating the absence of a child. Using pointers allows us to distinguish between "no child" and "a child with a zero value."
Approach One: Recursive Depth-First Search
The most intuitive solution combines two recursive operations. First, we traverse every node in the root tree. At each node, we ask: "Does the tree starting here exactly match subRoot?" If any node answers yes, we return true. This decomposes the problem into a traversal plus a same-tree check.
Implementing the Same-Tree Helper
The helper function checks whether two trees are structurally and value-wise identical. Both must be nil, or both must be non-nil with matching values and matching children:
// isSameTree reports whether two trees are identical.
func isSameTree(p, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
if p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
The order of checks matters. We first handle the case where both are nil, then the case where exactly one is nil, then the value comparison. Only when values match do we recurse into both children. This short-circuits early on mismatches, avoiding unnecessary work.
Implementing the Main Function
With the helper in place, the main function walks the root tree and applies the helper at each node:
// isSubtree reports whether subRoot is a subtree of root.
func isSubtree(root, subRoot *TreeNode) bool {
if root == nil {
return subRoot == nil
}
if isSameTree(root, subRoot) {
return true
}
return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}
If root is nil, the only possible subtree is also nil. Otherwise, we check the current node for a match, and if that fails, we recurse into both children. The logical OR ensures we stop as soon as any branch yields a match.
Putting It Together
Here is a complete runnable example:
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func isSameTree(p, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
if p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
func isSubtree(root, subRoot *TreeNode) bool {
if root == nil {
return subRoot == nil
}
if isSameTree(root, subRoot) {
return true
}
return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}
func main() {
root := &TreeNode{Val: 3,
Left: &TreeNode{Val: 4,
Left: &TreeNode{Val: 1},
Right: &TreeNode{Val: 2},
},
Right: &TreeNode{Val: 5},
}
subRoot := &TreeNode{Val: 4,
Left: &TreeNode{Val: 1},
Right: &TreeNode{Val: 2},
}
fmt.Println("Is subtree?", isSubtree(root, subRoot)) // true
}
Complexity Analysis
Let n be the number of nodes in root and m be the number of nodes in subRoot. In the worst case, we call isSameTree at every node of root, and each call may traverse up to m nodes. This gives a time complexity of O(n * m). The space complexity is O(max(n, m)) due to recursion stack depth, which corresponds to the height of the trees.
This quadratic behavior is acceptable for moderately sized trees but becomes a bottleneck for very large inputs. The next section explores an optimization.
Approach Two: Serialization and String Matching
A more efficient approach serializes both trees into strings and then checks whether the subRoot's serialization appears as a substring of the root's serialization. With a good substring search algorithm like KMP, this reduces time complexity to O(n + m).
The key is to choose a serialization format that preserves structure unambiguously. A pre-order traversal with explicit null markers works well:
import "strings"
// serialize converts a tree into a unique string representation.
func serialize(node *TreeNode) string {
if node == nil {
return "#"
}
return "^" + intToStr(node.Val) + " " +
serialize(node.Left) + " " + serialize(node.Right)
}
// intToStr is a minimal integer-to-string helper.
func intToStr(n int) string {
if n == 0 {
return "0"
}
negative := n < 0
if negative {
n = -n
}
digits := []byte{}
for n > 0 {
digits = append([]byte{byte('0' + n%10)}, digits...)
n /= 10
}
if negative {
digits = append([]byte{'-'}, digits...)
}
return string(digits)
}
// isSubtreeSerialized uses string matching to detect the subtree.
func isSubtreeSerialized(root, subRoot *TreeNode) bool {
rootStr := serialize(root)
subStr := serialize(subRoot)
return strings.Contains(rootStr, subStr)
}
The ^ prefix before each value prevents false matches caused by overlapping digits. For example, without a delimiter, a node with value 12 could falsely match part of a node with value 123. The # marker represents nil and ensures structural differences are captured in the string.
Note that strings.Contains in Go uses a naive algorithm, so the practical complexity remains O(n * m). To achieve true O(n + m), you would implement KMP or use a rolling hash. For most interview and production scenarios, the built-in function is fast enough due to optimized assembly implementations.
Best Practices
- Handle edge cases explicitly: Always account for nil root, nil subRoot, and the case where subRoot is larger than root. These should return predictable results rather than panicking.
- Prefer the recursive approach for clarity: Unless performance profiling shows a bottleneck, the two-function recursive solution is easier to read, test, and maintain.
- Use delimiters in serialization: When choosing the string-matching approach, always include delimiters or markers to prevent numeric collisions and structural ambiguity.
- Write table-driven tests: Cover scenarios like identical trees, subRoot larger than root, single-node trees, deep skewed trees, and trees with duplicate values to ensure correctness.
- Avoid global state: Keep your functions pure and self-contained so they are safe for concurrent use and easy to reason about.
- Consider iterative alternatives for very deep trees: Go's default goroutine stack is generous, but extremely deep recursion can still cause stack overflow. An explicit stack-based traversal avoids this risk.
Testing Your Implementation
Robust testing is essential. Here is a table-driven test suite covering common cases:
package main
import "testing"
func buildTree(vals []interface{}) *TreeNode {
if len(vals) == 0 || vals[0] == nil {
return nil
}
root := &TreeNode{Val: vals[0].(int)}
queue := []*TreeNode{root}
i := 1
for len(queue) > 0 && i < len(vals) {
node := queue[0]
queue = queue[1:]
if i < len(vals) && vals[i] != nil {
node.Left = &TreeNode{Val: vals[i].(int)}
queue = append(queue, node.Left)
}
i++
if i < len(vals) && vals[i] != nil {
node.Right = &TreeNode{Val: vals[i].(int)}
queue = append(queue, node.Right)
}
i++
}
return root
}
func TestIsSubtree(t *testing.T) {
tests := []struct {
name string
root []interface{}
subRoot []interface{}
expected bool
}{
{"basic match", []interface{}{3, 4, 5, 1, 2}, []interface{}{4, 1, 2}, true},
{"no match", []interface{}{3, 4, 5, 1, 2, nil, nil, nil, nil, 0}, []interface{}{4, 1, 2}, false},
{"identical trees", []interface{}{1, 2, 3}, []interface{}{1, 2, 3}, true},
{"single node match", []interface{}{1}, []interface{}{1}, true},
{"empty subRoot", []interface{}{1, 2}, []interface{}{}, true},
{"subRoot larger", []interface{}{1}, []interface{}{1, 2}, false},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
root := buildTree(tt.root)
subRoot := buildTree(tt.subRoot)
result := isSubtree(root, subRoot)
if result != tt.expected {
t.Errorf("expected %v, got %v", tt.expected, result)
}
})
}
}
The buildTree helper constructs trees from level-order slices, where nil represents an absent node. This makes test cases concise and readable while exercising diverse tree shapes.
Conclusion
Solving the Subtree of Another Tree problem in Go elegantly demonstrates the power of recursive thinking applied to hierarchical data. The straightforward two-function approach — combining a traversal with a same-tree check — is clear, correct, and sufficient for most use cases. When performance demands it, the serialization strategy offers a path to linear time by reframing a structural problem as a string matching problem. By understanding both approaches, their trade-offs, and the edge cases that trip up naive implementations, you equip yourself with reusable techniques that extend far beyond this single problem to any domain involving tree comparison, document diffing, or pattern matching in nested structures.