Solving Subtree of Another Tree: Comparing Tree Structures

The "Subtree of Another Tree" problem involves determining whether one binary tree is a subtree of another binary tree.

Problem Statement

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of tree s.

Example

Consider two binary trees s and t:

Tree t is a subtree of tree s.

Solution Approach - Recursive Comparison

Breaking Down the Solution

• Recursive Tree Comparison: The function isSameTree checks if two trees are identical.
• Subtree Check: The function isSubtree checks if t is the same as s, or if t is a subtree of either the left or right subtree of s.
• Base Cases: Handle null trees appropriately in both functions.

Conclusion

The Subtree of Another Tree problem is an interesting application of binary tree algorithms, requiring a combination of tree traversal and recursive comparison to determine subtree relationships.

Rust Solution

A recursive TreeNode can't hold itself inline, so each child is an Option<Box<TreeNode>> — the Box supplies the heap indirection a sized struct needs and the Option encodes "no child" without a null pointer. is_same compares two nodes with a single match (p, q) over the tuple: (None, None) => true, (Some(a), Some(b)) recurses on a.val == b.val plus both children, and the _ => false arm collapses every mismatched-shape case into one line. Every function takes &Option<Box<TreeNode>> by reference so the recursion borrows the tree instead of moving it, and the empty base case reads as t.is_none().

Go Solution

Go models the tree with plain *TreeNode pointers and nil rather than an option type, so the base cases are direct p == nil / q == nil checks instead of pattern matches. The shared parameter grouping func isSame(p, q *TreeNode) lets both nodes share one type annotation, and isSubtree returns t == nil on its empty branch. The three sequential if guards — both nil, either nil, then a Val mismatch — unfold what Rust folds into one match, favouring Go's flat, explicit style over conciseness.