Given two Binary Trees. Check whether they are Isomorphic or not.
Note: 
Two trees are called isomorphic if one can be obtained from another by a series of flips, i.e. by swapping left and right children of several nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.
For example, the following two trees are isomorphic with the following sub-trees flipped: 2 and 3, NULL and 6, 7 and 8.
Example 1:
Input:
 T1    1     T2:   1
     /   \        /  \
    2     3      3    2
   /            /
  4            4
Output: No
Example 2:
Input:
T1    1     T2:    1
    /  \         /   \
   2    3       3     2
  /                    \
  4                     4
Output: Yes
Your Task:
You don't need to read input or print anything. Your task is to complete the function isomorphic() that takes the root nodes of both the Binary Trees as its input and returns True if the two trees are isomorphic. Else, it returns False. (The driver code will print Yes if the returned values are true, otherwise false.)
 
Expected Time Complexity: O(min(M, N)) where M and N are the sizes of the two trees.
Expected Auxiliary Space: O(min(H1, H2)) where H1 and H2 are the heights of the two trees.
Constraints:
1<=Number of nodes<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    # Return True if the given trees are isomotphic. Else return False.
    def isIsomorphic(self, root1, root2): 
        #code here.

Solutions:
class Solution:

	def isIsomorphic(self, root1, root2):

		def pre(root):
			if root == None:
				return
			self.anspre.append(root.data)
			pre(root.left)
			pre(root.right)

		def post(root):
			if root == None:
				return
			post(root.left)
			post(root.right)
			self.anspost.append(root.data)
		self.anspre = []
		self.anspost = []
		pre(root1)
		post(root2)
		anspre1 = self.anspre
		anspost1 = self.anspost
		self.anspre = []
		self.anspost = []
		pre(root2)
		post(root1)
		anspre2 = self.anspre
		anspost2 = self.anspost
		if anspre1 == anspre2 and anspost1 == anspost2:
			return True
		return anspre1 == anspost1[::-1]


class Solution:

	def isIsomorphic(self, rt1, rt2):
		if rt1 is None and rt2 is None:
			return 1
		if rt1 is None or rt2 is None:
			return 0
		if rt1.data != rt2.data:
			return 0
		return (self.isIsomorphic(rt1.left, rt2.left) or self.isIsomorphic(rt1.left, rt2.right)) and (self.isIsomorphic(rt1.right, rt2.left) or self.isIsomorphic(rt1.right, rt2.right))


class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def isIsomorphic(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
		is_left_isomorphic = self.isIsomorphic(root1.left, root2.left) and self.isIsomorphic(root1.right, root2.right)
		is_right_isomorphic = self.isIsomorphic(root1.left, root2.right) and self.isIsomorphic(root1.right, root2.left)
		return is_left_isomorphic or is_right_isomorphic


class Solution:

	def isIsomorphic(self, 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
		a = self.isIsomorphic(root1.left, root2.left) and self.isIsomorphic(root1.right, root2.right)
		b = self.isIsomorphic(root1.left, root2.right) and self.isIsomorphic(root1.left, root2.right)
		return a or b


class Solution:

	def isIsomorphic(self, 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
		l = self.isIsomorphic(root1.left, root2.left) and self.isIsomorphic(root1.right, root2.right)
		r = self.isIsomorphic(root1.left, root2.right) and self.isIsomorphic(root1.left, root2.right)
		return l or r


class Solution:

	def isIsomorphic(self, root1, root2):

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


def slove(r1, r2):
	if r1 is None and r2 is None:
		return True
	if r1 is None or r2 is None:
		return False
	if r1.data != r2.data:
		return False
	return slove(r1.left, r2.left) and slove(r1.right, r2.right) or (slove(r1.left, r2.right) and slove(r1.right, r2.left))

class Solution:

	def isIsomorphic(self, root1, root2):
		return slove(root1, root2)


class Solution:

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


class Solution:

	def isIsomorphic(self, root1, root2):
		if root1 is None and root2 is None:
			return True
		if root1 is not None and root2 is None:
			return False
		if root1 is None and root2 is not None:
			return False
		if root1.data == root2.data:
			first = self.isIsomorphic(root1.left, root2.left)
			second = self.isIsomorphic(root1.right, root2.right)
			third = self.isIsomorphic(root1.right, root2.left)
			fourth = self.isIsomorphic(root1.left, root2.right)
			return first and second or (third and fourth)
		else:
			return False


class Solution:

	def isIsomorphic(self, root1, root2):

		def ino(root):
			a1 = []
			if root:
				a1 += ino(root.left)
				a1.append(root.data)
				a1 += ino(root.right)
			return a1

		def posto(root):
			a2 = []
			if root:
				a2 += posto(root.right)
				a2.append(root.data)
				a2 += posto(root.left)
			return a2
		x = ino(root1)
		y = posto(root2)
		z = ino(root2)
		if x == y or x == z:
			return True
		return False


class Solution:

	def isIsomorphic(self, root1, root2):

		def solve(n1, n2):
			if not n1 and (not n2):
				return True
			if n1 and (not n2):
				return False
			if not n1 and n2:
				return False
			if n1.data != n2.data:
				return False
			return solve(n1.left, n2.left) and solve(n1.right, n2.right) or (solve(n1.left, n2.right) and solve(n1.left, n2.right))
		return solve(root1, root2)


def solve(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
	le = solve(root1.left, root2.right) and solve(root1.right, root2.left)
	re = solve(root1.left, root2.left) and solve(root1.right, root2.right)
	return le or re

class Solution:

	def isIsomorphic(self, root1, root2):
		return solve(root1, root2)


class Solution:

	def isIsomorphic(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:
			ll = self.isIsomorphic(root1.left, root2.left)
			lr = self.isIsomorphic(root1.left, root2.right)
			rl = self.isIsomorphic(root1.right, root2.left)
			rr = self.isIsomorphic(root1.right, root2.right)
			return ll and rr or (lr and rl)
		else:
			return False


from collections import deque

class Solution:

	def isIsomorphic(self, 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
		a = self.isIsomorphic(root1.left, root2.left)
		b = self.isIsomorphic(root1.right, root2.right)
		c = self.isIsomorphic(root1.left, root2.right)
		d = self.isIsomorphic(root1.right, root2.left)
		return a & b | c & d


class Solution:

	def isIsomorphic(self, root_1, root_2):
		if root_1 is None and root_2 is None:
			return True
		if root_1 is None or root_2 is None:
			return False
		if root_1.data != root_2.data:
			return False
		one_condition = self.isIsomorphic(root_1.left, root_2.left) and self.isIsomorphic(root_1.right, root_2.right)
		swap_condition = self.isIsomorphic(root_1.left, root_2.right) and self.isIsomorphic(root_1.right, root_2.left)
		return one_condition or swap_condition


class Solution(object):

	def isIsomorphic(self, 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 self.isIsomorphic(node1.left, node2.left) and self.isIsomorphic(node1.right, node2.right) or (self.isIsomorphic(node1.left, node2.right) and self.isIsomorphic(node1.right, node2.left))


class Solution:

	def fun(self, 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
		return self.fun(root1.left, root2.left) and self.fun(root1.right, root2.right)

	def isIsomorphic(self, root1, root2):
		if root1 == None and root2 == None:
			return True
		elif root1 == None and root2 != None or (root1 != None and root2 == None):
			return False
		else:
			if root1.data == root2.data:
				x = self.isIsomorphic(root1.left, root2.right) and self.isIsomorphic(root1.right, root2.left)
				y = self.fun(root1, root2)
			else:
				return False
			return x or y


class Solution:

	def isIsomorphic(self, root1, root2):

		def solve(x, y):
			if not x and (not y):
				return True
			elif x and y:
				return x.data == y.data and solve(x.left, y.right) and solve(x.right, y.left) or (x.data == y.data and solve(x.left, y.left) and solve(x.right, y.right))
			return False
		if root1 and root2:
			return solve(root1, root2)
		return True


class Solution:

	def isIsomorphic(self, root1, root2):

		def check(a, b):
			if not a and (not b):
				return True
			elif a and b:
				return a.data == b.data and check(a.left, b.right) and check(a.right, b.left) or (a.data == b.data and check(a.left, b.left) and check(a.right, b.right))
			return False
		if root1 and root2:
			return check(root1, root2)
		return True


class Solution:

	def isIsomorphic(self, root1, root2):

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


class Solution:

	def isIsomorphic(self, 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
		op1 = self.isIsomorphic(root1.left, root2.left) and self.isIsomorphic(root1.right, root2.right)
		op2 = self.isIsomorphic(root1.left, root2.right) and self.isIsomorphic(root1.right, root2.left)
		return op1 or op2


class Solution:

	def isIsomorphic(self, root1, root2):
		if root1 is None and root2 is None:
			return 1
		if root1 is None or root2 is None:
			return 0
		if root1.data != root2.data:
			return 0
		a = self.isIsomorphic(root1.left, root2.right) and self.isIsomorphic(root1.right, root2.left)
		b = self.isIsomorphic(root1.left, root2.left) and self.isIsomorphic(root1.right, root2.right)
		if a or b:
			return 1
		return 0


class Solution:

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

	def isIsomorphic(self, root1, root2):
		return self.rec_isomorph(root1, root2)


class Solution:

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


class Solution:

	def isIsomorphic(self, root1, root2):
		if root1 == None or root2 == None:
			return root1 == root2
		if root1.data != root2.data:
			return False
		l1 = self.isIsomorphic(root1.left, root2.left)
		l2 = self.isIsomorphic(root1.right, root2.right)
		l3 = self.isIsomorphic(root1.left, root2.right)
		l4 = self.isIsomorphic(root1.right, root2.left)
		return l1 and l2 or (l3 and l4)


class Solution:

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


class Solution:

	def isIsomorphic(self, root1, root2):

		def foo(root1, root2):
			if not (root1 or root2):
				return True
			if root1 is None or root2 is None:
				return False
			if root1.data != root2.data:
				return False
			l1 = root1.left
			r1 = root1.right
			l2 = root2.left
			r2 = root2.right
			return foo(l1, l2) and foo(r1, r2) or (foo(l1, r2) and foo(r1, l2))
		return foo(root1, root2)


class Solution:

	def isIsomorphic(self, root1, root2):
		x = self.inorder(root1)
		y = self.preorder(root2)
		z = self.inorder(root2)
		if x == y or x == z:
			return True
		else:
			return False

	def inorder(self, root):
		if root == None:
			return []
		arr = []
		arr += self.inorder(root.left)
		arr.append(root.data)
		arr += self.inorder(root.right)
		return arr

	def preorder(self, root):
		if root == None:
			return []
		arr = []
		arr += self.preorder(root.right)
		arr.append(root.data)
		arr += self.preorder(root.left)
		return arr


class Solution:

	def isIsomorphic(self, root1, root2):
		k = root1
		l = root1
		global a, b, c
		(a, b, c) = ([], [], [])

		def sol4(l):
			global c
			if l:
				c.append(l.data)
				sol4(l.left)
				sol4(l.right)
		sol4(l)

		def sol(root1):
			if not root1:
				return
			if root1:
				if root1.left and root1.right == None:
					root1.right = root1.left
					root1.left = None
				if root1.right and root1.left == None:
					root1.left = root1.right
					root1.right = None
				if root1.left and root1.right:
					temp = root1.left
					root1.left = root1.right
					root1.right = temp
			sol(root1.left)
			sol(root1.right)
		sol(root1)

		def sol2(k):
			global a
			if k:
				a.append(k.data)
				sol2(k.left)
				sol2(k.right)
		sol2(k)

		def sol3(k):
			global b
			if k:
				b.append(k.data)
				sol3(k.left)
				sol3(k.right)
		sol3(root2)
		if a == b or c == b:
			return True
		return False