Solving Same Tree in Go: Step-by-Step Guide

Introduction to the Same Tree Problem

The "Same Tree" problem is one of the foundational challenges you will encounter when learning tree data structures and recursion. It appears frequently in coding interviews and on platforms like LeetCode (Problem 100). The task is simple to describe: given the roots of two binary trees, determine whether they are structurally identical and have the same node values at every corresponding position.

While the problem statement is short, mastering it teaches you several critical concepts: recursive tree traversal, base case design, short-circuit evaluation, and how to reason about edge cases such as nil nodes. In this tutorial, we will walk through the problem in Go from first principles, build a working solution, and then explore iterative alternatives and best practices.

What Is the Same Tree Problem?

Two binary trees are considered the "same" if they are structurally identical and every corresponding node contains the same value. This means:

• Both trees must have the same shape — every branch and leaf must align.
• Every matching node pair must hold equal values.
• If one tree has a node where the other does not, the trees are not the same.

Before writing any code, we need a representation of a binary tree node. In Go, this is typically defined as a struct with a value and pointers to left and right children:

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

This struct is the building block for every solution we will discuss. The Val field stores the integer payload, while Left and Right are pointers that may be nil when a child is absent.

Why the Same Tree Problem Matters

You might wonder why such a seemingly simple problem deserves so much attention. The answer lies in what it teaches and where it is applied:

• Recursion fundamentals: Trees are naturally recursive structures, and this problem is one of the cleanest examples of recursive decomposition.
• Base case thinking: Handling nil nodes correctly is a skill that transfers to almost every tree problem.
• Validation and testing: In real systems, comparing two tree structures is useful for verifying serialized data, detecting mutations, or diffing configurations.
• Interview readiness: It is a warm-up problem that interviewers use to gauge your comfort with pointers and recursion before moving to harder questions.

Once you can confidently solve Same Tree, problems like Subtree of Another Tree, Symmetric Tree, and Merge Two Binary Trees become much easier because they reuse the same patterns.

Step-by-Step Recursive Solution

Designing the Algorithm

The recursive approach mirrors the recursive nature of trees. At each step, we compare the current pair of nodes. There are three possible scenarios:

• Both nodes are nil — they match, so return true.
• Only one node is nil — the structures differ, so return false.
• Both nodes are non-nil — their values must be equal, and both their left and right subtrees must also be the same.

This translates directly into a recursive function with a clear base case and a recursive case. Let us write it out:

func isSameTree(p *TreeNode, q *TreeNode) bool {
    // Base case: both nodes are nil
    if p == nil && q == nil {
        return true
    }
    // One node is nil, the other is not
    if p == nil || q == nil {
        return false
    }
    // Both non-nil: compare values and recurse on children
    if p.Val != q.Val {
        return false
    }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

Notice how the logic reads almost like the English description. The && operator short-circuits: if the left subtrees differ, the right subtrees are never examined. This is both an efficiency win and a clarity win.

Tracing an Example

Consider two small trees. Tree p has root value 1, a left child with value 2, and a right child with value 3. Tree q is constructed identically. Let us trace the execution:

func main() {
    p := &TreeNode{Val: 1,
        Left:  &TreeNode{Val: 2},
        Right: &TreeNode{Val: 3},
    }
    q := &TreeNode{Val: 1,
        Left:  &TreeNode{Val: 2},
        Right: &TreeNode{Val: 3},
    }
    fmt.Println(isSameTree(p, q)) // Output: true
}

The first call compares roots 1 and 1 — equal. It then recurses on the left children, which are both 2, returning true. Finally it recurses on the right children, both 3, also returning true. The conjunction of two true values yields true.

If we changed q's right child to value 4, the right subtree comparison would return false immediately, and the entire function would return false without exploring further.

Complexity Analysis

Understanding the cost of your solution is essential. For the recursive approach:

• Time complexity: O(min(n, m)), where n and m are the number of nodes in the two trees. In the worst case, we visit every node in the smaller tree before discovering a mismatch or confirming equality.
• Space complexity: O(min(h1, h2)), where h1 and h2 are the heights of the trees. This accounts for the recursion stack. For a balanced tree, this is O(log n); for a degenerate (linked-list-like) tree, it is O(n).

These bounds are optimal for this problem — you cannot determine equality without inspecting every relevant node, and the recursion depth is dictated by the tree shape.

Iterative Solution Using a Queue

Recursion is elegant, but some environments limit stack depth, and some teams prefer explicit control over traversal. An iterative solution using a queue (breadth-first) or a stack (depth-first) achieves the same result without recursion.

Here is a breadth-first version using a slice as a queue:

func isSameTreeIterative(p *TreeNode, q *TreeNode) bool {
    queue := [][]*TreeNode{{p, q}}

    for len(queue) > 0 {
        pair := queue[0]
        queue = queue[1:]
        node1, node2 := pair[0], pair[1]

        if node1 == nil && node2 == nil {
            continue
        }
        if node1 == nil || node2 == nil {
            return false
        }
        if node1.Val != node2.Val {
            return false
        }

        queue = append(queue, []*TreeNode{node1.Left, node2.Left})
        queue = append(queue, []*TreeNode{node1.Right, node2.Right})
    }
    return true
}

The logic mirrors the recursive version. Instead of the call stack tracking node pairs, we explicitly enqueue pairs of children. When both nodes are nil, we simply continue to the next pair. When only one is nil or values differ, we return false. If the queue empties without finding a mismatch, the trees are identical.

The time and space complexity remain the same as the recursive version, though the space is now heap-allocated queue storage rather than call-stack frames. This can be preferable for very deep trees that would otherwise risk a stack overflow.

Testing Your Solution

A correct implementation deserves thorough testing. Go's built-in testing package makes this straightforward. Here is a test file covering the main cases:

package main

import "testing"

func TestIsSameTree(t *testing.T) {
    tests := []struct {
        name     string
        p        *TreeNode
        q        *TreeNode
        expected bool
    }{
        {
            name:     "both nil",
            p:        nil,
            q:        nil,
            expected: true,
        },
        {
            name:     "one nil",
            p:        &TreeNode{Val: 1},
            q:        nil,
            expected: false,
        },
        {
            name: "identical trees",
            p: &TreeNode{Val: 1,
                Left:  &TreeNode{Val: 2},
                Right: &TreeNode{Val: 3}},
            q: &TreeNode{Val: 1,
                Left:  &TreeNode{Val: 2},
                Right: &TreeNode{Val: 3}},
            expected: true,
        },
        {
            name: "different values",
            p: &TreeNode{Val: 1,
                Left: &TreeNode{Val: 2}},
            q: &TreeNode{Val: 1,
                Left: &TreeNode{Val: 3}},
            expected: false,
        },
        {
            name: "different structure",
            p: &TreeNode{Val: 1,
                Left:  &TreeNode{Val: 2},
                Right: &TreeNode{Val: 3}},
            q: &TreeNode{Val: 1,
                Right: &TreeNode{Val: 3}},
            expected: false,
        },
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            if got := isSameTree(tt.p, tt.q); got != tt.expected {
                t.Errorf("isSameTree() = %v, want %v", got, tt.expected)
            }
        })
    }
}

Run the tests with go test -v. These cases cover the four critical scenarios: both empty, one empty, full equality, value mismatch, and structural mismatch. Adding a few more — such as deeply nested asymmetric trees — will further strengthen your confidence.

Best Practices

Handle Nil Cases First

The most common source of bugs in tree code is forgetting to check for nil before accessing fields. Always structure your function so that nil checks come before any field access. The pattern if p == nil && q == nil followed by if p == nil || q == nil is idiomatic and safe.

Leverage Short-Circuit Evaluation

Using && between recursive calls ensures that the function exits early when a mismatch is found. This is not just a micro-optimization — it can dramatically reduce work on large trees that differ near the root.

Choose the Right Traversal Style

Recursion is usually the right default for tree problems because it is concise and mirrors the structure. However, if you are working with trees that may be very deep (for example, a degenerate tree built from sorted input), prefer the iterative approach to avoid stack overflow.

Write Helper Builders for Tests

Constructing trees by hand with nested struct literals becomes tedious for larger tests. Consider a helper that builds a tree from a slice representation, where nil entries denote missing nodes:

func buildTree(values []int) *TreeNode {
    if len(values) == 0 || values[0] == -1 {
        return nil
    }
    root := &TreeNode{Val: values[0]}
    queue := []*TreeNode{root}
    i := 1
    for len(queue) > 0 && i < len(values) {
        node := queue[0]
        queue = queue[1:]
        if i < len(values) && values[i] != -1 {
            node.Left = &TreeNode{Val: values[i]}
            queue = append(queue, node.Left)
        }
        i++
        if i < len(values) && values[i] != -1 {
            node.Right = &TreeNode{Val: values[i]}
            queue = append(queue, node.Right)
        }
        i++
    }
    return root
}

Using -1 as a sentinel for nil keeps the input compact and readable. This kind of utility pays off across every tree problem you tackle.

Keep Functions Pure

The isSameTree function does not mutate its inputs. Preserve this property. Side-effect-free functions are easier to test, reason about, and reuse in concurrent contexts.

Common Pitfalls to Avoid

• Forgetting the both-nil case: If you only check p == nil || q == nil, you will incorrectly return false when both are nil.
• Comparing pointers instead of values: Writing p == q compares memory addresses, not tree contents. Always compare Val fields and recurse on children.
• Ignoring tree shape: Two trees with the same values in different arrangements are not the same. Always recurse on both left and right children in lockstep.
• Mixing up child order: Comparing p.Left with q.Right is a subtle bug. Double-check that left compares to left and right to right.

Conclusion

The Same Tree problem is a compact exercise that reinforces the most important habits in tree programming: careful nil handling, recursive decomposition, short-circuit evaluation, and thorough testing. By implementing both the recursive and iterative versions in Go, you gain not only a solution to a specific interview question but also a reusable mental model for every tree comparison task that follows. Start with the recursive approach for its clarity, reach for the iterative version when depth is a concern, and always back your code with tests that cover empty trees, structural mismatches, and value mismatches. With these tools in hand, you are well prepared to tackle the broader family of tree problems with confidence.