Given a Binary Tree, write a function to check whether the given Binary Tree is a prefect Binary Tree or not. A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.
Example 1:
Input: 
          7
      /  \
     4    9
Output: YES
Explanation: 
As the root node 7 has two children and 
two leaf nodes 4 and 9 are at same level 
so it is a perfect binary tree.
Example 2:
Input: 
                   7
              /   \
             3     8
           /   \     \
          2     5     10
        /
       1
Output: NO
Your task:
You don't need to read input or print anything. Your task is to complete the function isPerfect() which takes root node of the tree as input parameter and returns a boolean value.If the tree is a perfect binary tree return true other wise return false.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=T<=10^5
1<=N<=10^5
1<=data of 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.data=val
        self.left=None
        self.right=None
'''
class Solution:
    def isPerfect(self,root):
        #code here

Solutions:
class Solution:

	def isPerfect(self, root):
		if root is None:
			return True
		if root.left is None and root.right is None:
			return True
		if root.left is None or root.right is None:
			return False
		if root.left.left is not None and root.right.right is None:
			return False
		if root.left.left is None and root.right.right is not None:
			return False
		if root.left is not None and root.right is not None:
			return self.isPerfect(root.left) and self.isPerfect(root.right)
		return False


class Solution:

	def isPerfect(self, root):
		if root is None:
			return True
		if root.left is None and root.right is None:
			return True

		def helper(root):
			if root is None:
				return -1
			left = right = -1
			if root.left is None and root.right is None:
				return left + 1
			elif root.left is None or root.right is None:
				return -1
			else:
				left = helper(root.left)
				right = helper(root.right)
				if left == -1 or right == -1:
					return -1
				elif left == right:
					return left + 1
				else:
					return -1
		ansL = helper(root.left)
		ansR = helper(root.right)
		if ansL == -1 or ansR == -1:
			return False
		return ansL == ansR


class Solution:

	def isPerfect(self, root):

		def height(root):
			if not root:
				return 0
			elif root:
				return 1 + max(height(root.right), height(root.left))

		def preorder(root, l):
			if not root:
				return
			else:
				l.append(1)
				preorder(root.left, l)
				preorder(root.right, l)
			return len(l)
		h = height(root)
		l = []
		c = preorder(root, l)
		return 1 if pow(2, h) - 1 == c else 0


class Solution:

	def fun(self, root, level, l):
		if root == None:
			return
		if level >= len(l):
			l.append([])
		if root.left == None and root.right == None:
			l[level].append('R')
			l[level].append(root.data)
		else:
			l[level].append(root.data)
		self.fun(root.left, level + 1, l)
		self.fun(root.right, level + 1, l)

	def fun1(self, root, r1):
		q = []
		q.append(root)
		while len(q):
			t = q.pop()
			if t.left == None and t.right != None:
				r1[0] = 0
				break
			if t.right == None and t.left != None:
				r1[0] = 0
				break
			if t.right:
				q.append(t.right)
			if t.left:
				q.append(t.left)

	def isPerfect(self, root):
		(r1, r2) = ([1], [0])
		if root == None:
			r1[0] = 0
		l = []
		self.fun(root, 0, l)
		self.fun1(root, r1)
		c = 0
		for i in l:
			if 'R' in i:
				c += 1
			if c > 1:
				break
		if c == 1:
			r2[0] = 1
		if r1[0] == 1 and r2[0] == 1:
			return True
		else:
			return False


class Solution:

	def isPerfect(self, root):
		from collections import deque
		q = deque()
		q.append(root)
		while len(q):
			size = len(q)
			isInternal = False
			isLeaf = False
			while size:
				size -= 1
				current = q.popleft()
				if current.left is None and current.right is None:
					isLeaf = True
				if current.left and current.right:
					isInternal = True
					q.append(current.left)
					q.append(current.right)
				elif current.left or current.right:
					return False
				if isInternal and isLeaf:
					return False
		return True


class Solution:

	def getHeight(self, node):
		if node is None:
			return 0
		else:
			return 1 + max(self.getHeight(node.left), self.getHeight(node.right))

	def isPerfect(self, root):
		if root == None:
			return True
		if root.left is None and root.right is None:
			return True
		if root.left is None or root.right is None:
			return False
		if root.left and root.right:
			return self.isPerfect(root.left) and self.isPerfect(root.right) and (self.getHeight(root.left) == self.getHeight(root.right))


class Solution:

	def solve(self, root, l, ans):
		if root == None:
			return
		if root.left == None and root.right != None or (root.left != None and root.right == None):
			self.flag = False
		if root.left == None and root.right == None:
			ans.append(l)
		l += 1
		self.solve(root.left, l, ans)
		self.solve(root.right, l, ans)
		l -= 1

	def isPerfect(self, root):
		self.flag = True
		ans = []
		self.solve(root, 0, ans)
		ans = set(ans)
		if self.flag and len(ans) < 2:
			return True
		return False


class Solution:

	def isPerfect(self, root):
		queue = []
		level = 1
		queue.append(root)
		while queue:
			another = []
			while queue:
				node = queue.pop(0)
				if node.right and (not node.left):
					return False
				elif not node.right and node.left:
					return False
				if node.right:
					another.append(node.right)
				if node.left:
					another.append(node.left)
			queue = another
			n = len(another)
			if n != 2 ** level and n != 0:
				return False
			level += 1
		return True


import collections

class Solution:

	def isPerfect(self, root):
		q = collections.deque()
		q.append(root)
		level = 0
		while q:
			qLen = len(q)
			for i in range(qLen):
				cur = q.popleft()
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
			if qLen != 2 ** level:
				return False
			level += 1
		return True


class Solution:

	def isPerfect(self, root):
		d = self.findADepth(root)
		return self.isPerfectRec(root, d)

	def findADepth(self, node):
		d = 0
		while node != None:
			d += 1
			node = node.left
		return d

	def isPerfectRec(self, root, d, level=0):
		if root == None:
			return True
		if root.left == None and root.right == None:
			return d == level + 1
		if root.left == None or root.right == None:
			return False
		return self.isPerfectRec(root.left, d, level + 1) and self.isPerfectRec(root.right, d, level + 1)


class Solution:
	ans = True

	def get_height(self, node):
		if node is None:
			return 0
		lh = self.get_height(node.left)
		rh = self.get_height(node.right)
		if lh != rh:
			self.ans = False
		return max(lh, rh) + 1

	def isPerfect(self, root):
		self.get_height(root)
		return self.ans


class Solution:

	def __init__(self):
		self.heights = []

	def tree_heights(self, tree):
		if tree is None:
			return 0
		if tree.left is None and tree.right is None:
			return 1
		lh = self.tree_heights(tree.left)
		rh = self.tree_heights(tree.right)
		self.heights.append((lh, rh))
		return lh + 1 if lh > rh else rh + 1

	def isPerfect(self, root):
		self.tree_heights(root)
		for child in self.heights:
			if child[0] != child[1]:
				return False
		return True


import collections

class Solution:

	def isPerfect(self, root):
		res = []
		q = collections.deque()
		q.append(root)
		while q:
			l = []
			for i in range(len(q)):
				x = q.popleft()
				if x:
					l.append(x.data)
					q.append(x.left)
					q.append(x.right)
			if l:
				res.append(l)
		a = []
		for k in res:
			x = len(k)
			a.append(x)
		if len(a) <= 1:
			return True
		else:
			count = 0
			for i in range(1, len(a)):
				if a[i] == 2 ** i:
					count = count + 1
				else:
					return False
			return True


class Solution:

	def isPerfect(self, root):
		A = []
		h = self.height(root)
		self.x(root, A)
		return 2 ** h - 1 == len(A)

	def height(self, root):
		if root is None:
			return 0
		left_height = self.height(root.left)
		right_height = self.height(root.right)
		return 1 + max(left_height, right_height)

	def x(self, root, A):
		if root:
			self.x(root.left, A)
			A.append(root.data)
			self.x(root.right, A)


class Solution:

	def calculateDepth(self, node):
		d = 0
		while node is not None:
			d += 1
			node = node.left
		return d

	def helper(self, root, d, level):
		if root == None:
			return
		if root.left == None and root.right == None:
			return d == level + 1
		if root.left == None and root.right == None:
			return False
		return self.helper(root.left, d, level + 1) and self.helper(root.right, d, level + 1)

	def isPerfect(self, root):
		level = 0
		d = self.calculateDepth(root)
		return self.helper(root, d, level)


class Solution:

	def isPerfect(self, root):
		q = deque()
		q.append(root)
		while len(q) > 0:
			count = len(q)
			leaf = 0
			tempCount = count
			while count > 0:
				num = q.popleft()
				flag = 0
				if num.left != None:
					flag = 1
					q.append(num.left)
				if num.right != None:
					flag += 1
					q.append(num.right)
				if flag == 1:
					return False
				elif flag == 0:
					leaf += 1
				count -= 1
			if leaf != 0 and tempCount != leaf:
				return False
		return True


class Solution:

	def isPerfect(self, root):
		two_p = 1
		q = [root]
		while len(q) != 0:
			if two_p != len(q):
				return False
			for i in range(len(q)):
				node = q.pop(0)
				if node.left != None:
					q.append(node.left)
				if node.right != None:
					q.append(node.right)
			two_p *= 2
		return True


import collections

class Solution:

	def isPerfect(self, root):
		q = collections.deque([root])
		while q:
			lastlevel = not (q[0].left or q[0].right)
			for i in range(len(q)):
				node = q.popleft()
				if not lastlevel:
					if not (node.left and node.right):
						return False
					q.append(node.left)
					q.append(node.right)
				elif node.left or node.right:
					return False
		return True


class Solution:

	def isPerfect(self, root):
		t = 1
		k = 0
		queue = [root]
		level = []
		while queue != [] and root is not None:
			l = []
			for node in queue:
				l.append(node.data)
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			if k > 0:
				if len(l) == 2 * t:
					t = len(l)
				else:
					return False
			queue = level
			level = []
			k += 1
		return True


class Solution:

	def isPerfect(self, root):
		arr = []
		self.myFunc(root, arr, 0)
		for i in range(len(arr) - 1):
			if arr[i] * 2 != arr[i + 1]:
				return False
		return True

	def myFunc(self, root, arr, level):
		if not root:
			return
		if len(arr) == level:
			arr.append(0)
		arr[level] += 1
		level += 1
		self.myFunc(root.left, arr, level)
		self.myFunc(root.right, arr, level)
		return


class Solution:

	def __init__(self):
		self.nodes = []

	def traverse(self, root, level):
		if root is None:
			return
		if level + 1 > len(self.nodes):
			self.nodes.append(0)
		self.nodes[level] += 1
		self.traverse(root.left, level + 1)
		self.traverse(root.right, level + 1)

	def isPerfect(self, root):
		self.traverse(root, 0)
		for (idx, val) in enumerate(self.nodes):
			if 1 << idx != val:
				return False
		return True


class Solution:

	def isPerfect(self, root):

		def helper(root: Node) -> (bool, int):
			if not root:
				return (True, 0)
			(left_f, left_value) = helper(root.left)
			(right_f, right_value) = helper(root.right)
			cur_height = max(left_value, right_value) + 1
			Cur_flag = False
			if left_value == right_value and left_f and right_f:
				Cur_flag = True
			return (Cur_flag, cur_height)
		(flag, val) = helper(root)
		return flag


import collections

class Solution:

	def isPerfect(self, root):
		if not root:
			return
		d = collections.defaultdict(list)
		queue = deque()
		queue.append((root, 0))
		while queue:
			(cur, x) = queue.popleft()
			if x not in d:
				d[x] = [cur.data]
			else:
				d[x].append(cur.data)
			if cur.left:
				queue.append((cur.left, x + 1))
			if cur.right:
				queue.append((cur.right, x + 1))
		for i in range(len(d)):
			if len(d[i]) != 2 ** i:
				return False
		return True


class Solution:

	def isPerfect(self, root):
		arr = [root]
		while arr:
			newArr = []
			noneCnt = 0
			for ele in arr:
				newArr.append(ele.left)
				newArr.append(ele.right)
				noneCnt += int(not newArr[-1]) + int(not newArr[-2])
			if noneCnt == len(newArr):
				return True
			if noneCnt != 0:
				return False
			arr = newArr
		return True


class Solution:

	def isPerfect(self, root):

		def helper(root: Node) -> (bool, int):
			if not root:
				return (True, 0)
			(left_flag, left_height) = helper(root.left)
			(right_flag, right_height) = helper(root.right)
			cur_height = max(left_height, right_height) + 1
			cur_flag = False
			if left_flag and right_flag and (left_height == right_height):
				cur_flag = True
			return (cur_flag, cur_height)
		(res, hight) = helper(root)
		return res


class Solution:

	def isPerfect(self, root):
		dep = self.depth(root)
		return self.perfec(root, dep)

	def perfec(self, root, depth, level=0):
		if root == None:
			return True
		if root.left == None and root.right == None:
			return depth == level + 1
		if root.left == None or root.right == None:
			return False
		return self.perfec(root.left, depth, level + 1) and self.perfec(root.right, depth, level + 1)

	def depth(self, root):
		if root == None:
			return 0
		return 1 + self.depth(root.left)


class Solution:

	def isPerfect(self, root):

		def height(root):
			if root == None:
				return 0
			return 1 + max(height(root.left), height(root.right))

		def check(root, d, level=0):
			if root == None:
				return True
			if root.left == None and root.right == None:
				return d == level + 1
			if root.left == None or root.right == None:
				return False
			return check(root.left, d, level + 1) and check(root.right, d, level + 1)
		d = height(root)
		return check(root, d, 0)


class Solution:

	def isPerfect(self, root):
		d = {}
		level = 0
		self.helper(root, level, d)
		for i in d:
			if len(d[i]) != 2 ** i:
				return False
		return True

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


class Solution:

	def treeHeight(self, root):
		if root == None:
			return 0
		lh = self.treeHeight(root.left)
		rh = self.treeHeight(root.right)
		if lh == -1 or rh == -1:
			return -1
		if lh == rh:
			return lh + 1
		else:
			return -1

	def isPerfect(self, root):
		if self.treeHeight(root) != -1:
			return True
		else:
			return False


class Solution:

	def Height(self, temp):
		if temp is None:
			return 0
		return max(self.Height(temp.left), self.Height(temp.right)) + 1

	def nodeCount(self, temp):
		if temp is None:
			return 0
		return self.nodeCount(temp.left) + self.nodeCount(temp.right) + 1

	def isPerfect(self, root):
		h = self.Height(root)
		nc = self.nodeCount(root)
		summ = 0
		for i in range(h):
			summ += pow(2, i)
		return summ == nc


def CheckPerfectTree(root):
	q = []
	q.append(root)
	flag = 0
	while q:
		size = len(q)
		if size != 0 and flag == 1:
			return False
		while size:
			temp = q[0]
			q.pop(0)
			if temp.left and temp.right:
				if flag == 1:
					return False
				else:
					q.append(temp.left)
					q.append(temp.right)
			elif not temp.left and (not temp.right):
				flag = 1
			elif not temp.left or not temp.right:
				return False
			size -= 1
	return True

class Solution:

	def isPerfect(self, root):
		return CheckPerfectTree(root)


class Solution:

	def isPerfect(self, root):

		def helper(root, k, mp):
			if root:
				if k in mp:
					mp[k] += 1
				else:
					mp[k] = 1
				helper(root.left, k + 1, mp)
				helper(root.right, k + 1, mp)
		mp = {}
		helper(root, 0, mp)
		f = 0
		for i in mp:
			if 2 ** i != mp[i]:
				f = 1
				break
		if f:
			return False
		else:
			return True


class Solution:

	def isPerfect(self, root):
		l = -1

		def per(level, r):
			nonlocal l
			if not r:
				return 1
			if not r.left and (not r.right):
				if l == -1:
					l = level
				elif level != l:
					return 0
			elif not r.left or not r.right:
				return 0
			return per(level + 1, r.left) and per(level + 1, r.right)
		return per(0, root)


class Solution:

	def isPerfect(self, root):

		def helper(x):
			ans = []
			q = []
			t = 0
			if not x:
				return ans
			q.append(x)
			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 += 1
				ans.append(t)
				t = 0
			return ans
		a = helper(root)
		for i in range(len(a) - 1):
			if a[i] * 2 != a[i + 1]:
				return False
		return True


class Solution:

	def isPerfect(self, root):
		global c, p, q, l
		c = 0
		p = 0
		q = 0

		def S(root, level):
			global p, q, c, l
			if not root:
				return 0
			if root.left == None and root.right == None and (c == 0):
				l = level
				c = 1
			elif root.left == None and root.right == None and (c == 1):
				if level != l:
					q = 1
			elif root.left == None or root.right == None:
				p = 1
			S(root.left, level + 1)
			S(root.right, level + 1)
		S(root, 0)
		if p == 0 and q == 0:
			return True
		else:
			return False


class Solution:

	def isPerfect(self, root):
		if root is None:
			return False
		self.res = True
		self.func(root)
		return self.res

	def func(self, root):
		if root is None:
			return -1
		if root.left is None and root.right is None:
			return 1
		elif root.left and root.right is None:
			self.res = False
			return -1
		elif root.left is None and root.right:
			self.res = False
			return -1
		left = self.func(root.left)
		right = self.func(root.right)
		if left == -1 or right == -1:
			return -1
		if left != right:
			self.res = False
			return -1
		return left + right + 1


import math

class Solution:

	def isPerfect(self, root):
		if root is None:
			return True
		height = self.TreeHight(root)
		i = 1
		while i <= height:
			lst = []
			lst = self.LevelOrdertrvsl(root, i, lst)
			if len(lst) != int(math.pow(2, i - 1)):
				return False
			i += 1
		return True

	def LevelOrdertrvsl(self, root, level, lst):
		if root is None:
			return lst
		if level == 1:
			lst.append(root.data)
			return lst
		elif level > 1:
			lst = self.LevelOrdertrvsl(root.left, level - 1, lst)
			lst = self.LevelOrdertrvsl(root.right, level - 1, lst)
		return lst

	def TreeHight(self, root):
		if root is None:
			return 0
		ls = 1 + self.TreeHight(root.left)
		rs = 1 + self.TreeHight(root.right)
		maxh = max(ls, rs)
		return maxh


class Solution:

	def isPerfect(self, root):
		if not root:
			return True
		q = [root]
		j = 0
		while q:
			temp = []
			for i 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)
			if len(temp) != 2 ** j:
				return False
			else:
				j += 1
		return True


class Solution:

	def isPerfect(self, root):

		def dfs(root):
			if not root:
				return 0
			lef = dfs(root.left)
			rig = dfs(root.right)
			if lef == -1 or rig == -1:
				return -1
			if abs(lef - rig) > 0:
				return -1
			return 1 + max(lef, rig)
		return True if dfs(root) != -1 else False


class Solution:

	def dump(self, root, d, level=0):
		if root == None:
			return True
		if root.left is None and root.right is None:
			return d == level + 1
		if root.left == None or root.right == None:
			return False
		return self.dump(root.left, d, level + 1) and self.dump(root.right, d, level + 1)

	def isPerfect(self, root):
		if root == None:
			return True
		k = 0
		curr = root
		while curr:
			k += 1
			curr = curr.left
		return self.dump(root, k)


class Solution:

	def isPerfect(self, root):
		number = self.numberofnode(root)
		height = self.height(root)
		if number == 2 ** height - 1:
			return True

	def height(self, root):
		if root == None:
			return 0
		return 1 + max(self.height(root.left), self.height(root.right))

	def numberofnode(self, root):
		if root == None:
			return 0
		leftnumber = self.numberofnode(root.left)
		rightnumber = self.numberofnode(root.right)
		return 1 + leftnumber + rightnumber


class Solution:

	def isPerfect(self, root):
		q = [root]
		arr = []
		count = 1
		while q:
			arr = q[0:]
			q = []
			if len(arr) != count:
				return False
			for i in range(len(arr)):
				t = arr.pop(0)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
			count *= 2
		return True


class Solution:

	def isPerfect(self, root):
		c = 0
		q = [[root, 0]]
		m = -1
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			if g > m:
				m = g
			if t.left:
				q.append([t.left, g + 1])
			if t.right:
				q.append([t.right, g + 1])
			c += 1
		if c == 2 ** (m + 1) - 1:
			return 1
		return 0


class Solution:

	def isPerfect(self, root):

		def height(root):
			if not root:
				return 0
			return max(height(root.left), height(root.right)) + 1

		def rec(root, height, level):
			if level == height and root.right is None and (root.left is None):
				return True
			if level < height and (not root.right) or not root.left:
				return False
			return rec(root.left, height, level + 1) and rec(root.right, height, level + 1)
		height_tree = height(root)
		return rec(root, height_tree, 1)


class Solution:

	def isPerfect(self, root):
		if not root:
			return False
		queue = []
		queue.append(root)
		level = 0
		n = 0
		res = []
		while queue:
			size = len(queue)
			n = size
			for _ in range(size):
				cur_ele = queue.pop(0)
				if not cur_ele.left and (not cur_ele.right):
					res.append(level)
				if cur_ele.left:
					queue.append(cur_ele.left)
				if cur_ele.right:
					queue.append(cur_ele.right)
			if queue:
				level += 1
		if len(set(res)) != 1:
			return False
		if 2 ** level != n:
			return False
		return True


class Solution:

	def findDepth(self, node):
		d = 0
		while node != None:
			d += 1
			node = node.left
		return d

	def perf(self, root, h, level=0):
		if root == None:
			return True
		if root.left == None and root.right == None:
			return h == level + 1
		if root.left == None or root.right == None:
			return False
		return self.perf(root.left, h, level + 1) and self.perf(root.right, h, level + 1)

	def isPerfect(self, root):
		h = self.findDepth(root)
		return self.perf(root, h)


class Solution:

	def getheight(self, root):
		if not root:
			return 0
		return 1 + max(self.getheight(root.left), self.getheight(root.right))

	def computeperfect(self, root, height, depth):
		if not root.left and (not root.right):
			if depth != height:
				return False
			return True
		if root.left is not None and root.right is not None:
			return self.computeperfect(root.left, height, depth + 1) and self.computeperfect(root.right, height, depth + 1)
		return False

	def isPerfect(self, root):
		height = self.getheight(root)
		return self.computeperfect(root, height, 1)


class Solution:

	def isPerfect(self, root):
		if root == None:
			return True
		q1 = [root]
		q2 = []
		r = 0
		l = 0
		while q1 != [] or q2 != []:
			c = False
			while q1 != []:
				t = q1[0]
				q1.pop(0)
				if t.left:
					q2.append(t.left)
				if t.right:
					q2.append(t.right)
				r += 1
				c = True
			if c:
				l += 1
			c = False
			while q2 != []:
				t = q2[0]
				q2.pop(0)
				if t.left:
					q1.append(t.left)
				if t.right:
					q1.append(t.right)
				r += 1
				c = True
			if c:
				l += 1
		re = pow(2, l) - 1
		if re == r:
			return True
		else:
			return False


class Solution:

	def isPerfect(self, root):
		(is_perfect, height) = self.perfect(root)
		return is_perfect

	def perfect(self, root):
		if root is None:
			return (True, 0)
		(l_is_perfect, l_height) = self.perfect(root.left)
		(r_is_perfect, r_height) = self.perfect(root.right)
		is_perfect = l_is_perfect and r_is_perfect and (l_height == r_height)
		height = 1 + max(l_height, r_height)
		return (is_perfect, height)


class Solution:

	def Depth(self, root):
		d = 0
		while root:
			d += 1
			root = root.left
		return d

	def Perfect(self, root, depth, level=0):
		if root is None:
			return True
		if root.left is None and root.right is None:
			return depth == level + 1
		if root.left is None or root.right is None:
			return False
		return self.Perfect(root.left, depth, level + 1) and self.Perfect(root.right, depth, level + 1)

	def isPerfect(self, root):
		d = self.Depth(root)
		return self.Perfect(root, d)


class Solution:

	def isPerfect(self, root):
		level = 0
		q = [[root, level]]
		ll = None
		while q:
			[a, l] = q.pop(0)
			if a.left and (not a.right) or (a.right and (not a.left)):
				return False
			if a.left and a.right:
				q.append([a.left, l + 1])
				q.append([a.right, l + 1])
			if not a.left and (not a.right):
				if ll is None:
					ll = l
				elif ll != l:
					return False
		return True


class Solution:

	def isPerfect(self, root):
		ans1 = self.number(root)
		ans2 = self.height(root)
		if ans1 == 2 ** ans2 - 1:
			return True

	def height(self, root):
		if root == None:
			return 0
		ans = max(self.height(root.left), self.height(root.right))
		return ans + 1

	def number(self, root):
		if root == None:
			return 0
		ans1 = self.number(root.left)
		ans2 = self.number(root.right)
		return ans1 + ans2 + 1


class Solution:

	def isPerfect(self, root):
		h = self.height(root)
		return self.perfect(root, h)

	def height(self, root):
		h = 0
		while root != None:
			h = h + 1
			root = root.left
		return h

	def perfect(self, root, h, level=0):
		if root == None:
			return True
		if root.left == None and root.right == None:
			return h == level + 1
		if root.left == None or root.right == None:
			return False
		return self.perfect(root.left, h, level + 1) and self.perfect(root.right, h, level + 1)
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.isPerfect(root)
		if res:
			print('YES')
		else:
			print('NO')


class Solution:

	def isPerfect(self, root):
		mx = [float('-inf')]
		mn = [float('inf')]

		def height(root):
			if root == None:
				return 0
			lh = height(root.left)
			rh = height(root.right)
			return 1 + max(lh, rh)
		d = height(root)

		def traverse(root, lvl):
			if root == None:
				return d == lvl
			return traverse(root.left, lvl + 1) and traverse(root.right, lvl + 1)
		return traverse(root, 0) and height(root)
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.isPerfect(root)
		if res:
			print('YES')
		else:
			print('NO')


class Solution:

	def levelOrder(self, root):
		queue = list()
		queue.append(root)
		final_list = list()
		while len(queue) > 0:
			l = len(queue)
			cur_nodelist = []
			for i in range(0, l):
				node_del = queue.pop(0)
				cur_nodelist.append(node_del.data)
				if node_del.left is not None:
					queue.append(node_del.left)
				if node_del.right is not None:
					queue.append(node_del.right)
			final_list.append(cur_nodelist)
		return final_list

	def isPerfect(self, root):
		if root == None:
			return False
		final_list = self.levelOrder(root)
		for i in range(0, len(final_list) - 1):
			if 2 * len(final_list[i]) != len(final_list[i + 1]):
				return False
		return True
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.isPerfect(root)
		if res:
			print('YES')
		else:
			print('NO')


class Solution:

	def isPerfect(self, root):

		def height(root):
			if root == None:
				return 0
			return 1 + max(height(root.left), height(root.right))
		q = deque()
		q.append(root)
		icount = 0
		total = 0
		while len(q):
			(l, r) = (0, 0)
			x = q.pop()
			if x.right:
				l = 1
				q.append(x.right)
			if x.left:
				r = 1
				q.append(x.left)
			if l and r:
				icount += 1
			if l ^ r:
				return False
			total += 1
		h = height(root)
		return 2 ** h - 1 == total
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.isPerfect(root)
		if res:
			print('YES')
		else:
			print('NO')


class Solution:

	def isPerfect(self, root):
		s = set()

		def fun(root, level):
			if root.left == None or root.right == None:
				s.add(level)
				if len(s) != 1:
					return False
				if root.left == None and root.right == None:
					return True
				return False
			return fun(root.left, level + 1) and fun(root.right, level + 1)
		return fun(root, 0)


class Solution:

	def isPerfect(self, root):
		d = fdep(root)
		return fper(root, d)

def fdep(node):
	d = 0
	while node != None:
		d += 1
		node = node.left
	return d

def fper(root, d, level=0):
	if root is None:
		return True
	if root.left == None and root.right == None:
		return d == level + 1
	if root.left == None or root.right == None:
		return False
	return fper(root.right, d, level + 1) and fper(root.left, d, level + 1)


class Solution:

	def isPerfect(self, root):
		from collections import deque
		q = deque([])
		q.append(root)
		ans = []
		while len(q) != 0:
			c = 0
			for i in range(len(q)):
				cur = q.popleft()
				c = c + 1
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
			ans.append(c)
		for i in range(len(ans)):
			cal = 2 ** i
			if ans[i] != cal:
				return False
				break
		return True


def leaves_at_same_lvl(root, lvl, fll):
	if root == None:
		return True
	if root.left == None and root.right == None:
		if fll[0] == -1:
			fll[0] = lvl
			return True
		elif fll[0] != lvl:
			return False
		return True
	return leaves_at_same_lvl(root.left, lvl + 1, fll) and leaves_at_same_lvl(root.right, lvl + 1, fll)

def node_has_2_children(root):
	if root == None:
		return True
	if root.left == None and root.right == None:
		return True
	if root.left == None or root.right == None:
		return False
	return node_has_2_children(root.left) and node_has_2_children(root.right)

class Solution:

	def isPerfect(self, root):
		return leaves_at_same_lvl(root, 0, [-1]) and node_has_2_children(root)


class Solution:

	def isPerfect(self, root):
		d = findDepth(root)
		return perfectBinaryTree(root, d)

def findDepth(root):
	count = 0
	while root is not None:
		count += 1
		root = root.left
	return count

def perfectBinaryTree(root, d, level=0):
	if root == None:
		return True
	if root.left == None and root.right == None:
		return d == level + 1
	if root.left == None or root.right == None:
		return False
	else:
		return perfectBinaryTree(root.left, d, level + 1) and perfectBinaryTree(root.right, d, level + 1)


class Solution:

	def isPerfect(self, root):
		leaf_level = None
		curr_level = 0
		que = deque([root])
		while que:
			n = len(que)
			for i in range(n):
				curr = que.popleft()
				if not curr.left and (not curr.right):
					if not leaf_level or leaf_level == curr_level:
						leaf_level = curr_level
					else:
						return False
				elif not curr.left or not curr.right:
					return False
				else:
					que.append(curr.left)
					que.append(curr.right)
			curr_level += 1
		return True


class Solution:

	def find_height(self, root):
		height = 0
		while root != None:
			height += 1
			root = root.left
		return height

	def is_perfect_binary_tree(self, root, level, depth):
		if root.left == None and root.right == None:
			if level + 1 == depth:
				return True
			else:
				return False
		if root.left == None or root.right == None:
			return False
		else:
			return self.is_perfect_binary_tree(root.left, level + 1, depth) and self.is_perfect_binary_tree(root.right, level + 1, depth)

	def isPerfect(self, root):
		depth = self.find_height(root)
		return self.is_perfect_binary_tree(root, 0, depth)


class Solution:

	def isPerfect(self, root):
		q = []
		c = 0
		q.append(root)
		while len(q):
			p = q.pop(0)
			if p.left and p.right:
				q.append(p.left)
				q.append(p.right)
			elif p.right:
				c = 1
				break
			elif p.left:
				c = 1
				break
		if c == 1:
			return False
		q = []
		level = 1
		d = {}
		q.append(root)
		while len(q):
			count = len(q)
			while count > 0:
				p = q.pop(0)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
				if p.left == None and p.right == None:
					d[p.data] = level
				count -= 1
			level += 1
		li = list(d.values())
		if li.count(li[0]) == len(li):
			return True
		else:
			return False


class Solution:

	def depth_of_tree(self, root):
		d = 0
		while root != None:
			d += 1
			root = root.left
		return d

	def is_perfect_tree(self, root, level, depth):
		if root.left == None and root.right == None:
			return depth == level + 1
		if root.left == None or root.right == None:
			return False
		return self.is_perfect_tree(root.left, level + 1, depth) and self.is_perfect_tree(root.right, level + 1, depth)

	def isPerfect(self, root):
		depth = self.depth_of_tree(root)
		return self.is_perfect_tree(root, 0, depth)


class Solution:

	def isPerfect(self, root):
		if root is None:
			return 1
		if root.left is None and root.right is None:
			return 1
		q = [root]
		l = []
		k = 0
		res = [root.data]
		while len(q) > 0:
			for node in q:
				if node.left:
					l.append(node.left)
					res.append(node.left.data)
				if node.right:
					l.append(node.right)
					res.append(node.right.data)
			k = k + 1
			q = l
			l = []
		if len(res) == pow(2, k) - 1:
			return True
		return False


class Solution:

	def isLeaf(self, root):
		if not root:
			return True
		if not root.left and (not root.right):
			return True
		return False

	def height(self, root):
		if not root:
			return 0
		return 1 + max(self.height(root.left), self.height(root.right))

	def isPerfect(self, root):
		if not root:
			return True
		q = deque()
		q.append(root)
		level = 0
		while q:
			qlen = len(q)
			if qlen != 2 ** level:
				return False
			for i in range(len(q)):
				node = q.popleft()
				if node.left and (not node.right) or (not node.left and node.right):
					return False
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
		return True


class Solution:

	def isPerfect(self, root):
		d = self.find_depth(root)
		return self.perfect_tree_util(root, d)

	def find_depth(self, root):
		if root is None:
			return 0
		d = 0
		while root != None:
			d += 1
			root = root.left
		return d

	def perfect_tree_util(self, root, d, level=0):
		if root == None:
			return True
		if root.left == None and root.right == None:
			return d == level + 1
		if root.left == None or root.right == None:
			return False
		return self.perfect_tree_util(root.left, d, level + 1) and self.perfect_tree_util(root.right, d, level + 1)


class Solution:

	def isPerfect(self, root):
		if not root:
			return
		return per(root.left, root.right, 1)

def per(n1, n2, h):
	if n1 == None and n2 == None:
		return h
	if n1 == None or n2 == None:
		return False
	h += 1
	if per(n1.left, n1.right, h) and per(n2.left, n2.right, h) and (per(n1.left, n1.right, h) == per(n2.left, n2.right, h)):
		return True


import math

class Solution:

	def algo(self, root):
		if root is None:
			return 0
		(l, r) = (self.algo(root.left), self.algo(root.right))
		if l == -1 or r == -1:
			return -1
		if abs(l - r) >= 1:
			return -1
		return 1 + max(l, r)

	def algo1(self, root):
		ans = 0
		q = []
		q.append(root)
		while len(q) > 0:
			c = q.pop(0)
			ans += 1
			if c.left:
				q.append(c.left)
			if c.right:
				q.append(c.right)
		return ans

	def isPerfect(self, root):
		return True if self.algo(root) != -1 else False


class Solution:

	def fun(self, root, found, level, l):
		if root == None:
			return
		if root.left == None and root.right != None:
			found[0] = 1
			return
		elif root.right == None and root.left != None:
			found[0] = 1
			return
		elif root.left == None and root.right == None:
			l.add(level)
		self.fun(root.left, found, level + 1, l)
		self.fun(root.right, found, level + 1, l)

	def isPerfect(self, root):
		found = [0]
		l = set()
		level = 0
		self.fun(root, found, level, l)
		if found[0] == 0 and len(l) == 1:
			return True
		else:
			return False


class Solution:

	def level(self, root):
		if not root:
			return -1
		return 1 + max(self.level(root.left), self.level(root.right))

	def isPerfect(self, root):
		if not root:
			return True
		if not root.left and (not root.right):
			return True
		if root.left and root.right:
			if not self.level(root.left) == self.level(root.right):
				return False
			return self.isPerfect(root.left) and self.isPerfect(root.right)
		return False


class Solution:

	def findDepth(self, root):
		depth = 0
		while root != None:
			depth += 1
			root = root.left
		return depth

	def isPerfectRoot(self, root, depth, level=0):
		if root is None:
			return True
		if root.left == None and root.right == None:
			return depth == level + 1
		if root.left == None or root.right == None:
			return False
		return self.isPerfectRoot(root.left, depth, level + 1) and self.isPerfectRoot(root.right, depth, level + 1)

	def isPerfect(self, root):
		depth = self.findDepth(root)
		return self.isPerfectRoot(root, depth, level=0)


class Solution:

	def isPerfect(self, root):
		return not self.solve(root) == -1

	def solve(self, root):
		if root.right == None and root.left == None:
			return 1
		elif root.right == None or root.left == None:
			return -1
		h1 = self.solve(root.right) if root.right != None else -1
		h2 = self.solve(root.left) if root.left != None else -1
		if h1 == -1 or h2 == -1 or h1 != h2:
			return -1
		else:
			return 1 + max(h1, h2)


class Solution:

	def isPerfect(self, root):
		q = []
		q.append(root)
		lvl = 0
		while q:
			sze = len(q)
			if sze != 2 ** lvl:
				return False
			while sze > 0:
				node = q.pop(0)
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
				sze -= 1
			lvl += 1
		return True


from collections import defaultdict

class Solution:

	def isPerfect(self, root):
		d = defaultdict(list)

		def bfs(node, level):
			if not node:
				return
			d[level].append(node.data)
			bfs(node.left, level + 1)
			bfs(node.right, level + 1)
		bfs(root, 0)
		i = 0
		for (key, value) in d.items():
			if len(value) != int(2 ** i):
				return False
			i = i + 1
		return True