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.

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.

References

• A tour of go - concurrency exercise 8

• Stackoverflow - Go Tour Exercise: Equivalent Binary Trees