Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money.

Analysis of the question

  • A walk function needs to be implemented
// Walk tree t sends all values from tree to Channel CH.
func Walk(t *tree.Tree, ch chan int)
Copy the code
  • We need to implement a same function using the previously generated walk function to verify that the two binary trees are equivalent

Thought analysis

In fact, we only know a condition of binary search tree, we might as well look at the properties of binary search tree:

An empty tree, or a binary tree with the following properties: (1) If the left subtree is not empty, then the values of all nodes of the left subtree are less than the values of its root node; (2) If the right subtree is not empty, then the values of all nodes in the right subtree are greater than the values of its root node; (3) the left and right subtrees are also binary sorting trees; (4) There are no nodes with equal key values.Copy the code

For those interested in tree data structures or who need to learn more about them, please refer to my previous article:

  • Data Structure Tree (1)
  • Data Structure Tree (2)
  • Data Structure Tree (3)

Therefore, the binary search tree must not have the same nodes, and the preorder traversal must be ordered.

We can write the nodes of the binary tree in sequence to the channel, and then read from the channel and write to the array.

Code implementation

  func DFS(t *tree.Tree, ch chan int){
      if t == nil {
          return
      }
      ift.Left ! =nil {
          DFS(t.Left, ch)
      }
      ch <- t.Value
      ift.Right ! =nil {
          DFS(t.Right, ch)
      }
  }
Copy the code

A simple DFS that reads the nodes of a binary tree in sequence.

func Walk(t *tree.Tree, ch chan int) {
    DFS(t,ch)
    close(ch)
}
Copy the code

The walk function calls DFS to traverse the nodes of the tree.

The data is then read from the channel and put into the array. But think of it as not slicing, just reading the second channel in the for loop

for i :=range ch1{
  j,ok := <- ch2
  if! ok {return false
  }
  ifi! =j {return false
  }
  fmt.Printf("ch1: %v - ch2: %v\n", i, j)
}
Copy the code

Overall implementation:

func Same(t1, t2 *tree.Tree) bool{
    ch1 := make(chan int)
    ch2 := make(chan int)
    go Walk(t1, ch1) 
    go Walk(t2, ch2)
    for i :=range ch1{
      j,ok := <- ch2
      if! ok {return false
      }
      ifi! =j {return false
      }
      fmt.Printf("ch1: %v - ch2: %v\n", i, j)
    }
    return true
} 
Copy the code

conclusion

The initial idea was to write the traversed tree to a channel and then read from the channel and write to the array. This was actually a very “single-threaded” idea, because if it were an algorithm, it would naturally read the data by DFS writing to and comparing arrays. At the moment the channel didn’t do anything, but later it occurred to us that we could compare the two trees by reading another channel while reading the channel. This topic gives the author a further understanding of the channel.

When looking up information on the Internet, I found that some people read data from the channel, and then do xor to the data, because this makes use of the binary search tree without repetition, so when the xOR result is 0, the two trees must be equal. But that’s not true, because they don’t tell us how many trees there are, so if A is 1,2, or 01 ^ 10:11, then if B is 3, then we still get the same number of trees.