Given two binary trees, the task is to find if both of them are identical or not.  
Example 2:
Input:
     1          1
   /   \      /   \
  2     3    2     3
Output: Yes
Explanation: There are two trees both
having 3 nodes and 2 edges, both trees
are identical having the root as 1,
left child of 1 is 2 and right child
of 1 is 3.
Example 2:
Input:
    1       1
  /  \     /  \
 2    3   3    2
Output: No
Explanation: There are two trees both
having 3 nodes and 2 edges, but both
trees are not identical.
Your task:
Since this is a functional problem you don't have to worry about input, you just have to complete the function isIdentical() that takes two roots as parameters and returns true or false. The printing is done by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 10^{5}
1 <=Data of a node <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
class Node:
    def _init_(self, val):
        self.right = None
        self.data = val
        self.left = None
'''

class Solution:
    #Function to check if two trees are identical.
    def isIdentical(self,root1, root2):
        # Code here

Solutions:
class Solution:

	def isIdentical(self, root1, root2):

		def isidentical(root1, root2):
			if root1 is None or root2 is None:
				if root2 is None and root1 is None:
					return True
				else:
					return False
			return root1.data == root2.data and isidentical(root1.right, root2.right) and isidentical(root1.left, root2.left)
		return isidentical(root1, root2)


class Solution:

	def isIdentical(self, root1, root2):
		if not root1 or not root2:
			return root1 == root2
		return root1.data == root2.data and self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)


class Solution:

	def isIdentical(self, root1, root2):
		f = []
		Solution.Identical(self, root1, root2, f)
		if len(f) == 0:
			return True
		return False

	def Identical(self, root1, root2, f):
		if root1 == None and root2 != None:
			f.append(0)
			return
		if root1 != None and root2 == None:
			f.append(0)
			return
		if root1 == None:
			return
		if root2 == None:
			return
		if root1.data != root2.data:
			f.append(0)
		Solution.Identical(self, root1.left, root2.left, f)
		Solution.Identical(self, root1.right, root2.right, f)


class Solution:

	def isIdentical(self, root1, root2):

		def isSame(node1, node2):
			if not node1 and (not node2):
				return True
			if not node1 or not node2:
				return False
			if node1.data != node2.data:
				return False
			return isSame(node1.left, node2.left) and isSame(node1.right, node2.right)
		return isSame(root1, root2)


class Solution:

	def isIdentical(self, root1, root2):
		if root1 is None and root2 is None:
			return 1
		if root1 is not None and root2 is not None:
			if root1.data != root2.data:
				return 0
			return self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)


class Solution:

	def isIdentical(self, root1, root2):
		if root1 == None and root2 == None:
			return True
		elif root1 != None and root2 != None:
			return root1.data == root2.data and self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)
		return False


class Solution:

	def isIdentical(self, root1, root2):

		def elements(root, q):
			if root is None:
				return
			q.append(root.data)
			elements(root.left, q)
			elements(root.right, q)
			return q
		a1 = elements(root1, [])
		a2 = elements(root2, [])
		if len(a1) != len(a2):
			return False
		for i in range(len(a1)):
			if a1[i] != a2[i]:
				return False
		return True


class Solution:

	def iden(self, root1, root2):
		if root1 == None or root2 == None:
			return root1 == root2
		return root1.data == root2.data and self.iden(root1.left, root2.left) and self.iden(root1.right, root2.right)

	def isIdentical(self, root1, root2):
		return self.iden(root1, root2)


class Solution:

	def isIdentical(self, root1, root2):
		t = root1
		s = root2
		ans1 = []
		ans2 = []

		def traverse(t, ans1):
			if t is not None:
				ans1.append(t.data)
				if t.left is not None:
					traverse(t.left, ans1)
				if t.right is not None:
					traverse(t.right, ans1)
		traverse(t, ans1)
		traverse(s, ans2)
		if ans1 == ans2:
			return True
		else:
			return False


from collections import deque

class Solution:

	def levelorder(self, root):
		if root == None:
			return None
		q = deque()
		arr = []
		q.append(root)
		while len(q) > 0:
			temp = q.popleft()
			arr.append(temp.data)
			if temp.left != None:
				q.append(temp.left)
			if temp.right != None:
				q.append(temp.right)
		return arr

	def isIdentical(self, root1, root2):
		arr1 = self.levelorder(root1)
		arr2 = self.levelorder(root2)
		if len(arr1) != len(arr2):
			return 0
		for i in range(len(arr1)):
			if arr1[i] != arr2[i]:
				return 0
		return 1


class Solution:

	def isIdentical(self, root1, root2):
		if not root1 and (not root2):
			return True
		if root1 and (not root2) or (not root1 and root2):
			return 0
		l = self.isIdentical(root1.left, root2.left)
		r = self.isIdentical(root1.right, root2.right)
		val = root1.data == root2.data
		if l and r and val:
			return 1
		return 0


class Solution:

	def isIdentical(self, root1, root2):
		if root1 is None and root2 is None:
			return True
		elif root1 is None and root2 is not None:
			return False
		elif root1 is not None and root2 is None:
			return False
		is_left_identical = self.isIdentical(root1.left, root2.left)
		is_right_identical = self.isIdentical(root1.right, root2.right)
		is_data_identical = root1.data == root2.data
		if is_left_identical and is_right_identical and is_data_identical:
			return True
		return False


class Solution:

	def isIdentical(self, root1, root2):
		if root1 is None and root2 is None:
			return True
		if root1 is not None and root2 is not None:
			return root1.data == root2.data and self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)
		return False


class Solution:

	def isIdentical(self, root1, root2):
		if not root1 and (not root2):
			return True
		if not root1 or not root2:
			return False
		q1 = [root1]
		q2 = [root2]
		while q1 and q2:
			curr1 = q1.pop(0)
			curr2 = q2.pop(0)
			if curr1.data != curr2.data:
				return False
			if curr1.left and (not curr2.left) or (not curr1.left and curr2.left):
				return False
			if curr1.right and (not curr2.right) or (not curr1.right and curr2.right):
				return False
			if curr1.left and curr2.left:
				q1.append(curr1.left)
				q2.append(curr2.left)
			if curr1.right and curr2.right:
				q1.append(curr1.right)
				q2.append(curr2.right)
		return True


class Solution:

	def isIdentical(self, root1, root2):
		if not root1 and (not root2):
			return 1
		if not root1 or not root2:
			return 0
		if root1.data == root2.data:
			return self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)
		else:
			return 0


class Solution:

	def isIdentical(self, root1, root2):
		if root1 == None and root2 == None:
			return 1
		elif root1 != None and root2 != None:
			if root1.data != root2.data:
				return 0
				if root1.data == root2.data:
					return 1
			return self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)


class Solution:

	def isIdentical(self, root1, root2):
		if not root1 and (not root2):
			return True
		if not root1 or not root2:
			return False
		if root1.data == root2.data:
			return self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)
		else:
			return False


class Solution:

	def isIdentical(self, root1, root2):

		def check(x, y):
			if x and y and (x.data == y.data):
				lx = x.left
				ly = y.left
				rx = x.right
				ry = y.right
				return check(lx, ly) and check(rx, ry)
				return True
			elif x == None and y == None:
				return True
			else:
				return False
		return check(root1, root2)


class Solution:

	def isIdentical(self, root1, root2):
		ans = self.meth(root1, root2)
		return ans

	def meth(self, n1, n2):
		if n1 == None and n2 == None:
			return True
		if n1 == None or n2 == None:
			return False
		if n1.data != n2.data:
			return False
		return self.meth(n1.left, n2.left) and self.meth(n1.right, n2.right)


class Solution:

	def solve(self, root, arr):
		if root == None:
			return
		arr.append(root.data)
		self.solve(root.left, arr)
		self.solve(root.right, arr)

	def isIdentical(self, root1, root2):
		ans1 = []
		ans1.append(root1.data)
		self.solve(root1, ans1)
		ans2 = []
		ans2.append(root2.data)
		self.solve(root2, ans2)
		if ans1 == ans2:
			return True
		else:
			return False


class Solution:

	def isIdentical(self, root1, root2):

		def check_equal(root1, root2):
			if not root1 and (not root2):
				return True
			elif root1 and root2:
				return root1.data == root2.data and check_equal(root1.left, root2.left) and check_equal(root1.right, root2.right)
			return False
		return check_equal(root1, root2)


from collections import deque

class Solution:

	def isIdentical(self, root1, root2):
		if root1 is None and root2 is None:
			return True
		if root1 is None or root2 is None:
			return False
		if root1.data != root2.data:
			return False
		return self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)


class Solution:

	def isIdentical(self, root1, root2):

		def preorder(root, l):
			if root is None:
				return
			l.append(root.data)
			if root.left:
				root.left = preorder(root.left, l)
			if root.right:
				root.right = preorder(root.right, l)
		l1 = []
		preorder(root1, l1)
		l2 = []
		preorder(root2, l2)
		if l1 == l2:
			return True
		return False


class Solution:

	def isIdentical(self, root1, root2):
		if root1 is None and root2 is None:
			return True
		if root1 is None or root2 is None:
			return False
		if root1.data != root2.data:
			return False
		left_identical = self.isIdentical(root1.left, root2.left)
		right_identical = self.isIdentical(root1.right, root2.right)
		return left_identical and right_identical


class Solution:

	def isIdentical(self, root1, root2):

		def find(root1, root2):
			if root1 == None and root2 == None:
				return True
			if root1 == None or root2 == None:
				return False
			if root1.data != root2.data:
				return False
			left = find(root1.left, root2.left)
			right = find(root1.right, root2.right)
			if left == False or right == False:
				return False
			return True
		return find(root1, root2)


class Solution:

	def isIdentical(self, p, q):

		def check(root1, root2):
			if root1 == None and root2 == None:
				return True
			if root1 == None or root2 == None:
				return False
			if root1.data != root2.data:
				return False
			lh = check(root1.left, root2.left)
			rh = check(root1.right, root2.right)
			return lh and rh
		ans = check(p, q)
		return ans


class Solution:

	def isIdentical(self, root1, root2):
		if root1 == None or root2 == None:
			return root1 == root2
		if root1.data != root2.data:
			return False
		leftcheck = self.isIdentical(root1.left, root2.left)
		rightcheck = self.isIdentical(root1.right, root2.right)
		return leftcheck and rightcheck


class Solution:

	def isIdentical(self, root1, root2):
		if root1 == None and root2 == None:
			return True
		if root1 != None and root2 == None:
			return False
		if root1 == None and root2 != None:
			return False
		left = self.isIdentical(root1.left, root2.left)
		right = self.isIdentical(root1.right, root2.right)
		value = root1.data == root2.data
		if left and right and value:
			return True
		else:
			return False


def traversal(root):
	if root == None:
		return 'N'
	left = traversal(root.left)
	right = traversal(root.right)
	return left + right + str(root.data)

class Solution:

	def isIdentical(self, root1, root2):
		return traversal(root1) == traversal(root2)


class Solution:

	def isIdentical(self, p, q):
		if not p and (not q):
			return True
		if p and (not q):
			return False
		if q and (not p):
			return False
		if p.data != q.data:
			return False
		return self.isIdentical(p.left, q.left) and self.isIdentical(p.right, q.right)