Solving Same Tree: Comparing Binary Tree Structures

The "Same Tree" problem is about determining whether two binary trees are structurally identical and have the same node values.

Problem Statement

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example

Consider two binary trees:

These two trees are the same.

Solution Approach - Recursive Comparison

Breaking Down the Solution

• Recursive Strategy: The solution uses recursion to compare corresponding nodes of the two trees.
• Base Cases: Check for null nodes. If both are null, they are the same; if only one is null, they are not the same.
• Value Comparison: Compare the value of the current nodes. If they are different, the trees are not the same.
• Recursive Calls: Recursively compare left and right children of the current nodes.

Conclusion

The Same Tree problem is a fundamental exercise in understanding binary tree structure and recursion, highlighting the importance of simultaneous traversal in tree comparison.

Rust Solution

Rust's Option<Box<TreeNode>> carries both the null case and the recursion in one type: Box heap-allocates each child so the struct has a known size, while Option stands in for the TS null. Because is_same_tree takes &Option<Box<TreeNode>> by shared reference and recurses on &a.left/&a.right, it reads the trees without moving or cloning them. The single match (p, q) on the tuple collapses the TS version's three separate if guards: (None, None) returns true, (Some(a), Some(b)) checks a.val == b.val and recurses, and the _ arm absorbs every remaining one-side-null mismatch.

Go Solution

Go models each optional child as a *TreeNode pointer compared against nil, mirroring the TS null checks almost line for line — p == nil && q == nil, then the one-sided p == nil || q == nil, then p.Val != q.Val. The shared-type parameter list func isSameTree(p, q *TreeNode) lets both pointers ride the single *TreeNode annotation. In main, the composite literals &TreeNode{Val: 2} omit Left and Right, so those fields fall back to the struct's zero value, which for a pointer is nil — no explicit null needed.