Given a binary tree, check if the tree can be folded or not. A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
Consider the below trees:
(a) and (b) can be folded.
(c) and (d) cannot be folded.
(a)
       10
     /    \
    7      15
     \    /
      9  11
(b)
        10
       /  \
      7    15
     /      \
    9       11
(c)
        10
       /  \
      7   15
     /    /
    5   11
(d)
         10
       /   \
      7     15
    /  \    /
   9   10  12
 
Example 1:
Input:
     10
    /    \
   7     15
 /  \   /  \
N   9  11   N
Output:Yes
Explaination:Structure of every left and right subtree are same. 
Example 2:
Input:
      10
    /    \
   7     15
 /  \   /  \
5   N  11   N
Output: No
Explaination: 7's left child is not NULL and right child is NULL. That's why the tree is not foldable. 
Your Task:
The task is to complete the function isFoldable() that takes root of the tree as input and returns true or false depending upon whether the tree is foldable or not.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
0 <= n <= 10^{3}
1 <= data of node <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None



'''

#Function to check whether a binary tree is foldable or not.

def IsFoldable(root):

    # code here

Solutions:
def IsFoldable(root):

	def check(n1, n2):
		if not n1 and (not n2):
			return True
		if not n1 or not n2:
			return False
		return check(n1.left, n2.right) and check(n1.right, n2.left)
	if not root:
		return True
	return check(root.left, root.right)


def check(left, right):
	if left is None and right is None:
		return True
	if left is None or right is None:
		return False
	return check(left.left, right.right) and check(left.right, right.left)

def IsFoldable(root):
	if root is None:
		return True
	return check(root.left, root.right)


def IsFoldable(root):
	if not root:
		return True
	q = deque([])
	q.append(root.left)
	q.append(root.right)
	while q:
		x = q.popleft()
		y = q.popleft()
		if not x and (not y):
			continue
		if not x or not y:
			return False
		q.append(x.left)
		q.append(y.right)
		q.append(x.right)
		q.append(y.left)
	return True


def IsFoldable(root):
	if root is None:
		return True

	def helper(root1, root2):

		def check(r1, r2):
			if r1.left and r1.right:
				if r2.left and r2.right:
					return True
				else:
					return False
			elif r1.left:
				if r2.left is None and r2.right:
					return True
				else:
					return False
			elif r1.right:
				if r2.left and r2.right is None:
					return True
				else:
					return False
			elif r2.left is None and r2.right is None:
				return True
			else:
				return False
		if root1 is None and root2 is None:
			return True
		elif root1 is None or root2 is None:
			return False
		else:
			return check(root1, root2) and helper(root1.left, root2.right) and helper(root1.right, root2.left)
	return helper(root.left, root.right)


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

def IsFoldable(root):
	if root == None:
		return True
	return solve(root.left, root.right)


def IsFoldable(root):

	def traverse(a, b):
		if not a and (not b):
			return True
		elif a and b:
			return traverse(a.right, b.left) and traverse(a.left, b.right)
		else:
			return False
	if not root:
		return True
	return traverse(root.left, root.right)


def IsFoldable(node):
	if node == None:
		return True
	res = helper(node.left, node.right)
	return res

def helper(a, b):
	if a == None and b == None:
		return True
	if a != None and b != None and helper(a.left, b.right) and helper(a.right, b.left):
		return True
	return False


def IsFoldable(node):
	if node == None:
		return True
	res = isStructSame(node.left, node.right)
	mirror(node.left)
	return res

def isStructSame(a, b):
	if a == None and b == None:
		return True
	if a != None and b != None and isStructSame(a.left, b.right) and isStructSame(a.right, b.left):
		return True
	return False

def mirror(node):
	if node == None:
		return
	else:
		mirror(node.left)
		mirror(node.right)
		temp = node.left
		node.left = node.right
		node.right = temp


def IsFoldable(root):

	def helper(a, b):
		if not a and (not b):
			return True
		if not a and b or (not b and a):
			return False
		v1 = helper(a.left, b.right)
		v2 = helper(a.right, b.left)
		return v1 and v2
	return helper(root, root)


def solve(left, right):
	if not left and (not right):
		return True
	if left and (not right) or (not left and right):
		return False
	return solve(left.left, right.right) and solve(left.right, right.left)

def IsFoldable(root):
	if not root:
		return True
	return solve(root.left, root.right)


def IsFoldable(root):

	def Mirror(root):
		if root is None:
			return
		Mirror(root.left)
		Mirror(root.right)
		temp = root.left
		root.left = root.right
		root.right = temp

	def Same(a, b):
		if a is None and b is None:
			return True
		if a is not None and b is not None and Same(a.left, b.left) and Same(a.right, b.right):
			return True
		return False
	if root == None:
		return True
	Mirror(root.left)
	res = Same(root.left, root.right)
	Mirror(root.left)
	return res


def IsFoldable(root):

	def helper(root_left, root_right):
		if not root_left and (not root_right):
			return True
		if not root_left or not root_right:
			return False
		return helper(root_left.left, root_right.right) and helper(root_left.right, root_right.left)
	if not root:
		return True
	return helper(root.left, root.right)


def IsFoldable(root):

	def helper(root_left, root_right):
		if not root_left and (not root_right):
			return True
		if not root_left or not root_right:
			return False
		l = helper(root_left.left, root_right.right)
		r = helper(root_left.right, root_right.left)
		return l and r
	if not root:
		return True
	flag = helper(root.left, root.right)
	return flag


def IsFoldable(root):
	res = []
	queue = [root]
	while queue:
		level = []
		vals = []
		for i in queue:
			if i == None:
				vals.append('None')
				continue
			vals.append('VALUE')
			level.append(i.left)
			level.append(i.right)
		queue = level
		res.append(vals)
	for i in res:
		if i != i[::-1]:
			return False
	return True


def IsFoldable(root):

	def inorder_path(node, acc):
		if node.left:
			inorder_path(node.left, acc)
			acc.append(0)
		if node.right:
			inorder_path(node.right, acc)
			acc.append(1)

	def reversed_inorder_path(node, acc):
		if node.right:
			reversed_inorder_path(node.right, acc)
			acc.append(0)
		if node.left:
			reversed_inorder_path(node.left, acc)
			acc.append(1)
	if root is None:
		return True
	if root.left is None or root.right is None:
		if root.left is None and root.right is None:
			return True
		else:
			return False
	acc_left = []
	acc_right = []
	inorder_path(root.left, acc_left)
	reversed_inorder_path(root.right, acc_right)
	return acc_left == acc_right


def IsFoldable(root):
	hashmap = {}
	Q = []
	if root == None:
		return True
	if root.left == None and root.right == None:
		return True
	Q.append([root, 0])
	while len(Q) != 0:
		it = Q[0][0]
		lev = Q[0][1]
		Q.pop(0)
		if lev in hashmap:
			hashmap[lev] += 1
		else:
			hashmap[lev] = 1
		if it and it.left:
			Q.append([it.left, lev - 1])
		if it and it.right:
			Q.append([it.right, lev + 1])
	if hashmap[0] % 2 != 0:
		for i in range(1, len(hashmap) // 2 + 1):
			try:
				if hashmap[i] != hashmap[-i]:
					return False
			except:
				return False
	else:
		return False
	return True


def IsFoldable(root):
	if not root:
		return True

	def sol(left, right):
		if not left and (not right):
			return 1
		if not left or not right:
			return 0
		return sol(left.right, right.left) and sol(left.left, right.right)
	if sol(root.left, root.right):
		return True
	return False


def utils(r1, r2):
	if r1 is None and r2 is None:
		return True
	if r1 is not None and r2 is not None and utils(r1.left, r2.right) and utils(r1.right, r2.left):
		return True
	return False

def IsFoldable(root):
	if root is None:
		return True
	if root.right is not None and root.left is None:
		return False
	if root.right is None and root.left is not None:
		return False
	if root.right is None and root.left is None:
		return True
	return utils(root.left, root.right)


import collections as c

def IsFoldable(root):
	if root == None:
		return True

	def p(t1, t2):
		if t1 == None and t2 == None:
			return True
		if t1 == None or t2 == None:
			return False
		return p(t1.left, t2.right) and p(t1.right, t2.left)
	return p(root.left, root.right)


def IsFoldable(root):
	return ans(root, root)

def ans(x, y):
	if x == None and y == None:
		return True
	elif x == None and y != None or (x != None and y == None):
		return False
	return ans(x.left, y.right) and ans(x.right, y.left)


def IsFoldable(root):
	if root == None:
		return True

	def helper(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 = helper(root1.left, root2.right)
		right = helper(root1.right, root2.left)
		return left and right
	return helper(root.left, root.right)


def IsFoldable(root):
	stack = [(root, root)]
	while stack:
		(root, mirror) = stack.pop()
		if root and (not mirror):
			return False
		if mirror and (not root):
			return False
		if not root and (not mirror):
			continue
		stack.append((root.left, mirror.right))
		stack.append((root.right, mirror.left))
	return True


def structure(r1, r2):
	if r1 == r2 == None:
		return 1
	if None in [r1, r2]:
		return 0
	return structure(r1.left, r2.right) * structure(r1.right, r2.left)

def IsFoldable(root):
	if root == None:
		return True
	return bool(structure(root.left, root.right))


def IsFoldable(root):

	def isMirror(t1, t2):
		if t1 == None and t2 == None:
			return True
		if t1 == None or t2 == None:
			return False
		return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
	return isMirror(root, root)


def IsFoldable(root):
	if not root:
		return True
	return isMirror(root.left, root.right)

def isMirror(root1, root2):
	if not root1 and (not root2):
		return True
	if not root1 and root2:
		return False
	if root1 and (not root2):
		return False
	return isMirror(root1.left, root2.right) and isMirror(root1.right, root2.left)


import collections

def IsFoldable(root):
	if not root:
		return True

	def trav(root1, root2):
		q1 = collections.deque([root1])
		q2 = collections.deque([root2])
		while q1 or q2:
			res1 = ''
			l1 = len(q1)
			for _ in range(l1):
				cur = q1.popleft()
				if cur:
					res1 += '$'
				else:
					res1 += '#'
					continue
				q1.append(cur.left)
				q1.append(cur.right)
			res2 = ''
			l2 = len(q2)
			for _ in range(l2):
				cur2 = q2.popleft()
				if cur2:
					res2 += '$'
				else:
					res2 += '#'
					continue
				q2.append(cur2.right)
				q2.append(cur2.left)
			if res1 != res2:
				return False
		return True
	return trav(root.left, root.right)


def IsFoldable(root):
	if not root:
		return True

	def traverse(root1, root2):
		if not root1 or not root2:
			return root1 == root2
		return traverse(root1.left, root2.right) and traverse(root1.right, root2.left)
	return traverse(root.left, root.right)


def IsFoldable(root):

	def solve(a, b):
		if a == None and b == None:
			return True
		if a == None or b == None:
			return False
		return solve(a.left, b.right) and solve(a.right, b.left)
	if root == None:
		return True
	return solve(root.left, root.right)


def IsFoldable(root):

	def traversal(root1, root2):
		if root1 == None and root2 == None:
			return True
		elif root1 != None and root2 != None:
			return traversal(root1.left, root2.right) and traversal(root1.right, root2.left)
		else:
			return False
	return traversal(root, root)


def fold(a, b):
	if a == None and b == None:
		return True
	if a == None or b == None:
		return False
	if a.data != None and b.data != None and (fold(a.left, b.right) == True) and (fold(a.right, b.left) == True):
		return True
	else:
		return False

def IsFoldable(root):
	if root == None:
		return True
	a = root.left
	b = root.right
	return fold(a, b)


def IsFoldableUtil(n1, n2):
	if n1 == None and n2 == None:
		return True
	if n1 == None or n2 == None:
		return False
	d1 = IsFoldableUtil(n1.left, n2.right)
	d2 = IsFoldableUtil(n1.right, n2.left)
	return d1 and d2

def IsFoldable(root):
	if root == None:
		return True
	return IsFoldableUtil(root.left, root.right)


def IsFoldable(root):

	def is_same(p, q):
		if not p and (not q):
			return True
		if not p or not q:
			return False
		return is_same(p.left, q.right) and is_same(p.right, q.left)
	if not root:
		return True
	return is_same(root.left, root.right)


from collections import deque

def IsFoldable(root):
	if not root:
		return True
	q = deque([root])
	while q:
		lvl = []
		for i in range(len(q)):
			node = q.popleft()
			if node:
				lvl.append(1)
				q.append(node.left)
				q.append(node.right)
			else:
				lvl.append(0)
		if lvl != lvl[::-1]:
			return False
	return True


def IsFoldable(root):
	if root is None:
		return True
	return isSimilar(root.left, root.right)

def isSimilar(subtree_one, subtree_two):
	if subtree_one is None and subtree_two is None:
		return True
	if sum((x is None for x in [subtree_one, subtree_two])) % 2 == 1:
		return False
	return isSimilar(subtree_one.left, subtree_two.right) and isSimilar(subtree_one.right, subtree_two.left)


def flipTree(root):
	if not root:
		return
	if root.left or root.right:
		flipTree(root.left)
		flipTree(root.right)
	(root.left, root.right) = (root.right, root.left)

def areBothSame(leftRoot, rightRoot):
	if leftRoot == rightRoot == None:
		return True
	if leftRoot == None or rightRoot == None:
		return False
	return areBothSame(leftRoot.left, rightRoot.left) and areBothSame(leftRoot.right, rightRoot.right)

def IsFoldable(root):
	if not root:
		return True
	(leftRoot, rightRoot) = (root.left, root.right)
	flipTree(rightRoot)
	return areBothSame(leftRoot, rightRoot)


def IsFoldable(root):
	if not root:
		return True

	def dfs(r1, r2):
		if not r1 and (not r2):
			return True
		if not r1 and r2:
			return False
		if r1 and (not r2):
			return False
		return dfs(r1.left, r2.right) and dfs(r1.right, r2.left)
	return dfs(root.left, root.right)


def isMirror(r1, r2):
	if not r1 and (not r2):
		return True
	elif not r1 or not r2:
		return False
	return isMirror(r1.left, r2.right) and isMirror(r1.right, r2.left)

def IsFoldable(root):
	if not root:
		return True
	return isMirror(root.left, root.right)


def is_mirror(left_sub, right_sub):
	if not left_sub and (not right_sub):
		return True
	if not left_sub or not right_sub:
		return False
	outer_side = is_mirror(left_sub.left, right_sub.right)
	inner_side = is_mirror(left_sub.right, right_sub.left)
	if outer_side and inner_side:
		return True
	return False

def IsFoldable(root):
	if not root:
		return True
	return is_mirror(root.left, root.right)


def IsFoldable(root):

	def Compare(Node1, Node2):
		if Node1 == None and Node2 == None:
			return True
		if Node1 == None or Node2 == None:
			return False
		if Node1 and Node2:
			return True and Compare(Node1.left, Node2.right) and Compare(Node1.right, Node2.left)
	if root == None:
		return True
	return Compare(root.left, root.right)


def IsFoldable(root):
	if root is None:
		return True
	return solve(root, root)

def solve(root1, root2):
	if root1 is None:
		return root2 == None
	elif root2 is None:
		return root1 == None
	else:
		return solve(root1.left, root2.right) and solve(root1.right, root2.left)


def check(left, right):
	if not left and (not right):
		return True
	if left and (not right):
		return False
	if right and (not left):
		return False
	return check(left.left, right.right) and check(left.right, right.left)

def IsFoldable(root):
	if not root:
		return True
	return check(root.left, root.right)


def isMirrorStructure(r1, r2):
	if not r1 and (not r2):
		return True
	if not r1 or not r2:
		return False
	return isMirrorStructure(r1.left, r2.right) and isMirrorStructure(r1.right, r2.left)

def IsFoldable(root):
	if not root:
		return True
	return isMirrorStructure(root.left, root.right)


def IsFoldable(root):
	if not root:
		return True
	return symmetric(root.left, root.right)

def symmetric(r1, r2):
	if r1 == None and r2 == None:
		return True
	if r1 == None or r2 == None:
		return False
	return symmetric(r1.left, r2.right) and symmetric(r1.right, r2.left)


def IsFoldable(root):

	def helper(node1, node2):
		if node1 == None or node2 == None:
			return node1 == node2
		else:
			return helper(node1.left, node2.right) and helper(node1.right, node2.left)
	if root == None:
		return True
	return helper(root.left, root.right)


def mirror(root):
	if root == None:
		return
	temp = root.left
	root.left = root.right
	root.right = temp
	mirror(root.left)
	mirror(root.right)

def recur(root1, root2):
	if not root1 and (not root2):
		return True
	if not root1 and root2:
		return False
	if not root2 and root1:
		return False
	if root1 and root2:
		bool1 = root1.left and root2.left or (not root1.left and (not root2.left))
		bool2 = root1.right and root2.right or (not root1.right and (not root2.right))
		if bool1 and bool2:
			x1 = recur(root1.left, root2.left)
			x2 = recur(root1.right, root2.right)
		else:
			return False
	return x1 and x2

def IsFoldable(root):
	if not root:
		return True
	mirror(root.right)
	con = recur(root.left, root.right)
	return con


def IsFoldable(root):
	dic = {}
	lis = []
	if root == None:
		return True

	def fun(root, level, order):
		if root == None:
			return
		if order == 0:
			lis.append(0)
		if level not in dic:
			dic[level] = [order]
		else:
			dic[level].append(order)
		fun(root.left, level + 1, order - 1)
		fun(root.right, level + 1, order + 1)
	fun(root, 0, 0)
	if len(lis) % 2 == 0:
		return False
	for i in dic:
		if sum(dic[i]) != 0:
			return False
	return True


def IsFoldable(root):

	def issame(a, b):
		if a == None and b == None:
			return True
		elif a == None or b == None:
			return False
		issameleft = issame(a.left, b.right)
		issameright = issame(a.right, b.left)
		return issameleft and issameright
	if root == None:
		return True
	return issame(root.left, root.right)


def IsFoldable(root):
	if not root:
		return True
	mirror(root.left)
	res = isStructureSame(root.left, root.right)
	mirror(root.left)
	return res

def mirror(node):
	if not node:
		return
	else:
		mirror(node.left)
		mirror(node.right)
		temp = node.left
		node.left = node.right
		node.right = temp

def isStructureSame(a, b):
	if a is None and b is None:
		return True
	if a is not None and b is not None and isStructureSame(a.left, b.left) and isStructureSame(a.right, b.right):
		return True
	return False


def IsFoldable(root):
	if not root:
		return True

	def fold(root1, root2):
		if not root1 and (not root2):
			return True
		if root1 and (not root2) or (root2 and (not root1)):
			return False
		return fold(root1.left, root2.right) and fold(root1.right, root2.left)
	return fold(root.left, root.right)


from collections import deque

def IsFoldable(root):
	if root:
		return is_foldable(root.left, root.right)
	return True

def is_foldable(tmp1, tmp2):
	if (tmp1 == None) ^ (tmp2 == None):
		return False
	if not (tmp1 and tmp2):
		return True
	return is_foldable(tmp1.left, tmp2.right) and is_foldable(tmp1.right, tmp2.left)


def check(root1, root2):
	if not root1 and (not root2):
		return True
	elif root1 and root2:
		return check(root1.left, root2.right) and check(root1.right, root2.left)
	else:
		return False

def IsFoldable(root):
	if not root:
		return True
	return check(root.left, root.right)


from collections import deque

def IsFoldable(root):
	q = deque()
	if root:
		q.append(root)
		while q:
			n = len(q)
			child = []
			while n:
				tmp = q.popleft()
				child.append(tmp.left)
				child.append(tmp.right)
				if tmp.left:
					q.append(tmp.left)
				if tmp.right:
					q.append(tmp.right)
				n -= 1
			if not is_foldable(child):
				return False
	return True

def is_foldable(array):
	left = 0
	right = len(array) - 1
	while left < right:
		if (array[left] == None) ^ (array[right] == None):
			return False
		left += 1
		right -= 1
	return True


def checkFoldable(left, right):
	if left is None or right is None:
		return left == right
	else:
		return checkFoldable(left.left, right.right) and checkFoldable(left.right, right.left)

def IsFoldable(root):
	if root is None:
		return True
	return checkFoldable(root.left, root.right)


def f(n1, n2):
	if n1 is None and n2 is None:
		return True
	if n1 is None or n2 is None:
		return False
	return f(n1.left, n2.right) & f(n1.right, n2.left)

def IsFoldable(root):
	if root is None:
		return True
	return f(root.left, root.right)


class Node:

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

def IsFoldable(root):
	if root is None:
		return True
	elif root.left == None and root.right == None:
		return True
	else:
		return mirror(root.left, root.right)

def mirror(node1, node2):
	if node1 and (not node2):
		return False
	elif not node1 and node2:
		return False
	elif not node1 and (not node2):
		return True
	else:
		return mirror(node1.left, node2.right) and mirror(node1.right, node2.left)


def IsFoldable(root):
	if not root:
		return True

	def check(l_sub, r_sub):
		if not l_sub and (not r_sub):
			return True
		if not l_sub or not r_sub:
			return False
		return check(l_sub.left, r_sub.right) and check(l_sub.right, r_sub.left)
	return check(root.left, root.right)


def IsFoldable(root):
	if root is None:
		return True

	def isgood(root1, root2):
		if root1 == None and root2 == None:
			return True
		if root1 == None or root2 == None:
			return False
		return isgood(root1.left, root2.right) and isgood(root1.right, root2.left)
	ans = isgood(root.left, root.right)
	return ans


def check(p, q):
	if p == None and q == None:
		return True
	if p == None or q == None:
		return False
	return check(p.left, q.right) and check(p.right, q.left)

def IsFoldable(root):
	if root == None:
		return True
	return check(root.left, root.right)


case1 = True

def isFoldableUtils(root1, root2):
	global case1
	if root1 == None and root2 == None:
		return
	if root1 == None and root2 != None or (root2 == None and root1 != None):
		case1 = False
		return
	if root2.left == None and root1.right != None or (root2.left != None and root1.right == None):
		case1 = False
		return
	if root1.left != None and root2.right == None or (root1.left == None and root2.right != None):
		case1 = False
		return
	isFoldableUtils(root1.left, root2.right)
	isFoldableUtils(root1.right, root2.left)

def IsFoldable(root):
	global case1
	case1 = True
	if root == None:
		return True
	isFoldableUtils(root.left, root.right)
	return case1


from collections import deque

def IsFoldable(root):
	if root == None:
		return True
	else:
		return check(root.left, root.right)

def check(left, right):
	if left != None and right != None:
		if check(left.left, right.right) and check(left.right, right.left):
			return True
		else:
			return False
	elif left == None and right == None:
		return True
	else:
		return False


from collections import deque

def IsFoldable(root):
	if not root:
		return True

	def bfs(root):
		queue = deque()
		queue.append(root.left)
		queue.append(root.right)
		while queue:
			p = queue.popleft()
			q = queue.popleft()
			if not p and (not q):
				continue
			if not p or not q:
				return False
			queue.append(p.left)
			queue.append(q.right)
			queue.append(p.right)
			queue.append(q.left)
		return True
	return bfs(root)


def gs(r):
	m = ''
	if r is not None:
		q = [r]
	else:
		q = []
	c = 0
	while c != len(q):
		t = q[c]
		m += 'N'
		if t.left:
			m += 'L'
			q.append(t.left)
		if t.right:
			q.append(t.right)
			m += 'R'
		c += 1
	return m

def IsFoldable(root):
	if root is None:
		return True
	a = gs(root.left)
	b = gs(root.right)
	a = a.replace('LR', '')
	b = b.replace('LR', '')
	a = a.replace('L', '*')
	a = a.replace('R', 'L')
	a = a.replace('*', 'R')
	return a == b


def ifFoldable(l, r):
	if l is None or r is None:
		return l == r
	if l is not None and r is not None:
		return ifFoldable(l.left, r.right) and ifFoldable(l.right, r.left)

def IsFoldable(root):
	if root is None:
		return True
	l = root.left
	r = root.right
	return ifFoldable(l, r)


def IsFoldable(root):
	if not root:
		return True
	return IsFoldableAux(root.left, root.right)

def IsFoldableAux(left, right):
	if not left and (not right):
		return True
	if left and right:
		return IsFoldableAux(left.right, right.left) and IsFoldableAux(left.left, right.right)
	return False


from collections import deque

def IsFoldable(root):

	def isPalindrome(a):
		ll = len(a)
		(l, r) = (0, ll - 1)
		while l < r:
			if a[l] != a[r]:
				return False
			l += 1
			r -= 1
		return True
	q = deque()
	q.append(root)
	while q:
		ll = len(q)
		level = []
		for _ in range(ll):
			node = q.popleft()
			if node:
				level.append('V')
			else:
				level.append('N')
			if node:
				if node.left:
					q.append(node.left)
				else:
					q.append(None)
				if node.right:
					q.append(node.right)
				else:
					q.append(None)
		if not isPalindrome(level):
			return False
	return True


def IsFoldable(root, lnode=None, rnode=None, first=True):
	if not root:
		return True
	if first:
		lnode = root.left
		rnode = root.right
		first = False
	if not lnode and (not rnode):
		return True
	if not (lnode and rnode):
		return False
	return IsFoldable(root, lnode.left, rnode.right, first) and IsFoldable(root, lnode.right, rnode.left, first)


def IsFoldable(root):
	pathLeft = traverseTreeLeft(root)
	pathRight = traverseTreeRight(root)
	return pathLeft == pathRight

def traverseTreeLeft(node, directionFromParent=0):
	result = []
	if not node:
		return result
	if node.left:
		result.extend(traverseTreeLeft(node.left, 0))
	result.append(directionFromParent)
	if node.right:
		result.extend(traverseTreeLeft(node.right, 1))
	return result

def traverseTreeRight(node, directionFromParent=0):
	result = []
	if not node:
		return result
	if node.right:
		result.extend(traverseTreeRight(node.right, 0))
	result.append(directionFromParent)
	if node.left:
		result.extend(traverseTreeRight(node.left, 1))
	return result


from collections import deque

def IsFoldable(root):
	if root == None:
		return True
	return rec(root.left, root.right)

def rec(p, q):
	if p == None and q == None:
		return True
	if p == None or q == None:
		return False
	return rec(p.left, q.right) and rec(p.right, q.left)


def mirror(root):
	if not root:
		return False
	mirror(root.left)
	mirror(root.right)
	(root.left, root.right) = (root.right, root.left)
	return root

def isSamestruct(left, right):
	if not left and (not right):
		return True
	if not left or not right:
		return False
	return isSamestruct(left.left, right.left) and isSamestruct(left.right, right.right)

def IsFoldable(root):
	if not root:
		return True
	mirror(root.left)
	res = isSamestruct(root.left, root.right)
	mirror(root.left)
	return res


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

def IsFoldable(root):
	if root == None:
		return True
	return checkMirror(root, root)