The solution provided below is updated for channel synchronization without using the time delays in go routines or main function.

The earlier solution can be found here.

Also, you can get an excellent introduction to concept of Binary Trees here and here.

If you are trying to learn the Go Programming Language, A Tour of Go is very concise resource to get you started. The Tour covers most important features of the Go language and also has exercises in between to solidify the learnings by "doing it".

This post is an effort to provide the solution to one of the Exercise: Equivalent Binary Trees. The Exercise is to use channels to store the tree values and to find out whether the two Binary trees are equivalent by using Go's Concurrency and Channels.

A function to check whether two binary trees store the same sequence is quite complex in most languages. We'll use Go's concurrency and channels to write a simple solution.

First and Foremost activity is to break down the problem in parts and solve it — Bottom-up approach.

  1. Understand the Binary Trees.
  2. Design an Algorithm to traverse the Binary Trees and store the tree values on Channels
  3. Check Whether the 2 Binary Trees store the same values.

Binary Trees

A Tree is a Data Structure in which each Node is comprised of Some Data and Pointers to Left, Right Child Nodes.

A Binary Tree is type of Tree Structure where Each Node has some data and pointers to at most two child nodes.

The Binary Tree Structure we will be using is as below.

type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

Binary Search Tree(BST) is special form of Binary Tree. One of the important feature of the Binary Search Tree (BST) is, For Each Node in the Binary Tree — Each Left Node Value is Less than its own value and Each Right Node Value is greater. Binary Search Tree is also called as Ordered or Sorted Binary Tree. Simply Speaking,

Left Node value < Node Value < Right Node Value

The Channel Output Expected in the Exercise is ascending values of the Tree Node Values like numbers 1, 2, 3, …, 10.

You can see stack-overflow answer on difference between Binary Tree and Binary Search Tree.

Walk Function

Walk function has recursive calls as we need to maintain the reference to the Parent Node and traverse the Entire Tree Structure. We also need to collect values of each of the node and its children and store them on Go Channel.

  1. Check if current node in the tree is null; if null then return.
  2. If there is Left Node to Current Node then Walk to that Left Child Node.
  3. Repeat 1,2 till we find the Left Node as Null.
  4. When encountered Left Node null — Push the Current Value of Node on Channel.
  5. Also Check if the Right Node is Null; if Not Null, repeat 1,2,3,4 for the Right Node.
  6. At the end of the Walk, Channel will be filled with the values sorted in ascending order.

Same Function

Same function takes 2 Binary Trees and returns boolean value whether the 2 trees store the same values.

  1. Same function receives 2 binary trees.
  2. Make 2 channels — these 2 channels will be used to fill values from the Trees using the Walk function described above. Remember that the channel stores the number values in the ascending order.
  3. A Channel in Go is FIFO (first in, first out) message queue. So, we unload these 2 channels queues created in step 2 above to for each value and compare the two values for equality.
  4. If all values are equal, we return True else Return False.

There could be better implementation for the this Go Exercise. I am also working to optimize the solution and trying to find out the flaws in the code.

Suggestions are welcome. :-)

Code is Mysterious as People are.

Solution

Test on Go Playground — https://play.golang.org/p/fWIsbkHn7Ok

package main
import (
 "fmt"
"golang.org/x/tour/tree"
)
func main() {
 fmt.Println("Tour of Go Solution - Equivalent Binary Trees")
t1 := tree.New(5)
 t2 := tree.New(5)
 fmt.Println("Tree 1:", t1)
 fmt.Println("Tree 2:", t2)
 fmt.Println("Are they same? - ", Same(t1, t2))
 fmt.Println("------")
t3 := tree.New(2)
 t4 := tree.New(3)
 fmt.Println("Tree 3:", t3)
 fmt.Println("Tree 4:", t4)
 fmt.Println("Are they same? - ", Same(t3, t4))
 fmt.Println("")
}
func Walker(t *tree.Tree, ch chan int) {
 Walk(t, ch)
 //close the channel to avoid panic
 close(ch)
}
func Walk(t *tree.Tree, ch chan int) {
 if t == nil {
  return
 } else if t.Left == nil {
  ch <- t.Value
  if t.Right != nil {
   Walk(t.Right, ch)
  }
  return
 } else {
  Walk(t.Left, ch)
 }
 ch <- t.Value
 if t.Right != nil {
  Walk(t.Right, ch)
 }
}
func Same(t1, t2 *tree.Tree) bool {
 var br bool
 done := make(chan bool)
 c1 := make(chan int)
 c2 := make(chan int)
 go Walker(t1, c1)
 go Walker(t2, c2)
 go func() {
  for i := range c1 {
   if i == <-c2 {
    br = true
   } else {
    br = false
    break
   }
  }
  done <- true
 }()
 <-done
 return br
}