Given two binary trees with same number of nodes, the task is to check if each of their levels are anagrams of each other or not. 
Example 1:
Input:
Output: 1
Explanation: 
Tree 1:
Level 0 : 1
Level 1 : 3, 2
Level 2 : 5, 4
Tree 2:
Level 0 : 1
Level 1 : 2, 3
Level 2 : 4, 5
As we can clearly see all the levels of above two binary trees 
are anagrams of each other, hence return true.
Example 2:
Input:
Output: 0
Explanation: 
Tree 1:
Level 0 : 1
Level 1 : 2, 3 
Level 2 : 5, 4 
Tree 2: 
Level 0 : 1 
Level 1 : 2, 4 
Level 2 : 5, 3 
As we can clearly see that level 1 and leve 2 are not anagrams of each other, hence return false.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function areAnagrams() which takes the root of two trees as input and returns an 1 if all the levels are anagrams, else returns 0 as output.
 
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{4}
1 <= tree.val <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Starter code: from typing import Optional

from collections import deque

"""



definition of binary tree node.

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

"""



class Solution:

    def areAnagrams(self, node1 : Optional['Node'], node2 : Optional['Node']) -> bool:

        # code here

        



Solutions:
from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def bfs(root):
			q = deque()
			q.append(root)
			list1 = []
			while q:
				s = []
				for i in range(len(q)):
					pop = q.popleft()
					s.append(pop.data)
					if pop.left:
						q.append(pop.left)
					if pop.right:
						q.append(pop.right)
				list1.append(s)
			return list1
		p1 = bfs(node1)
		p2 = bfs(node2)
		if len(p1) != len(p2):
			return 0
		for i in range(len(p1)):
			if sorted(p1[i]) != sorted(p2[i]):
				return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		dic1 = {}
		dic2 = {}
		max_level = [0] * 1

		def fun(node, level, dic1):
			if node == None:
				return
			max_level[0] = max(max_level[0], level)
			if level not in dic1:
				dic1[level] = [node.data]
			else:
				dic1[level].append(node.data)
			fun(node.left, level + 1, dic1)
			fun(node.right, level + 1, dic1)
		fun(node1, 0, dic1)
		fun(node2, 0, dic2)
		flag = True
		for i in range(max_level[0]):
			dic1[i].sort()
			dic2[i].sort()
			flag = False
			n = len(dic1[i])
			m = len(dic2[i])
			if n != m:
				return False
			for j in range(n):
				if dic1[i][j] != dic2[i][j]:
					return False
		if flag:
			if dic1[0][0] != dic2[0][0]:
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def helper(self, root):
		P = []
		Q = deque()
		Q.append(root)
		while Q:
			n = len(Q)
			S = []
			for i in range(n):
				a = Q.popleft()
				S.append(a.data)
				if a.left:
					Q.append(a.left)
				if a.right:
					Q.append(a.right)
			P.append(S)
		return P

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		P1 = self.helper(node1)
		P2 = self.helper(node2)
		if len(P1) != len(P2):
			return 0
		for i in range(len(P1)):
			if sorted(P1[i]) != sorted(P2[i]):
				return 0
		return 1


from typing import Optional
from collections import deque

class Node:

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

class Sol:

	def __init__(self):
		self.l = []
		self.node = []
		self.res = []
		self.nextnode = []

	def levelOrder(self, root):
		if root == None:
			return []
		self.node.append(root)
		while self.node != []:
			for x in self.node:
				self.l.append(x.data)
				if x.left != None:
					self.nextnode.append(x.left)
				if x.right != None:
					self.nextnode.append(x.right)
			self.node = self.nextnode
			self.nextnode = []
			self.res.append(self.l)
			self.l = []
		return self.res

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		obj = Sol()
		obj2 = Sol()
		res1 = obj.levelOrder(node1)
		res2 = obj2.levelOrder(node2)
		n1 = len(res1)
		n2 = len(res2)
		if n1 != n2:
			return 0
		for i in range(n1):
			if set(res1[i]) != set(res2[i]):
				return 0
		return 1


from typing import Optional
from collections import deque

class Node:

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

def check_anagram(tree_1: Node, tree_2: Node):
	level_map = {}
	queue_1 = [tree_1]
	queue_2 = [tree_2]
	while len(queue_1) > 0 and len(queue_2) > 0:
		n1 = len(queue_1)
		n2 = len(queue_2)
		if n1 != n2:
			return False
		if n1 == 0:
			return False
		if n2 == 0:
			return False
		for i in range(n1):
			element_pop = queue_1.pop(0)
			if element_pop.data in level_map:
				level_map[element_pop.data] = level_map[element_pop.data] + 1
			else:
				level_map[element_pop.data] = 1
			if element_pop.left is not None:
				queue_1.append(element_pop.left)
			if element_pop.right is not None:
				queue_1.append(element_pop.right)
		for i in range(n2):
			element_pop = queue_2.pop(0)
			if element_pop.data not in level_map:
				return False
			level_map[element_pop.data] = level_map[element_pop.data] - 1
			if level_map[element_pop.data] == 0:
				del level_map[element_pop.data]
			if element_pop.left is not None:
				queue_2.append(element_pop.left)
			if element_pop.right is not None:
				queue_2.append(element_pop.right)
		if len(level_map) != 0:
			return False
	if len(queue_1) != 0 or len(queue_2) != 0:
		return False
	return True

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		return check_anagram(node1, node2)


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		mp = {}
		qu = [node1]
		level = 1
		while len(qu):
			n = len(qu)
			mp[level] = {}
			while n:
				top = qu.pop(0)
				if top.data not in mp[level]:
					mp[level][top.data] = 1
				else:
					mp[level][top.data] += 1
				if top.left:
					qu.append(top.left)
				if top.right:
					qu.append(top.right)
				n -= 1
			level += 1
		qu = [node2]
		level = 1
		while len(qu):
			n = len(qu)
			while n:
				top = qu.pop(0)
				if top.data not in mp[level]:
					return False
				elif mp[level][top.data] <= 0:
					return False
				else:
					mp[level][top.data] -= 1
				if top.left:
					qu.append(top.left)
				if top.right:
					qu.append(top.right)
				n -= 1
			for (key, val) in mp[level].items():
				if val > 0:
					return False
			level += 1
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		if node1 == None and node2 == None:
			return True
		if node1 == None or node2 == None:
			return False
		q1 = []
		q2 = []
		q1.append(node1)
		q2.append(node2)
		while 1:
			n1 = len(q1)
			n2 = len(q2)
			if n1 != n2:
				return False
			if n1 == 0:
				break
			cl1 = []
			cl2 = []
			while n1 > 0:
				x = q1.pop(0)
				cl1.append(x.data)
				if x.left != None:
					q1.append(x.left)
				if x.right != None:
					q1.append(x.right)
				x = q2.pop(0)
				cl2.append(x.data)
				if x.left != None:
					q2.append(x.left)
				if x.right != None:
					q2.append(x.right)
				n1 -= 1
			cl1.sort()
			cl2.sort()
			if cl1 != cl2:
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, root1: Optional['Node'], root2: Optional['Node']) -> bool:
		if root1 == None and root2 == None:
			return True
		if root1 == None or root2 == None:
			return False
		q1 = deque()
		q2 = deque()
		q1.append(root1)
		q2.append(root2)
		while True:
			n1 = len(q1)
			n2 = len(q2)
			if n1 != n2:
				return False
			if n1 == 0:
				break
			cur_level1 = []
			cur_level2 = []
			while n1 > 0:
				node1 = q1.popleft()
				if node1.left != None:
					q1.append(node1.left)
				if node1.right != None:
					q1.append(node1.right)
				n1 -= 1
				node2 = q2.popleft()
				if node2.left != None:
					q2.append(node2.left)
				if node2.right != None:
					q2.append(node2.right)
				cur_level1.append(node1.data)
				cur_level2.append(node2.data)
			cur_level1.sort()
			cur_level2.sort()
			if cur_level1 != cur_level2:
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def LevelOrder(self, root):
		dq = deque()
		dq.append(root)
		ans = []
		while len(dq) > 0:
			currsize = len(dq)
			nodes = []
			for i in range(currsize):
				temp = dq.popleft()
				nodes.append(temp.data)
				if temp.left != None:
					dq.append(temp.left)
				if temp.right != None:
					dq.append(temp.right)
			nodes.sort()
			ans.append(nodes)
		return ans

	def areAnagrams(self, root1: Optional['Node'], root2: Optional['Node']) -> bool:
		level1 = self.LevelOrder(root1)
		level2 = self.LevelOrder(root2)
		n1 = len(level1)
		n2 = len(level2)
		if n1 != n2:
			return 0
		for i in range(n1):
			m1 = len(level1[i])
			m2 = len(level2[i])
			if m1 != m2:
				return 0
			for j in range(m1):
				if level1[i][j] != level2[i][j]:
					return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def is_anagram(self, l1, l2):
		return sorted(l1) == sorted(l2)

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		t1 = []
		t2 = []
		d1 = [node1]
		d2 = [node2]
		while d1:
			temp = []
			for i in range(len(d1)):
				node = d1.pop(0)
				temp.append(node.data)
				if node.left:
					d1.append(node.left)
				if node.right:
					d1.append(node.right)
			t1.append(temp)
		while d2:
			temp = []
			for i in range(len(d2)):
				node = d2.pop(0)
				temp.append(node.data)
				if node.left:
					d2.append(node.left)
				if node.right:
					d2.append(node.right)
			t2.append(temp)
		if len(t1) != len(t2):
			return 0
		for i in range(len(t1)):
			if self.is_anagram(t1[i], t2[i]) == False:
				return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		from collections import Counter, deque

		def isAnagram(a: list, b: list):
			return Counter(a) == Counter(b)
		stack1 = deque([node1])
		stack2 = deque([node2])
		while stack1 or stack2:
			if len(stack1) != len(stack2):
				return 0
			temp1 = []
			temp2 = []
			for i in range(len(stack1)):
				node1 = stack1.popleft()
				temp1.append(node1.data)
				node2 = stack2.popleft()
				temp2.append(node2.data)
				if node1.left:
					stack1.append(node1.left)
				if node1.right:
					stack1.append(node1.right)
				if node2.left:
					stack2.append(node2.left)
				if node2.right:
					stack2.append(node2.right)
			if not isAnagram(temp1, temp2):
				return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def helper(root):
			q = []
			ans = []
			t = []
			if not root:
				return ans
			q.append(root)
			while q:
				for i in range(len(q)):
					a = q.pop(0)
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t.append(a.data)
				ans.append(t)
				t = []
			return ans
		a = helper(node1)
		b = helper(node2)
		n = len(a)
		m = len(b)
		if n != m:
			return 0
		for i in range(n):
			if sorted(a[i]) != sorted(b[i]):
				return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		root = node1
		stack = [root]
		dic = {}
		x = 0
		while len(stack):
			a = []
			x += 1
			for i in range(len(stack)):
				if stack[i].left:
					a.append(stack[i].left)
					if stack[i].left.data not in dic:
						dic[stack[i].left.data] = [x]
					else:
						dic[stack[i].left.data].append(x)
				if stack[i].right:
					a.append(stack[i].right)
					if stack[i].right.data not in dic:
						dic[stack[i].right.data] = [x]
					else:
						dic[stack[i].right.data].append(x)
			stack = a
		root = node2
		stack = [root]
		if node1.data != node2.data:
			return 0
		y = 0
		while len(stack):
			a = []
			y += 1
			for i in range(len(stack)):
				if stack[i].left:
					a.append(stack[i].left)
					if stack[i].left.data not in dic or dic[stack[i].left.data][0] != y:
						return 0
					else:
						dic[stack[i].left.data].pop(0)
				if stack[i].right:
					a.append(stack[i].right)
					if stack[i].right.data not in dic or dic[stack[i].right.data][0] != y:
						return 0
					else:
						dic[stack[i].right.data].pop(0)
			stack = a
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, root1: Optional['Node'], root2: Optional['Node']) -> bool:
		if root1 == None and root2 == None:
			return True
		if root1 == None or root2 == None:
			return False
		q1 = []
		q2 = []
		q1.append(root1)
		q2.append(root2)
		m = {}
		while len(q1) > 0 and len(q2) > 0:
			n1 = len(q1)
			n2 = len(q2)
			if n1 != n2:
				return False
			if n1 == 0:
				break
			while n1 > 0:
				node1 = q1.pop(0)
				m[node1.data] = m.get(node1.data, 0) + 1
				if node1.left != None:
					q1.append(node1.left)
				if node1.right != None:
					q1.append(node1.right)
				n1 -= 1
			while n2 > 0:
				node2 = q2.pop(0)
				if m.get(node2.data, 0) == 0:
					return False
				m[node2.data] = m.get(node2.data, 0) - 1
				if m[node2.data] == 0:
					m.pop(node2.data)
				if node2.left != None:
					q2.append(node2.left)
				if node2.right != None:
					q2.append(node2.right)
				n2 -= 1
			if len(m) > 0:
				return False
		if len(q1) == 0 and len(q2) == 0:
			return True
		return False


from typing import Optional
from collections import deque

class Solution:

	def tra(self, root, d, l=0):
		if root == None:
			return None
		if d.get(l) == None:
			d[l] = []
		d[l].append(root.data)
		self.tra(root.left, d, l + 1)
		self.tra(root.right, d, l + 1)

	def areAnagrams(self, n1: Optional['Node'], n2: Optional['Node']) -> bool:
		done = dict()
		self.tra(n1, done)
		dtwo = dict()
		self.tra(n2, dtwo)
		if max(done.keys()) != max(dtwo.keys()):
			return 0
		for x in done.keys():
			l1 = done[x]
			l2 = dtwo[x]
			if sorted(l1) != sorted(l2):
				return 0
		return 1


from typing import Optional
from collections import deque, defaultdict

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		q1 = deque([[node1]])
		q2 = deque([[node2]])
		while q1 and q2:
			(l1, l2) = (q1.popleft(), q2.popleft())
			if len(l1) != len(l2):
				return 0
			f = {}
			nlevel1 = []
			nlevel2 = []
			for i in range(len(l1)):
				f[l1[i].data] = f.get(l1[i].data, 0) + 1
				if l1[i].left:
					nlevel1.append(l1[i].left)
				if l1[i].right:
					nlevel1.append(l1[i].right)
			if nlevel1:
				q1.append(nlevel1)
			for i in range(len(l2)):
				if l2[i].data not in f:
					return 0
				f[l2[i].data] -= 1
				if f[l2[i].data] == 0:
					f.pop(l2[i].data)
				if l2[i].left:
					nlevel2.append(l2[i].left)
				if l2[i].right:
					nlevel2.append(l2[i].right)
			if nlevel2:
				q2.append(nlevel2)
			if f:
				return 0
		return 1


from typing import Optional
from collections import deque, defaultdict

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def bfs(root):
			levelOrder = []
			q = deque([[root]])
			while q:
				front = q.popleft()
				currentLevel = set()
				nlevel = []
				for i in range(len(front)):
					currentLevel.add(front[i].data)
					if front[i].left:
						nlevel.append(front[i].left)
					if front[i].right:
						nlevel.append(front[i].right)
				levelOrder.append(currentLevel)
				if nlevel:
					q.append(nlevel)
			return levelOrder
		bfs1 = bfs(node1)
		bfs2 = bfs(node2)
		return 1 if bfs1 == bfs2 else 0


from typing import Optional
from collections import deque

def isAnagram(l1, l2):
	(m, n) = (len(l1), len(l2))
	if m != n:
		return False
	freq = {}
	for d in l1:
		if d not in freq:
			freq[d] = 1
		else:
			freq[d] += 1
	for d in l2:
		if d not in freq or freq[d] < 1:
			return False
		else:
			freq[d] -= 1
	return True

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		(Q1, Q2) = (deque(), deque())
		Q1.append([node1, 0])
		Q2.append([node2, 0])
		currD = -1
		(l1, l2) = ([], [])
		while Q1 and Q2:
			(ptr1, d1) = Q1.popleft()
			(ptr2, d2) = Q2.popleft()
			if d1 != d2:
				return False
			if d1 != currD:
				if isAnagram(l1, l2) == False:
					return False
				currD = d1
				(l1, l2) = ([], [])
			l1.append(ptr1.data)
			l2.append(ptr2.data)
			if ptr1.left:
				Q1.append([ptr1.left, d1 + 1])
			if ptr1.right:
				Q1.append([ptr1.right, d1 + 1])
			if ptr2.left:
				Q2.append([ptr2.left, d2 + 1])
			if ptr2.right:
				Q2.append([ptr2.right, d2 + 1])
		if Q1 or Q2:
			return False
		else:
			return isAnagram(l1, l2)


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		(r1, r2) = (self.helper(node1), self.helper(node2))
		return self.toAnagram(r1, r2)

	def toAnagram(self, r1, r2):
		for lev in r1:
			if lev not in r2:
				return False
			(t1, t2) = ({}, {})
			for data in r1[lev]:
				if data not in t1:
					t1[data] = 1
				else:
					t1[data] += 1
			for data in r2[lev]:
				if data not in t2:
					t2[data] = 1
				else:
					t2[data] += 1
			for a in t1:
				if a not in t2:
					return False
				elif t2[a] != t1[a]:
					return False
		return True

	def helper(self, node):
		levels = {}
		level = 0
		res = {level: [node.data]}
		stack = [node]
		levels[node] = level
		while stack:
			top = stack.pop()
			if top.left:
				stack.append(top.left)
				levels[top.left] = levels[top] + 1
				lev = levels[top.left]
				if lev not in res:
					res[lev] = [top.left.data]
				else:
					res[lev].append(top.left.data)
			if top.right:
				stack.append(top.right)
				levels[top.right] = levels[top] + 1
				lev = levels[top.right]
				if lev not in res:
					res[lev] = [top.right.data]
				else:
					res[lev].append(top.right.data)
		return res


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		qleft = deque([node1])
		qright = deque([node2])
		(n1, n2) = (1, 1)
		if len(qleft) != len(qright):
			return 0
		while qleft and qright:
			(n1, n2) = (len(qleft), len(qright))
			if n1 != n2:
				return False
			(left, right) = (deque([]), deque([]))
			tl = set()
			tr = set()
			while qleft:
				l = qleft.popleft()
				left.append(l)
				if l:
					tl.add(l.data)
			while qright:
				r = qright.pop()
				right.append(r)
				if r:
					if r.data not in tl:
						return 0
					tr.add(r.data)
			if len(tl) != len(tr):
				return 0
			while left:
				node = left.popleft()
				lf = node.left if node else None
				rt = node.right if node else None
				if lf:
					qleft.append(lf)
				if rt:
					qleft.append(rt)
			while right:
				node = right.pop()
				lf = node.left if node else None
				rt = node.right if node else None
				if lf:
					qright.append(lf)
				if rt:
					qright.append(rt)
		if qleft or qright:
			return 0
		else:
			return 1


from typing import Optional
from collections import deque

class Solution:

	def levelOrderTraversal(self, node, l, d):
		if not node:
			return
		if not d.get(l):
			d[l] = []
		d[l].append(node.data)
		self.levelOrderTraversal(node.left, l + 1, d)
		self.levelOrderTraversal(node.right, l + 1, d)

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		(d1, d2) = ({}, {})
		self.levelOrderTraversal(node1, 0, d1)
		self.levelOrderTraversal(node2, 0, d2)
		for i in d1:
			if i not in d2:
				return False
			if sorted(d1[i]) != sorted(d2[i]):
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def addDataToMap(self, hashmap, root):
		q = deque()
		q.append((root, 0))
		while q:
			n = len(q)
			for i in range(n):
				(node, level) = q.popleft()
				if level not in hashmap:
					hashmap[level] = set([node.data])
				else:
					hashmap[level].add(node.data)
				if node.left:
					q.append((node.left, level + 1))
				if node.right:
					q.append((node.right, level + 1))

	def checkAnagram(self, hashmap, root):
		q = deque()
		q.append((root, 0))
		while q:
			n = len(q)
			for i in range(n):
				(node, level) = q.popleft()
				if level not in hashmap or node.data not in hashmap[level]:
					return False
				if node.left:
					q.append((node.left, level + 1))
				if node.right:
					q.append((node.right, level + 1))
		return True

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		hashmap = {}
		self.addDataToMap(hashmap, node1)
		return self.checkAnagram(hashmap, node2)


from typing import Optional
from collections import deque

class Solution:

	def get_values(self, node, lvl, vals):
		if node is None:
			return
		if lvl not in vals:
			vals[lvl] = []
		vals[lvl].append(node.data)
		self.get_values(node.left, lvl + 1, vals)
		self.get_values(node.right, lvl + 1, vals)
		return

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		(vals1, vals2) = ({}, {})
		self.get_values(node1, 0, vals1)
		self.get_values(node2, 0, vals2)
		if len(vals1) != len(vals2):
			return 0
		for lvl in vals1:
			for (a, b) in zip(sorted(vals1[lvl]), sorted(vals2[lvl])):
				if a != b:
					return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		dicti = {}

		def dfs(node, h, num):
			if node == None:
				return
			if h in dicti.keys():
				if node.data in dicti[h]:
					if num == 1:
						dicti[h][node.data][0] += 1
					else:
						dicti[h][node.data][1] += 1
				elif num == 1:
					dicti[h][node.data] = [1, 0]
				else:
					dicti[h][node.data] = [0, 1]
			else:
				dicti[h] = {}
				if num == 1:
					dicti[h][node.data] = [1, 0]
				else:
					dicti[h][node.data] = [0, 1]
			dfs(node.left, h + 1, num)
			dfs(node.right, h + 1, num)
		dfs(node1, 0, 1)
		dfs(node2, 0, 2)
		for h in dicti.keys():
			for val in dicti[h]:
				if dicti[h][val][0] != dicti[h][val][1]:
					return 0
		return 1


from typing import Optional
from collections import deque, defaultdict

class Solution:

	def areAnagrams(self, node1, node2) -> bool:
		freqs1 = []
		dfs(node1, 0, freqs1)
		freqs2 = []
		dfs(node2, 0, freqs2)
		return freqs1 == freqs2

def dfs(n, l, freqs):
	if not n:
		return
	if len(freqs) == l:
		freqs.append(defaultdict(int))
	freqs[l][n.data] += 1
	dfs(n.left, l + 1, freqs)
	dfs(n.right, l + 1, freqs)


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		q1 = [node1]
		q2 = [node2]
		while q1 and q2:
			n1 = len(q1)
			n2 = len(q2)
			l1 = []
			l2 = []
			if n1 != n2:
				return False
			for i in range(n1):
				node1 = q1[0]
				del q1[0]
				node2 = q2[0]
				del q2[0]
				if node1:
					if node1.left:
						q1.append(node1.left)
					if node1.right:
						q1.append(node1.right)
					l1.append(node1.data)
				if node2:
					if node2.left:
						q2.append(node2.left)
					if node2.right:
						q2.append(node2.right)
					l2.append(node2.data)
			if sorted(l1) != sorted(l2):
				return False
		if q1 or q2:
			return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		level = dict()
		q = list()
		level[0] = [node1.data]
		q.append([0, node1])
		while q:
			cur = q.pop(0)
			level[cur[0]] = [cur[1].data] + level.get(cur[0], [])
			if cur[1].left:
				q.append([cur[0] + 1, cur[1].left])
			if cur[1].right:
				q.append([cur[0] + 1, cur[1].right])
		q = list()
		q.append([0, node2])
		while q:
			cur = q.pop(0)
			if not level.get(cur[0]):
				return False
			if cur[1].data not in level.get(cur[0]):
				return False
			if cur[1].left:
				q.append([cur[0] + 1, cur[1].left])
			if cur[1].right:
				q.append([cur[0] + 1, cur[1].right])
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def height(root):
			if root == None:
				return 0
			lh = height(root.left)
			rh = height(root.right)
			return max(lh, rh) + 1
		tall1 = height(node1)
		tall2 = height(node2)
		if tall1 != tall2:
			return False

		def traversal(root, level, arr):
			if root == None:
				return None
			if level == 0:
				arr.append(root.data)
			else:
				traversal(root.left, level - 1, arr)
				traversal(root.right, level - 1, arr)
		arr1 = []
		arr2 = []
		for i in range(tall1):
			traversal(node1, i, arr1)
			traversal(node2, i, arr2)
			if sorted(arr1) != sorted(arr2):
				return False
			(arr1, arr2) = ([], [])
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		map1 = self.BFS(node1)
		map2 = self.BFS(node2)
		if map1.keys() != map2.keys():
			return False
		for lvl in map1:
			if map1[lvl] != map2[lvl]:
				return False
		return True

	def BFS(self, root):
		queue = deque()
		queue.append((0, root))
		map = {}
		while queue:
			(lvl, top) = queue.popleft()
			if lvl not in map:
				map[lvl] = set([top.data])
			map[lvl].add(top.data)
			if top.left:
				queue.append((lvl + 1, top.left))
			if top.right:
				queue.append((lvl + 1, top.right))
		return map


from typing import Optional
from collections import deque, defaultdict

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def getlevelwise(root):
			q = deque()
			q.append((root, 0))
			d = defaultdict(set)
			while q:
				nc = len(q)
				while nc > 0:
					(node, x) = q.popleft()
					d[x].add(node.data)
					if node.left:
						q.append((node.left, x + 1))
					if node.right:
						q.append((node.right, x + 1))
					nc -= 1
			return d
		d = getlevelwise(node1)
		q = deque()
		q.append((node2, 0))
		while q:
			nc = len(q)
			while nc > 0:
				(node, x) = q.popleft()
				if node.data in d[x]:
					d[x].remove(node.data)
				if node.left:
					q.append((node.left, x + 1))
				if node.right:
					q.append((node.right, x + 1))
				nc -= 1
		for v in d.values():
			if len(v) != 0:
				return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def solve(self, root, l):
		q = [root]
		while q:
			tmp = []
			t = len(q)
			while t:
				s = q.pop(0)
				if s.left:
					q.append(s.left)
				if s.right:
					q.append(s.right)
				tmp.append(s.data)
				t -= 1
			l.append(sorted(tmp))

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		(l, t) = ([], [])
		self.solve(node1, l)
		self.solve(node2, t)
		if l == t:
			return 1
		return 0


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		q1 = [node1]
		q2 = [node2]

		def buildTree(q):
			t = []
			while q:
				temp = []
				for _ in range(len(q)):
					node = q.pop(0)
					temp.append(node.data)
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				t.append(temp)
			return t
		t1 = buildTree(q1)
		t2 = buildTree(q2)
		if len(t1) != len(t2):
			return 0
		for i in range(len(t1)):
			if sorted(t1[i]) != sorted(t2[i]):
				return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def level(self, node):
		head = node
		q = [head, None]
		q1 = []
		m = {}
		while len(q) != 0:
			temp = q.pop(0)
			if temp == None:
				if len(q) == 0:
					q1.append(m)
					break
				q1.append(m)
				q.append(None)
				m = {}
				continue
			if temp.data in m:
				m[temp.data] += 1
			else:
				m[temp.data] = 1
			if temp.left != None:
				q.append(temp.left)
			if temp.right != None:
				q.append(temp.right)
		return q1

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		x = self.level(node1)
		y = self.level(node2)
		if len(x) != len(y):
			return 0
		for i in range(len(x)):
			for j in x[i]:
				if j not in y[i] or x[i][j] != y[i][j]:
					return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def __init__(self):
		self.n1 = {}
		self.n2 = {}

	def no1(self, node1, level):
		if node1 != None:
			if level in self.n1:
				self.n1[level].append(node1.data)
			else:
				self.n1[level] = [node1.data]
			self.no1(node1.left, level + 1)
			self.no1(node1.right, level + 1)

	def no2(self, node2, level):
		if node2 != None:
			if level in self.n2:
				self.n2[level].append(node2.data)
			else:
				self.n2[level] = [node2.data]
			self.no2(node2.left, level + 1)
			self.no2(node2.right, level + 1)

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		self.no1(node1, 0)
		self.no2(node2, 0)
		for i in self.n1:
			if sorted(self.n1[i]) != sorted(self.n2[i]):
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def levelorder(self, root):
		arr = []
		if root:
			queue = deque([root])
			n = 1
			while n:
				vec = []
				temp = None
				for i in range(n):
					temp = queue.popleft()
					vec.append(temp.data)
					if temp.left:
						queue.append(temp.left)
					if temp.right:
						queue.append(temp.right)
				vec.sort()
				arr.append(vec)
				n = len(queue)
		del queue
		del vec
		return arr

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		tree1 = self.levelorder(node1)
		tree2 = self.levelorder(node2)
		n1 = len(tree1)
		n2 = len(tree2)
		if n1 != n2:
			return False
		for i in range(n1):
			if tree1[i] != tree2[i]:
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		if node1 is None and node2 is None:
			return 1
		if node1 is None or node2 is None:
			return 0
		q1 = deque()
		q2 = deque()
		q1.append(node1)
		q2.append(node2)
		while q1 and q2:
			if len(q1) != len(q2):
				return 0
			c = len(q1)
			lvl1 = []
			lvl2 = []
			while c:
				nd1 = q1.popleft()
				nd2 = q2.popleft()
				if nd1.left:
					q1.append(nd1.left)
				if nd1.right:
					q1.append(nd1.right)
				if nd2.left:
					q2.append(nd2.left)
				if nd2.right:
					q2.append(nd2.right)
				lvl1.append(nd1.data)
				lvl2.append(nd2.data)
				c -= 1
			lvl1.sort()
			lvl2.sort()
			if lvl1 != lvl2:
				return 0
		return 1


from typing import Optional
from collections import deque, defaultdict

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		if node1 is None:
			return node2 is None
		if node2 is None:
			return node1 is None
		(q1, q2) = (deque(), deque())
		q1.append(node1)
		q2.append(node2)
		while len(q1) > 0 and len(q2) > 0:
			(q1Size, q2Size) = (len(q1), len(q2))
			if q1Size != q2Size:
				return False
			(s1, s2) = (set(), set())
			for i in range(q1Size):
				(n1, n2) = (q1.popleft(), q2.popleft())
				s1.add(n1.data)
				s2.add(n2.data)
				if n1.left:
					q1.append(n1.left)
				if n1.right:
					q1.append(n1.right)
				if n2.left:
					q2.append(n2.left)
				if n2.right:
					q2.append(n2.right)
			if s1 != s2:
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def levelorder(root):
			res = []
			q = []
			q.append(root)
			while q:
				length = len(q)
				level = []
				for i in range(length):
					node = q.pop(0)
					if node:
						level.append(node.data)
						q.append(node.left)
						q.append(node.right)
				if level:
					level.sort()
					res.append(level)
			return res
		res1 = levelorder(node1)
		res2 = levelorder(node2)
		for (i, j) in zip(res1, res2):
			if i != j:
				return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		tree1 = self.levels(node1)
		tree2 = self.levels(node2)
		len1 = len(tree1)
		len2 = len(tree2)
		if len1 != len2:
			return False
		for tr in tree1.keys():
			if set(tree1[tr]) - set(tree2[tr]) != set():
				return False
		return True

	def levels(self, intree):
		rawlevel = self.traverse(intree, 1)
		ulevel = dict()
		for each in rawlevel:
			try:
				ulevel[each[1]].append(each[0])
			except KeyError:
				ulevel[each[1]] = [each[0]]
		return ulevel

	def traverse(self, node, level):
		if not node:
			return []
		return [[node.data, level]] + self.traverse(node.left, level + 1) + self.traverse(node.right, level + 1)


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def chk(arr1, arr2):
			if len(arr1) != len(arr2):
				return False
			s = set(arr1)
			for i in arr2:
				if i not in s:
					return False
			return True
		(aq, bq) = (deque(), deque())
		aq.append(node1)
		bq.append(node2)
		if node1.data != node2.data:
			return 0
		while aq and bq:
			l = len(aq)
			(e, r) = ([], [])
			for i in range(l):
				n1 = aq.popleft()
				n2 = bq.popleft()
				if n1.left:
					aq.append(n1.left)
					e.append(n1.left.data)
				if n2.left:
					bq.append(n2.left)
					r.append(n2.left.data)
				if n1.right:
					aq.append(n1.right)
					e.append(n1.right.data)
				if n2.right:
					bq.append(n2.right)
					r.append(n2.right.data)
			if not chk(e, r):
				return 0
		return 1


from typing import Optional
from collections import deque

def anagramchecker(a1, a2):
	if len(a1) != len(a2):
		return False
	for i in range(len(a1)):
		if a1[i] != a2[i]:
			return False
	return True

def bfs(root):
	queue = []
	q2 = []
	queue.append([root, 0])
	while queue:
		p = queue.pop(0)
		q2.append([p[0].data, p[1]])
		if p[0].left:
			queue.append([p[0].left, p[1] + 1])
		if p[0].right:
			queue.append([p[0].right, p[1] + 1])
	return q2

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		a1 = bfs(node1)
		a2 = bfs(node2)
		a1.sort()
		a2.sort()
		return anagramchecker(a1, a2)


from typing import Optional
from collections import deque

class help:

	def __init__(self):
		self.d = {}

	def helper(self, node, level):
		if node == None:
			return
		if level in self.d:
			self.d[level].append(node.data)
		else:
			self.d[level] = [node.data]
		self.helper(node.left, level + 1)
		self.helper(node.right, level + 1)

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		obj1 = help()
		obj2 = help()
		obj1.helper(node1, 0)
		obj2.helper(node2, 0)
		if len(obj1.d.keys()) != len(obj2.d.keys()):
			return 0
		else:
			for i in list(obj1.d.keys()):
				obj1.d[i].sort()
				obj2.d[i].sort()
				if obj1.d[i] != obj2.d[i]:
					return 0
			return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def lot(root):
			q = deque([root])
			arr = []
			while q:
				for i in range(len(q)):
					x = q.popleft()
					arr.append(x.data)
					if x.left:
						q.append(x.left)
					if x.right:
						q.append(x.right)
				arr.append('*')
			return arr
		arr1 = lot(node1)
		arr2 = lot(node2)
		(ans1, ans2) = ([], [])
		s = ''
		for i in range(len(arr1)):
			if arr1[i] == '*':
				ans1.append(s)
				s = ''
			else:
				s += str(arr1[i])
		s = ''
		for i in range(len(arr2)):
			if arr2[i] == '*':
				ans2.append(s)
				s = ''
			else:
				s += str(arr2[i])
		for (i, j) in zip(ans1, ans2):
			if set(i) != set(j) or len(i) != len(j):
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		q1 = deque()
		q2 = deque()
		q1.append(node1)
		q2.append(node2)
		while q1 and q2:
			if len(q1) != len(q2):
				return 0
			values1 = set()
			values2 = set()
			for i in range(len(q1)):
				node1 = q1.popleft()
				node2 = q2.popleft()
				values1.add(node1.data)
				values2.add(node2.data)
				if node1.left:
					q1.append(node1.left)
				if node1.right:
					q1.append(node1.right)
				if node2.left:
					q2.append(node2.left)
				if node2.right:
					q2.append(node2.right)
			if values1 != values2:
				return 0
		if len(q1) != 0 or len(q2) != 0:
			return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		if not node1:
			if node2:
				return False
			return True
		dict1 = {}
		dict2 = {}
		q = [(node1, 0)]
		while q:
			(n, d) = q.pop(0)
			if d not in dict1:
				dict1[d] = []
			dict1[d].append(n.data)
			if n.left:
				q.append((n.left, d + 1))
			if n.right:
				q.append((n.right, d + 1))
		for (k, v) in dict1.items():
			dict1[k] = set(v)
		q = [(node2, 0)]
		while q:
			(n, d) = q.pop(0)
			if d not in dict2:
				dict2[d] = []
			dict2[d].append(n.data)
			if n.left:
				q.append((n.left, d + 1))
			if n.right:
				q.append((n.right, d + 1))
		for (k, v) in dict2.items():
			if k not in dict1 or set(v) != dict1[k]:
				return False
		for (k, v) in dict1.items():
			if k not in dict2:
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		(a, b) = ([node1], [node2])
		(p, q) = (1, 1)
		(x, y) = ([node1.data], [node2.data])
		while p != 0 and q != 0:
			x.sort()
			y.sort()
			if x != y:
				return 0
			(x, y) = ([], [])
			(l1, l2) = (a.copy(), b.copy())
			(a, b) = ([], [])
			for i in range(p):
				if l1[i].left != None:
					x.append(l1[i].left.data)
					a.append(l1[i].left)
				if l1[i].right != None:
					x.append(l1[i].right.data)
					a.append(l1[i].right)
			for i in range(q):
				if l2[i].left != None:
					y.append(l2[i].left.data)
					b.append(l2[i].left)
				if l2[i].right != None:
					y.append(l2[i].right.data)
					b.append(l2[i].right)
			p = len(a)
			q = len(b)
		if p != q:
			return 0
		return 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		l1 = []
		l2 = []

		def lf(r, l):
			q = []
			if r:
				q.append(r)
			while len(q) != 0:
				n = len(q)
				t = []
				while n:
					a = q.pop(0)
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t.append(a.data)
					n -= 1
				l.append(t)
		lf(node1, l1)
		lf(node2, l2)
		for i in range(len(l1)):
			if sorted(l1[i]) != sorted(l2[i]):
				return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		if not node1 and (not node2):
			return True
		if node1.data != node2.data:
			return False
		s1 = s2 = set([node1.data])
		arr1 = [node1]
		arr2 = [node2]
		while s1 and s2:
			t1 = set([])
			t2 = set([])
			arr1t = []
			arr2t = []
			for num in arr1:
				if num.left:
					t1.add(num.left.data)
					arr1t.append(num.left)
				if num.right:
					t1.add(num.right.data)
					arr1t.append(num.right)
			for num in arr2:
				if num.left:
					t2.add(num.left.data)
					arr2t.append(num.left)
				if num.right:
					t2.add(num.right.data)
					arr2t.append(num.right)
			if t1 != t2:
				return False
			s1 = t1.copy()
			s2 = t2.copy()
			arr1 = arr1t.copy()
			arr2 = arr2t.copy()
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		(levelOrder1, levelOrder2) = ({}, {})
		self.traversal(node1, 0, levelOrder1)
		self.traversal(node2, 0, levelOrder2)
		if len(levelOrder1) != len(levelOrder2):
			return 0
		for i in range(len(levelOrder1)):
			if sorted(levelOrder1[i]) != sorted(levelOrder2[i]):
				return 0
		return 1

	def traversal(self, root, count, dict_):
		if root == None:
			return
		if count not in dict_:
			dict_[count] = [root.data]
		else:
			dict_[count].append(root.data)
		self.traversal(root.left, count + 1, dict_)
		self.traversal(root.right, count + 1, dict_)


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		d1 = depth(node1)
		d2 = depth(node2)
		if d1 != d2:
			return 0
		for i in range(1, d1 + 1):
			l1 = printCurrentLevel(node1, i)
			l1.sort()
			l2 = printCurrentLevel(node2, i)
			l2.sort()
			if l1 != l2:
				return 0
		return 1

def printCurrentLevel(root, level):
	n = []
	u = []
	if level == 1:
		if root != None:
			n.append(root.data)
		else:
			n.append(-1)
	elif level > 1:
		if root.left != None:
			u = printCurrentLevel(root.left, level - 1)
		else:
			u = [-1]
		if len(u) != 0:
			n += u
		if root.right != None:
			u = printCurrentLevel(root.right, level - 1)
		else:
			u = [-1]
		if len(u) != 0:
			n += u
	return n

def depth(node):
	if node is None:
		return 0
	else:
		ldepth = depth(node.left)
		rdepth = depth(node.right)
		if ldepth > rdepth:
			return ldepth + 1
		else:
			return rdepth + 1


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:

		def bfs(node):
			queue = [node, None]
			lst = []
			st = set()
			while queue:
				node = queue.pop(0)
				if not node:
					lst.append(st)
					st = set()
					if queue:
						queue.append(None)
				else:
					st.add(node.data)
					if node.left:
						queue.append(node.left)
					if node.right:
						queue.append(node.right)
			return lst
		ls1 = bfs(node1)
		ls2 = bfs(node2)
		if len(ls1) == len(ls2):
			for i in range(len(ls1)):
				if ls1[i] != ls2[i]:
					return False
			return True
		return False


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		if not node1 or not node2:
			return 0
		q1 = deque()
		q2 = deque()
		q1.append(node1)
		q2.append(node2)
		while q1 and q2:
			count_obj = {}
			for i in range(len(q1)):
				current = q1.popleft()
				count_obj[current.data] = 1 + count_obj.get(current.data, 0)
				if current.left:
					q1.append(current.left)
				if current.right:
					q1.append(current.right)
			for j in range(len(q2)):
				current_2 = q2.popleft()
				count = count_obj.get(current_2.data, 0)
				if count == 0:
					return 0
				else:
					count_obj[current_2.data] -= 1
				if current_2.left:
					q2.append(current_2.left)
				if current_2.right:
					q2.append(current_2.right)
			all_vals = count_obj.values()
			if any((i > 0 for i in all_vals)):
				return 0
		if not q1 and (not q2):
			return 1
		else:
			return 0


from typing import Optional
from collections import deque

class Solution:

	def check(self, l, q):
		if len(l) != len(q):
			return False
		n = len(l)
		(a, b) = ([], [])
		for i in l:
			a.append(i.data)
		for i in q:
			b.append(i.data)
		(a, b) = (sorted(a), sorted(b))
		for i in range(n):
			if a[i] != b[i]:
				return False
		return True

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		(q1, q2) = ([node1], [node2])
		while len(q1) != 0 and len(q2) != 0:
			if self.check(q1, q2) == False:
				return False
			(k1, k2) = ([], [])
			for i in q1:
				if i.left != None:
					k1.append(i.left)
				if i.right != None:
					k1.append(i.right)
			for i in q2:
				if i.left != None:
					k2.append(i.left)
				if i.right != None:
					k2.append(i.right)
			(q1, q2) = (k1, k2)
		if len(q1) != 0 or len(q2) != 0:
			return False
		return True


from typing import Optional
from collections import deque

class Solution:

	def areAnagrams(self, node1: Optional['Node'], node2: Optional['Node']) -> bool:
		if node1.data != node2.data:
			return False
		ans = True
		tree1 = [node1]
		tree2 = [node2]
		while tree1 != [] and tree2 != []:
			new_tree1 = []
			new_tree2 = []
			new_tree1_values = []
			new_tree2_values = []
			for i in range(len(tree1)):
				if tree1[i].left != None:
					new_tree1.append(tree1[i].left)
					new_tree1_values.append(tree1[i].left.data)
				if tree1[i].right != None:
					new_tree1.append(tree1[i].right)
					new_tree1_values.append(tree1[i].right.data)
				if tree2[i].left != None:
					new_tree2.append(tree2[i].left)
					new_tree2_values.append(tree2[i].left.data)
				if tree2[i].right != None:
					new_tree2.append(tree2[i].right)
					new_tree2_values.append(tree2[i].right.data)
			new_tree1_values.sort()
			new_tree2_values.sort()
			(tree1, tree2) = (new_tree1, new_tree2)
			if new_tree1_values != new_tree2_values or len(tree1) != len(tree2):
				ans = False
				break
		return ans