[Interview Qn] Checking if 2 Binary Trees Are Equal

Write a function same(root1, root2) that takes in 2 binary tree roots, and returns True if the are equal else False.

2 binary trees are equal if they have the same structure and values.

# 2 binary trees with same structure but different values

 _____1___ 
 |       | 
 2___    3 
    |      
    4

 _____1___ 
 |       | 
 2___    3 
    |      
    5 

# 2 binary trees with the same values but different structure

_____1___ 
|       | 
2___    3 
   |      
   4

  ___1___ 
  |     | 
__2     3 
|         
4    

For 2 binary trees to be the same, both structure and values must be exactly the same.

class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

def same(root1, root2):
    # TODO

Some test cases to help you

class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

ta1 = None
ta2 = None

tb1 = Node(1)
tb2 = Node(1)

tc1 = Node(1)
tc1.left = Node(2)
tc2 = Node(1)
tc2.left = Node(2)

td1 = Node(1)
td1.right = Node(2)
td2 = Node(1)
td2.right = Node(2)

te1 = Node(1)
te1.left = Node(2)
te1.right = Node(3)
te1.right.left = Node(4)
te2 = Node(1)
te2.left = Node(2)
te2.right = Node(3)…