Preface
In most programming languages, checking whether two binary trees store the same sequence of values is a rather complex problem. It typically requires writing a recursive algorithm to traverse both trees and then compare them node by node. In Go, however, we can leverage its powerful concurrency primitives and channel mechanism to write a clean and elegant solution.
Through a classic exercise from the Go Tour, this article demonstrates how to use Go’s concurrency features to solve the binary tree equivalence problem.
Problem Description
Given two binary trees, how do we determine whether they contain the same sequence of values? Note that the trees do not need to have the exact same structure; they only need to produce the same in-order traversal result.
For example, the following two different binary trees both store the sequence 1, 1, 2, 3, 5, 8, 13:
Tree 1 Tree 2
8 5
/ \ / \
3 13 2 8
/ \ / / \
1 5 1 3 13
/
1
A traditional solution requires:
1. Performing an in-order traversal on both trees separately and storing the results in arrays
2. Comparing whether the two arrays are equal
This approach requires extra storage space and the code is rather verbose. Let’s see how Go solves this problem in a more elegant way.
Core Concept: Go Channels
Before starting the implementation, let’s review the key features of Go channels:
– Channels are type-safe queues: chan int represents an integer channel
– Send and receive operations: ch <- value sends a value, value := <-ch receives a value
– Blocking behavior: send and receive operations block until the other party is ready
– Closable: use close(ch) to close a channel; the receiver can detect if the channel is closed using value, ok := <-ch
– Works with goroutines: channels are the primary way for goroutines to communicate
Implementation Steps
Step 1: Implement the Walk function
The task of the Walk function is to perform an in-order traversal of the binary tree and send each node’s value to a channel.
// Walk 中序遍历树 t，将所有值发送到通道 ch
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
// 递归遍历左子树
Walk(t.Left, ch)
// 发送当前节点的值
ch <- t.Value
// 递归遍历右子树
Walk(t.Right, ch)
}
// Walk 中序遍历树 t，将所有值发送到通道 ch
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
// 递归遍历左子树
Walk(t.Left, ch)
// 发送当前节点的值
ch <- t.Value
// 递归遍历右子树
Walk(t.Right, ch)
}Key points:
1. In-order traversal: Traverses in the order “left subtree → root node → right subtree”, so for a binary search tree, the output values will be in ascending order
2. Recursive structure: Each recursion sends the value to the same channel, ensuring the order of values
3. Blocking send: ch <- t.Value is a blocking operation; it only continues execution when a receiver is ready to receive Step 2: Test the Walk function Before implementing the Same function, let’s first test whether Walk works correctly.
func main() {
// 测试 Walk 函数
fmt.Println("测试 Walk 函数:")
ch := make(chan int)
go Walk(tree.New(1), ch)
for i := 0; i < 10; i++ {
fmt.Print(<-ch, " ")
}
fmt.Println()
}
Explanation:
– tree.New(k) creates a randomly structured binary search tree containing the values k, 2k, 3k, …, 10k
– go Walk(…) is used to execute the traversal in a separate goroutine to avoid blocking the main thread
– Reading 10 values from the channel should output 1 2 3 4 5 6 7 8 9 10
Step 3: Implement the Same function
This is the core of the entire exercise. We need to use the Walk function to determine whether two trees are equivalent.
// Same 判断树 t1 和 t2 是否包含相同的值
func Same(t1, t2 *tree.Tree) bool {
// 创建两个通道
ch1 := make(chan int)
ch2 := make(chan int)
// 启动两个 goroutine 分别遍历两棵树
go func() {
Walk(t1, ch1)
close(ch1)
}()
go func() {
Walk(t2, ch2)
close(ch2)
}()
// 同时从两个通道读取值并比较
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
// 如果两个通道都关闭了，说明遍历完成且所有值都相等
if !ok1 && !ok2 {
return true
}
// 如果一个通道关闭而另一个没有，或者值不相等，返回 false
if !ok1 || !ok2 || v1 != v2 {
return false
}
}
}
Design approach:
1. Parallel traversal: Start two goroutines to traverse the two trees separately, fully utilizing concurrency
2. Timely channel closure: Each goroutine closes its own channel after completing the traversal, letting the receiver know that the traversal has ended
3. Synchronous comparison: Read values from both channels simultaneously in the main goroutine, achieving a “traverse while comparing” effect
4. Early termination: Immediately returns false upon finding unequal values or inconsistent lengths, without needing to traverse the entire tree
Comparison logic explained:
v1, ok1 := <-ch1
v2, ok2 := <-ch2
– ok1 and ok2 indicate whether the channels are still open
– If !ok1 && !ok2: Both channels are closed, meaning both trees have the same number of nodes and all values are equal
– If !ok1 || !ok2: One channel closes first, meaning the trees have a different number of nodes
– If v1 != v2: The current node values are not equal
Step 4: Test the Same function
func main() {
// ... 前面的 Walk 测试代码 ...
// 测试 Same 函数
fmt.Println("\n测试 Same 函数:")
fmt.Println("Same(tree.New(1), tree.New(1)) =", Same(tree.New(1), tree.New(1)))
fmt.Println("Same(tree.New(1), tree.New(2)) =", Same(tree.New(1), tree.New(2)))
}
Expected output:
Same(tree.New(1), tree.New(1)) = true
Same(tree.New(1), tree.New(2)) = false
Complete Code
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk 中序遍历树 t，将所有值发送到通道 ch
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
// 递归遍历左子树
Walk(t.Left, ch)
// 发送当前节点的值到通道
ch <- t.Value
// 递归遍历右子树
Walk(t.Right, ch)
}
// Same 判断树 t1 和 t2 是否包含相同的值
func Same(t1, t2 *tree.Tree) bool {
// 创建两个通道用于接收树的值
ch1 := make(chan int)
ch2 := make(chan int)
// 启动两个 goroutine 分别遍历两棵树
go func() {
Walk(t1, ch1)
close(ch1) // 关闭通道，表示遍历完成
}()
go func() {
Walk(t2, ch2)
close(ch2) // 关闭通道，表示遍历完成
}()
// 同时从两个通道读取值并比较
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
// 如果两个通道都关闭了，说明遍历完成且所有值都相等
if !ok1 && !ok2 {
return true
}
// 如果一个通道关闭而另一个没有，或者值不相等，返回 false
if ok1 != ok2 || v1 != v2 {
return false
}
}
}
func main() {
// 测试 Walk 函数
fmt.Println("测试 Walk 函数：")
ch := make(chan int)
go Walk(tree.New(1), ch)
for i := 0; i < 10; i++ {
fmt.Print(<-ch, " ")
}
fmt.Println()
// 测试 Same 函数
fmt.Println("\n测试 Same 函数：")
fmt.Println("Same(tree.New(1), tree.New(1)) =", Same(tree.New(1), tree.New(1)))
fmt.Println("Same(tree.New(1), tree.New(2)) =", Same(tree.New(1), tree.New(2)))
}
Why is this solution more elegant?
1. No extra storage required
Traditional methods require storing traversal results in arrays, but this solution compares directly during the traversal process, saving memory space.
2. Lazy evaluation
Due to the blocking nature of channels, we essentially fetch values “on demand”. Once a problem is detected, we can terminate early without needing to traverse the entire tree.
3. Natural parallelism
The traversal of both trees can proceed simultaneously, fully utilizing the advantages of multi-core CPUs.
4. Concise code
The entire solution requires only about 40 lines of code, with clear logic that is easy to understand.
Further Reflection
Performance Analysis
Although this solution uses concurrency, note the following:
– Channel operation overhead: Every send and receive incurs synchronization overhead
– Goroutine creation cost: Although creating a goroutine is lightweight, it still has a cost
– Applicable scenarios: For small trees, traditional methods might be faster; for large trees or scenarios requiring stream processing, this solution has the advantage
Areas for Improvement
1. Using a buffered channel`make(chan int, bufferSize) can reduce the number of blocks and improve performance
2. Add a timeout mechanism: Prevents the traversal of a tree from getting stuck in an infinite loop
3. Support generics: Go 1.18+ can use generics to support different types of trees
Summary
Through this exercise, we learned:
1. ✅ How to use channels to pass data between goroutines
2. ✅ How to leverage the blocking nature of channels to achieve synchronization
3. ✅ How to signal task completion by closing a channel
4. ✅ How to apply concurrent thinking to algorithm design
Go’s concurrency model (CSP – Communicating Sequential Processes) allows us to write concurrent code in a declarative way, avoiding complex mechanisms like locks and condition variables found in traditional multithreaded programming. “Don’t communicate by sharing memory; share memory by communicating” — this is exactly the essence of Go’s concurrency philosophy.