Go concurrency practice: use channels to check the equivalence of binary trees

Preface

In most programming languages, it is quite complex to check if two binary trees store the same sequence of values. It is usually necessary to write a recursive algorithm to traverse the two trees and then compare them by node. But in the Go language, we can use its powerful concurrent primitives and channel (channel) mechanisms to write concise and elegant solutions.

This article will show how to use the concurrency of Go to solve the problem of binary tree equivalence through a classic exercise of Go Tour.

problem description

Given two binary trees, how can you tell if they contain the same sequence of values? Note that the structure of the tree is not required to be exactly the same, as long as the result of the middle order traversal is the same.

For example, the following two different binary trees store sequences 1, 1, 2, 3, 5, 8, 13:

    树1                    树2
     8                      5
    / \                    / \
   3   13                 2   8
  / \                    /   / \
 1   5                  1   3  13
/
1

Traditional solutions require:
1. Carry out the in-order traversal of the two trees respectively, and store the results in the array
2. Compare whether the two arrays are equal

This method requires additional storage space, and the code is more lengthy. Let’s see how Go solves this in a more elegant way.

Core Concept: Channel of Go

Before starting to implement, review the key features of the Go channel:

– Channels are type-safe queues: chan int represents a channel of an integer type
– Send and receive operations: ch <- value Send value, value := <-ch receive value – Blocking characteristics: Send and receive operations will block until the other party is ready – Can be closed: use close(ch) to close the channel, the receiver can check whether the channel is closed through value, ok := <-ch – Match with goroutine: channels are the main way to communicate between goroutines implementation steps Step 1: Implement the walk function The task of the walk function is to traverse the binary tree in the order and send the value of each node into the 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 point analysis:

1. In-order traversal: traverse in the order of “Left Subtree → Root Node → Right Subtree”, so that for sorted binary trees, the output value will be ascending
2. Recursive Structure: Each recursion will send the value to the same channel to ensure the order of the value
3. Blocking sending: ch <- t.value is a blocking operation, and will continue to execute only when a receiver is ready to receive Step 2: Test the walk function Before implementing the SAME function, let’s first test whether the walk is working properly.

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()
}

Description:

– Tree.new(k) creates a sorted binary tree of random structure, containing values k, 2k, 3k, …, 10k
– Use Go Walk(…) to perform traversing in a standalone goroutine, avoid blocking the main thread
– Read 10 values from the channel and should output 1 2 3 4 5 6 7 8 9 10

Step 3: Implement the SAME function

This is the core of the whole exercise. We need to use the walk function to determine whether the 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 ideas:

1. Parallel traversal: start two goroutines to traverse two trees, make full use of the concurrency ability
2. Close the channel in time: each goroutine closes its own channel after completing the traversal, let the receiver know that the traversal is over
3. Synchronous comparison: read the value from two channels at the same time in the main goroutine, and achieve the effect of “comparing while traversing”
4. Early termination: Once the unequal values or lengths are found to be inconsistent, return FALSE immediately, no need to traverse the complete tree

Details of the comparison logic:

v1, ok1 := <-ch1
v2, ok2 := <-ch2

– OK1 and OK2 indicate whether the channel is still open
– If !ok1 && !ok2: Both channels are closed, the number of nodes of the two trees is the same and all values are equal
– If !ok1 || !ok2: One channel is closed first, indicating that the number of nodes of the two trees is different
– if v1 != v2: the value of the current node is 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 plan more elegant?

1. No additional storage required

Traditional methods need to store the traversal results into an array, and this scheme directly compares during the traversal process, saving memory space.

2. Lazy Evaluation

Due to the blocking characteristics of the channel, we are actually “on demand” to get the value. Once the problem is found, it can be terminated early, and there is no need to traverse the entire tree.

3. Natural parallelism

The traversal of the two trees can be carried out at the same time, making full use of the advantages of multi-core CPUs.

4. The code is concise

The entire solution only takes about 40 lines of code, which is clear and easy to understand.

Deep thinking

performance analysis

Although this scheme uses concurrency, it should be noted that:

– Overhead of channel operation: Synchronization overhead for each send and receive
– Creation cost of goroutine: Creating goroutine although lightweight, but also cost
– Applicable scenarios: Traditional methods may be faster for small trees; this scheme is more advantageous for large trees or scenarios that require streaming

improve direction

1. Use the buffer channel `make(chan int, buffersize) to reduce the number of blocking and improve performance
2. Add timeout mechanism: prevent the traversal of a tree into 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 pass data between goroutines using channels
2. ✅ How to use the blocking characteristics of the channel to achieve synchronization
3. ✅ How to signal the completion of the task by closing the channel
4. ✅ How to apply concurrent thinking to algorithm design

Go’s concurrency model (CSP – Communicating Sequential Processes) enables us to write concurrent code in a declarative manner, avoiding complex mechanisms such as locks and conditional variables in traditional multi-threaded programming. “Don’t communicate through shared memory, but share memory through communication” – this is the essence of Go concurrency philosophy.