# Equivalent Binary Trees

## Question 

> Two binary trees are equivalent if the sequences from their in order traversals are the same. 

## Example 

```
I: 
   tree_a               tree_b
           3                      8
         /   \                  /   \ 
        1     8                3    13  
       / \   / \             /   \
      1   2 5   13          1     5 
                          /   \ 
                         1     2  

O: treu because same sequence 1,1,2,3,5,8,13 
```

## Approach 

An easy approach is to construct with time and space $$O(V\_1) + O(V\_2)$$. Just in order traverse tree A and store that and traverse tree B then store that and compare in the end. 

A better way is to use two iterators to terminate early and only use the $$O(h\_1) + O(h\_2)$$space. 

## Parallel Approach 

We can compute the next value in the iterator in parallel after retrieving it. That will be a lot faster if the tree depth is high. 

```go

func walkHelper(t *tree.Tree, ch chan int) {
	if t == nil {
		return
	}
	
	walkHelper(t.Left, ch)

	ch <- t.Value 
	
	walkHelper(t.Right, ch)
	
	fmt.Println("lol")

}


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
	
	walkHelper(t, ch) 
	close(ch)

}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {

	ch1 := make(chan int)
	ch2 := make(chan int) 
	
	go Walk(t1, ch1)
	go Walk(t2, ch2) 
	
	for {
		val1, ok1 := <- ch1
		val2, ok2 := <- ch2
		
		if val1 != val2 || ok1 != ok2 {
			return false
		}
		
		if ok1 == false && ok2 == false {
			return true 
		}
	}

}
```

Goroutine is a more powerful version of coroutine because it can be parallelized.&#x20;

## References

* A tour of go - [concurrency exercise 8](https://tour.golang.org/concurrency/8)&#x20;
* Stackoverflow - [Go Tour Exercise: Equivalent Binary Trees](http://stackoverflow.com/questions/12224042/go-tour-exercise-equivalent-binary-trees)