Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes should be as much close to left as possible.
Example 1:
Input:
       1
      / \
     2   3
Output:
Complete Binary Tree
Example 2:
Input:
              1
            /   \
          2      3
           \    /  \
            4  5    6
Output:
Not Complete Binary Tree
Constraints:
1<=Number of Node<=100
0 <= Data of a node <= 10^{6}
Your Task:
You don't need to take input. Just complete the function isCompleteBT() that takes root node as a parameter and returns true, if the tree is Complete else returns false.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: # function return true if the tree is complete else false



class Solution():

    def isCompleteBT(self, root):

        #Add Code Here



Solutions:
class Solution:

	def isCompleteBT(self, root):
		queue = [root]
		flag = 0
		while queue:
			node = queue.pop(0)
			if node.left:
				queue.append(node.left)
				if flag == 1:
					return False
			else:
				flag = 1
			if node.right:
				queue.append(node.right)
				if flag == 1:
					return False
			else:
				flag = 1
		return True


class Solution:

	def isCompleteBT(self, root):
		q = [root]
		seen = False
		while q:
			n = len(q)
			for i in range(n):
				c = q[i]
				if c:
					if seen:
						return False
					else:
						q.append(c.left)
						q.append(c.right)
				else:
					seen = True
			q = q[n:]
		return True


class Solution:

	def check(self, root, i, n):
		if root == None:
			return True
		if i >= n:
			return False
		return self.check(root.left, 2 * i + 1, n) and self.check(root.right, 2 * i + 2, n)

	def solve(self, root):
		if root == None:
			return
		self.count += 1
		self.solve(root.left)
		self.solve(root.right)

	def isCompleteBT(self, root):
		self.count = 0
		self.solve(root)
		return self.check(root, 0, self.count)


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		if not root:
			return True
		q = deque()
		q.append(root)
		flag = False
		while len(q) > 0:
			curr = q.popleft()
			if not curr.left and curr.right:
				return False
			elif curr.left and (not curr.right):
				if flag:
					return False
				flag = True
				q.append(curr.left)
			elif curr.left and curr.right:
				if flag:
					return False
				q.append(curr.left)
				q.append(curr.right)
			else:
				flag = True
		return True


class Solution:

	def isCompleteBT(self, root):
		if not root:
			return True
		queue = [root]
		condition = True
		while len(queue) > 0:
			current = queue.pop(0)
			if (current.left or current.right) and (not condition):
				return False
			if not current.left and current.right:
				return False
			if not current.left or not current.right:
				condition = False
			if current.left:
				queue.append(current.left)
			if current.right:
				queue.append(current.right)
		return True


from queue import Queue

class Solution:

	def isCompleteBT(self, root):
		q = Queue()
		q.put(root)
		while not q.empty():
			node = q.get()
			if node is None and (not q.empty()):
				break
			q.put(node.left)
			q.put(node.right)
		while not q.empty():
			node = q.get()
			if node is not None:
				return False
		return True


class Solution:

	def isCompleteBT(self, root):
		q = deque([root])
		while q:
			node = q.popleft()
			if node:
				q.append(node.left)
				q.append(node.right)
			else:
				while q:
					if q.popleft():
						return False
		return True


class Solution:

	def isCompleteBT(self, root):
		if not root:
			return True
		q = []
		q.append(root)
		flag = False
		while q:
			temp = q.pop(0)
			if not temp:
				flag = True
			else:
				if flag:
					return False
				q.append(temp.left)
				q.append(temp.right)
		return True


class Solution:

	def isCompleteBT(self, root):

		def dfs(root, coords):
			if root:
				self.right_most = max(self.right_most, coords)
				self.total += 1
				dfs(root.left, 2 * coords)
				dfs(root.right, 2 * coords + 1)
		self.total = 0
		self.right_most = 0
		dfs(root, 1)
		return self.total == self.right_most


class Solution:

	def isCompleteBT(self, root):
		if root == None:
			return True
		q = deque()
		flag = False
		q.append(root)
		while q:
			temp = q.popleft()
			if temp.left:
				q.append(temp.left)
				if flag == True:
					return False
			else:
				flag = True
			if temp.right:
				q.append(temp.right)
				if flag == True:
					return False
			else:
				flag = True
		return True


class Solution:

	def isCompleteBT(self, root):
		from collections import deque
		if not root:
			return True
		q = deque([root])
		while q[0] is not None:
			node = q.popleft()
			q.append(node.left)
			q.append(node.right)
		while q and q[0] is None:
			q.popleft()
		return not bool(q)


class Solution:

	def isCompleteBT(self, root):
		if not root:
			return True
		q = [root]
		f = False
		while q:
			n = q.pop(0)
			if n is None:
				f = True
				continue
			if f:
				return False
			q.append(n.left)
			q.append(n.right)
		return True


class Solution:

	def isCompleteBT(self, root):
		q = deque([root])
		c = 0
		while q:
			for i in range(len(q)):
				curr = q.popleft()
				if curr.left:
					if c == 1:
						return 0
					else:
						q.append(curr.left)
				else:
					c = 1
				if curr.right:
					if c == 1:
						return 0
					else:
						q.append(curr.right)
				else:
					c = 1
		return True


class Solution:

	def isCompleteBT(self, root):
		q = [root]
		i = 0
		while q[i]:
			q.append(q[i].left)
			q.append(q[i].right)
			i += 1
		return not any(q[i:])


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		q = deque([root])
		prev = root
		while q:
			cur = q.popleft()
			if cur:
				if not prev:
					return False
				q.append(cur.left)
				q.append(cur.right)
			prev = cur
		return True


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return True
		q = deque()
		q.append(root)
		flag = False
		while len(q) > 0:
			temp = q.popleft()
			if temp.left:
				q.append(temp.left)
				if flag == True:
					return False
			else:
				flag = True
			if temp.right:
				q.append(temp.right)
				if flag == True:
					return False
			else:
				flag = True
		return True


class Solution:

	def isCompleteBT(self, root):
		queue = [root]
		i = 0
		while queue[i]:
			queue.extend([queue[i].left, queue[i].right])
			i += 1
		return not any(queue[i:])


class Solution:

	def isCompleteBT(self, root):
		prev = False
		queue = [root]
		while queue != []:
			curr = queue[0]
			queue.pop(0)
			if prev and curr != None:
				return False
			if curr != None:
				queue.append(curr.left)
				queue.append(curr.right)
			else:
				prev = True
		return True


class Solution:

	def isCompleteBT(self, root):
		q = []
		q.append(root)
		flag = False
		while q:
			l = len(q)
			for i in range(l):
				temp = q.pop(0)
				if temp.left:
					if flag == True:
						return False
					q.append(temp.left)
				else:
					flag = True
				if temp.right:
					if flag == True:
						return False
					q.append(temp.right)
				else:
					flag = True
		return True


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		queue = deque([root])
		ans = []
		while queue:
			ele = queue.popleft()
			if ele is None:
				ans.append('N')
				continue
			ans.append(ele.data)
			queue.append(ele.left)
			queue.append(ele.right)
		isN = False
		for i in ans:
			if i != 'N' and isN:
				return False
			if i == 'N':
				isN = True
		return True


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
from collections import deque

class Solution:

	def isCompleteBT(self, root):
		NOTperfect = False
		if root == None:
			return True
		q = deque()
		q.append(root)
		while q:
			temp = q.popleft()
			if temp.left:
				if NOTperfect == True:
					return False
				q.append(temp.left)
			else:
				NOTperfect = True
			if temp.right:
				if NOTperfect == True:
					return False
				q.append(temp.right)
			else:
				NOTperfect = True
		return True


class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return True
		flag = False
		l = []
		l.append(root)
		while len(l) != 0:
			a = l.pop(0)
			if a.left:
				if flag == True:
					return False
				l.append(a.left)
			else:
				flag = True
			if a.right:
				if flag == True:
					return False
				l.append(a.right)
			else:
				flag = True
		return True


class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return True
		q = []
		f = False
		q.append(root)
		while len(q) != 0:
			temp = q.pop(0)
			if temp.left:
				if f == True:
					return False
				q.append(temp.left)
			else:
				f = True
			if temp.right:
				if f == True:
					return False
				q.append(temp.right)
			else:
				f = True
		return True


class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return True
		q = []
		Flag = False
		q.append(root)
		while len(q) != 0:
			y = q.pop(0)
			if y is None:
				Flag = True
			else:
				if Flag:
					return False
				q.append(y.left)
				q.append(y.right)
		return True


class Solution:

	def isCompleteBT(self, root):
		res = []
		res.append(root)
		end = False
		while res != []:
			curr = res.pop(0)
			if curr == None:
				end = True
			else:
				if end == True:
					return False
				res.append(curr.left)
				res.append(curr.right)
		return True


class Solution:

	def isCompleteBT(self, root):
		arr = [[]]
		self.helper(root, 0, arr)
		transversal = []
		for item in arr:
			transversal += item
		while transversal[-1] == None:
			transversal.pop()
		return None not in transversal

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


class Solution:

	def isCompleteBT(self, root):
		p = [root]
		x = False
		while len(p) > 0:
			a = p.pop(0)
			if a == None:
				x = True
			elif x:
				return False
			else:
				p.append(a.left)
				p.append(a.right)
		return True


class Solution:

	def isCompleteBT(self, root):
		a1 = {}
		queue = [root]
		queue1 = [0]
		while len(queue) > 0:
			x = queue.pop(0)
			y = queue1.pop(0)
			if y not in a1:
				a1[y] = []
			a1[y] += [x]
			if x:
				queue.append(x.left)
				queue.append(x.right)
				queue1.append(y + 1)
				queue1.append(y + 1)
		c = 0
		for i in range(max(a1) + 1):
			for j in a1[i]:
				if j and c > 0:
					return False
				elif j == None:
					c += 1
		return True


class Solution:

	def isCompleteBT(self, root):
		stack = [root]
		temp = []
		while stack:
			n = len(stack)
			while n:
				top = stack.pop(0)
				if top.left:
					temp.append(top.left.data)
					stack.append(top.left)
				else:
					temp.append(-1)
				if top.right:
					temp.append(top.right.data)
					stack.append(top.right)
				else:
					temp.append(-1)
				n -= 1
		n = len(temp)
		for i in range(n - 1):
			(a, b) = (temp[i], temp[i + 1])
			if a == -1 and b > -1:
				return 0
		return 1


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		if root == None:
			return False
		q = deque()
		q.append(root)
		flag = False
		while q:
			t = q.popleft()
			if t.left:
				if flag == True:
					return False
				q.append(t.left)
			else:
				flag = True
			if t.right:
				if flag == True:
					return False
				q.append(t.right)
			else:
				flag = True
		return True


class Solution:

	def isCompleteBT(self, root):
		q = []
		q.append(root)
		foundNull = False
		while len(q) > 0:
			for i in range(len(q)):
				temp = q.pop(0)
				if temp == None:
					foundNull = True
				elif foundNull == True:
					return False
				else:
					q.append(temp.left)
					q.append(temp.right)
		return True


class Solution:

	def isCompleteBT(self, root):
		queue = deque([(root, 1)])
		Flag = False
		while queue:
			(node, h) = queue.popleft()
			if node.left is not None:
				if Flag:
					return False
				queue.append((node.left, h + 1))
			else:
				Flag = True
			if node.right is not None:
				if Flag:
					return False
				queue.append((node.right, h + 1))
			else:
				Flag = True
		return True


class Solution:

	def isCompleteBT(self, root):
		q = [root]
		arr = [root]
		while len(q) != 0:
			for i in range(len(q)):
				node = q.pop(0)
				if node.left != None:
					q.append(node.left)
				arr.append(node.left)
				if node.right != None:
					q.append(node.right)
				arr.append(node.right)
		status = 1
		for i in range(len(arr)):
			if arr[i] == None:
				cur = 0
			else:
				cur = 1
			if status == 0 and cur == 1:
				return False
			else:
				status = cur
		return True


import collections

class Solution:

	def isCompleteBT(self, root):
		q = collections.deque([root])
		curLevelGap = False
		while q:
			NextLevelGap = False
			for i in range(len(q)):
				node = q.popleft()
				if NextLevelGap:
					if node.left:
						return False
				elif node.left:
					q.append(node.left)
				else:
					NextLevelGap = True
				if NextLevelGap:
					if node.right:
						return False
				elif node.right:
					q.append(node.right)
				else:
					NextLevelGap = True
			if curLevelGap:
				if len(q) != 0:
					return False
			curLevelGap = NextLevelGap
		return True


class Solution:

	def isCompleteBT(self, root):
		node_count = self.count_nodes(root)
		index = 0
		if self.is_complete(root, index, node_count):
			return True
		else:
			return False

	def is_complete(self, root, index, numberNodes):
		if root is None:
			return True
		if index >= numberNodes:
			return False
		return self.is_complete(root.left, 2 * index + 1, numberNodes) and self.is_complete(root.right, 2 * index + 2, numberNodes)

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


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		que = deque()
		que.append(root)
		flag = False
		while que:
			x = que.popleft()
			if flag == False:
				if x.left == None:
					flag = True
				else:
					que.append(x.left)
				if x.right == None:
					flag = True
				elif flag == False:
					que.append(x.right)
				elif flag == True:
					return False
			elif x.left or x.right:
				return False
		return True


class Solution:

	def isCompleteBT(self, root):
		if root == None:
			return 0
		height = 1
		flag = 0
		queue = []
		queue.append(root)
		while len(queue) > 0:
			curSize = len(queue)
			while curSize > 0:
				cur = queue.pop(0)
				if cur.left != None:
					if flag == 1:
						return False
					else:
						queue.append(cur.left)
				else:
					flag = 1
				if cur.right != None:
					if flag == 1:
						return False
					else:
						queue.append(cur.right)
				else:
					flag = 1
				curSize -= 1
			height += 1
		return True


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		if not root:
			return True
		q = [root]
		flag = False
		while q:
			for _ in range(len(q)):
				c = q.pop(0)
				if c is None:
					flag = True
				elif flag:
					return False
				else:
					q.append(c.left)
					q.append(c.right)
		return True


class Solution:

	def isCompleteBT(self, root):

		def traversal(root, level):
			if root == None:
				arr.append(None)
				return
			if level == 0:
				arr.append(root.data)
			else:
				traversal(root.left, level - 1)
				traversal(root.right, level - 1)

		def height(root):
			if root == None:
				return 0
			lh = height(root.left)
			rh = height(root.right)
			return max(lh, rh) + 1
		tall = height(root)
		arr = []
		for i in range(tall):
			traversal(root, i)
			length = len(arr)
			if None in arr:
				if i != tall - 1:
					return False
				else:
					for i in range(-1, -length, -1):
						if i > -length and arr[i] != None and (arr[i - 1] == None):
							return False
			arr = []
		return True


class Solution:

	def isCompleteBT(self, root):
		level = [root]

		def findNone(arr, starti=0):
			while 0 <= starti < len(arr):
				if not arr[starti]:
					return starti
				starti += 1
			return -1
		while level:
			newLevel = []
			for ele in level:
				newLevel.append(ele.left)
				newLevel.append(ele.right)
			firstNone = findNone(newLevel)
			if firstNone >= 0:
				secondNone = firstNone
				while secondNone < len(newLevel) and newLevel[secondNone] is None:
					secondNone += 1
				if secondNone == len(newLevel):
					for i in range(firstNone):
						if newLevel[i].left or newLevel[i].right:
							return False
					return True
				return False
			level = newLevel
		return False


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return False
		if not root.left and (not root.right):
			return True
		(q, len1) = ([root], 1)
		while True:
			(nq, len2) = ([], 0)
			for i in q:
				if i.left:
					nq.append(i.left)
					len2 += 1
				if i.right:
					nq.append(i.right)
					len2 += 1
			if len2 == 0:
				return True
			elif len2 == 2 * len1:
				(q, len1) = (nq, len2)
			else:
				return False
		return False

	def isCompleteBT(self, root):
		NOTperfect = False
		if root == None:
			return True
		q = deque()
		q.append(root)
		while q:
			temp = q.popleft()
			if temp.left:
				if NOTperfect == True:
					return False
				q.append(temp.left)
			else:
				NOTperfect = True
			if temp.right:
				if NOTperfect == True:
					return False
				q.append(temp.right)
			else:
				NOTperfect = True
		return True

	def isCompleteBT(self, root):
		if root is None:
			return True
		(q, flag) = ([root], False)
		while q:
			temp = q.pop(0)
			if temp.left:
				if flag == True:
					return False
				q.append(temp.left)
			else:
				flag = True
			if temp.right:
				if flag == True:
					return False
				q.append(temp.right)
			else:
				flag = True
		return True


class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return
		q = [root]
		flag = False
		while q != []:
			n = len(q)
			for i in range(n):
				temp = q.pop(0)
				if flag:
					if temp.left or temp.right:
						return False
				if temp.left:
					q.append(temp.left)
				else:
					flag = True
					if temp.right:
						return False
				if temp.right:
					q.append(temp.right)
				else:
					flag = True
		return True


class Solution:

	def isCompleteBT(self, root):
		q = []
		if not root:
			return True
		q.append(root)
		flag = True
		while q:
			n = len(q)
			while n > 0:
				tmp = q.pop(0)
				if tmp.left and tmp.right and flag:
					q.append(tmp.left)
					q.append(tmp.right)
				elif flag and tmp.left and (not tmp.right):
					q.append(tmp.left)
					flag = False
				elif flag and (not (tmp.left or tmp.right)):
					flag = False
				elif not flag and (not (tmp.left or tmp.right)):
					pass
				else:
					return False
				n -= 1
		return True


class Solution:

	def isCompleteBT(self, root):
		q = [root]
		status = False
		while q:
			l = len(q)
			while l > 0:
				node = q.pop(0)
				if node.left == None:
					status = True
				else:
					if status:
						return False
					q.append(node.left)
				if node.right == None:
					status = True
				else:
					if status:
						return False
					q.append(node.right)
				l -= 1
		return True


class Solution:

	def isCompleteBT(self, root):
		if root == None:
			return True
		queue = [root]
		end = False
		while queue:
			a = queue.pop(0)
			if a == None:
				end = True
			else:
				if end == True:
					return False
				queue.append(a.left)
				queue.append(a.right)
		return True


class Solution:

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


class Solution:

	def isCompleteBT(self, root):
		q = deque([root])
		done = False
		while q:
			if done:
				break
			for i in range(len(q)):
				n = q.popleft()
				if done:
					if n.left or n.right:
						return False
				if n.left:
					q.append(n.left)
				else:
					done = True
				if n.right:
					if done:
						return False
					else:
						q.append(n.right)
				else:
					done = True
		while q:
			n = q.popleft()
			if n.left or n.right:
				return False
		return True


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return False
		queue = deque()
		queue.append(root)
		while queue:
			curr = queue.popleft()
			if curr.left is not None and curr.right is not None:
				queue.append(curr.left)
				queue.append(curr.right)
			elif curr.left is None and curr.right is not None:
				return False
			elif curr.left is None and curr.right is None:
				n = len(queue)
				for i in range(n):
					c = queue.popleft()
					if c.left is not None:
						return False
					if c.right is not None:
						return False
			else:
				queue.append(curr.left)
				n = len(queue)
				for i in range(n):
					c = queue.popleft()
					if c.left is not None:
						return False
					if c.right is not None:
						return False
		return True


from collections import deque

class Solution:

	def isCompleteBT(self, root):
		q = deque()
		q.append(root)
		none_occ = False
		while q:
			ll = len(q)
			for ii in range(ll):
				node = q.popleft()
				if node and none_occ:
					return False
				if node == None:
					none_occ = True
				if node:
					q.append(node.left)
					q.append(node.right)
		return True


class Solution:

	def isCompleteBT(self, root):
		q = []
		q.append(root)
		seen = False
		while len(q):
			p = q.pop(0)
			if p.left:
				q.append(p.left)
				if seen == True:
					return False
			else:
				seen = True
			if p.right:
				q.append(p.right)
				if seen == True:
					return False
			else:
				seen = True
		return True


class Solution:

	def isCompleteBT(self, root):
		lst = []
		lst.append(root)
		Node = False
		while lst:
			root = lst.pop(0)
			if root:
				if Node:
					return False
				lst.append(root.left)
				lst.append(root.right)
			else:
				Node = True
		return True


class Solution:

	def isCompleteBT(self, root):
		res = []
		temp = []
		temp.append(root)
		while len(temp) > 0:
			el = temp.pop(0)
			if el is not None:
				temp.append(el.left)
				temp.append(el.right)
				res.append(el.data)
			else:
				res.append('N')
		flag = -1
		for el in res:
			if el == 'N':
				flag = 0
			if el != 'N' and flag == 0:
				return False
		return True


class Solution:

	def isCompleteBT(self, root):
		umap = {}
		flag = 0
		temp = [root, 0]
		queue = [temp]
		while len(queue) != 0:
			if queue[0][1] in umap:
				umap[queue[0][1]].append(queue[0][0].data)
			else:
				umap[queue[0][1]] = [queue[0][0].data]
			if flag == 1:
				if queue[0][0].left != None or queue[0][0].right != None:
					return False
			if queue[0][0].left != None:
				temp = [queue[0][0].left, queue[0][1] + 1]
				queue.append(temp)
			else:
				flag = 1
			if queue[0][0].right != None:
				if flag == 1:
					return False
				temp = [queue[0][0].right, queue[0][1] + 1]
				queue.append(temp)
			else:
				flag = 1
			queue.pop(0)
		val = max(umap)
		for i in umap:
			if i != val:
				if len(umap[i]) != pow(2, i):
					return False
		return True


class Solution:

	def isCompleteBT(self, root):
		q = []
		q.append(root)
		if not root:
			return True
		i = 0
		prev = 1
		flag = False
		while q:
			n = len(q)
			cur = q.pop(0)
			if cur.left:
				if flag:
					return False
				q.append(cur.left)
			else:
				flag = True
			if cur.right:
				if flag:
					return False
				q.append(cur.right)
			else:
				flag = True
		return True


class Solution:
	res = ''

	def isCompleteBT(self, root):
		height = self.height(root)
		for level in range(1, height):
			self.res = ''
			self.printNodes(root, level)
			if '#' in self.res:
				return False
		self.res = ''
		self.printNodes(root, height)
		if '#' in self.res.rstrip('#'):
			return False
		return True

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

	def printNodes(self, root, level):
		if root is None:
			self.res += '#'
			return
		if level == 1:
			self.res += str(root.data)
			return
		elif level > 1:
			self.printNodes(root.left, level - 1)
			self.printNodes(root.right, level - 1)


class Solution:

	def isCompleteBT(self, root):
		heights = []

		def rec(node, h):
			if not node:
				heights.append(h)
				return
			rec(node.left, h + 1)
			rec(node.right, h + 1)
		rec(root, 0)

		def isComplete():
			n = len(heights)
			count1 = 0
			count2 = 0
			for i in range(n):
				if heights[i] == heights[0]:
					count1 += 1
				else:
					break
			if heights[-1] != heights[0]:
				for i in range(n - 1, -1, -1):
					if heights[i] == heights[-1]:
						count2 += 1
					else:
						break
			return 0 <= heights[0] - heights[-1] <= 1 and count1 + count2 == n
		return isComplete()


class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return True
		flag = True
		q = []
		q.append(root)
		while len(q) != 0:
			k = len(q)
			for i in range(0, k):
				if q[i] == None:
					flag = False
					for j in range(i + 1, k):
						if q[j] != None:
							return False
			for i in range(0, k):
				if q[i] != None:
					if q[i].left is not None:
						q.append(q[i].left)
					else:
						q.append(None)
					if q[i].right is not None:
						q.append(q[i].right)
					else:
						q.append(None)
			for i in range(0, k):
				del q[0]
			if flag == False:
				for i in q:
					if i != None:
						return False
		return True


import collections

class Solution:

	def isCompleteBT(self, root):
		flag = False
		q = collections.deque()
		q.append(root)
		while q:
			node = q.popleft()
			if not node:
				flag = True
				continue
			elif flag:
				return False
			if not node.left and node.right:
				return False
			else:
				if node.left:
					q.append(node.left)
				else:
					q.append(None)
				if node.right:
					q.append(node.right)
				else:
					q.append(None)
		return True


class Solution:

	def isCompleteBT(self, root):
		Q = []
		Q.append(root)
		end = False
		while Q:
			root = Q.pop(0)
			if root is None:
				end = True
			else:
				if end is True:
					return False
				Q.append(root.left)
				Q.append(root.right)
		return True


class Solution:

	def isCompleteBT(self, root):
		c = self.count(root)
		return self.helper(root, 0, c)

	def helper(self, root, index, count):
		if root == None:
			return True
		if index >= count:
			return False
		return self.helper(root.left, 2 * index + 1, count) and self.helper(root.right, 2 * index + 2, count)

	def count(self, root):
		if root == None:
			return 0
		return 1 + self.count(root.left) + self.count(root.right)
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = 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__':
	root = None
	t = int(input())
	for i in range(t):
		s = input()
		root = buildTree(s)
		obj = Solution()
		if obj.isCompleteBT(root):
			print('Complete Binary Tree')
		else:
			print('Not Complete Binary Tree')


class Solution:

	def isCompleteBT(self, root):
		if root is None:
			return True
		queue = []
		queue.append(root)
		seenNone = False
		while queue:
			elem = queue.pop(0)
			if elem is not None:
				if not seenNone:
					queue.append(elem.left)
					queue.append(elem.right)
				else:
					return False
			else:
				seenNone = True
		return True
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = 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__':
	root = None
	t = int(input())
	for i in range(t):
		s = input()
		root = buildTree(s)
		obj = Solution()
		if obj.isCompleteBT(root):
			print('Complete Binary Tree')
		else:
			print('Not Complete Binary Tree')


class Solution:

	@staticmethod
	def levelOrder(node, levelOrder_list):
		queue = list()
		queue.append(node)
		while len(queue) > 0:
			poppedNode = queue.pop(0)
			levelOrder_list.append(poppedNode)
			if poppedNode.left is not None:
				queue.append(poppedNode.left)
			if poppedNode.right is not None:
				queue.append(poppedNode.right)

	def isCompleteBT(self, root):
		levelOrder_list = list()
		Solution.levelOrder(root, levelOrder_list)
		N = len(levelOrder_list)
		for (index, node) in enumerate(levelOrder_list):
			parentIndex = index
			childIndex1 = 2 * parentIndex + 1
			childIndex2 = 2 * parentIndex + 2
			if childIndex1 < N and node.left != levelOrder_list[childIndex1] or (childIndex2 < N and node.right != levelOrder_list[childIndex2]):
				return False
		return True
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = 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__':
	root = None
	t = int(input())
	for i in range(t):
		s = input()
		root = buildTree(s)
		obj = Solution()
		if obj.isCompleteBT(root):
			print('Complete Binary Tree')
		else:
			print('Not Complete Binary Tree')