# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-3/advanced_topics/concurrency/goroutine/equivalent-binary-trees.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.