Given a Binary Tree. Check whether the Binary tree is a full binary tree or not.
Example 1:
Input:
          1
       /    \
      2      3
    /   \
   4     5
Output: 1
Explanation: Every node except leaf node
has two children so it is a full tree.
Example 2:
Input:
          1
       /    \
      2      3
    /   
   4     
Output: 0
Explanation: Node 2 has only one child
so this is not a full tree.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function isFullTree() which takes the root node of the tree as input and returns True if the given Binary Tree is full. Else, it returns False. (The driver code will print 1 if the returned value is true, otherwise 0).
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1<=Number of nodes<=1000
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Difficulty: EASY
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).

Starter code:
#User function Template for python3



'''

# Node Class:

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

        

# Return True if the given Binary Tree is a Full Binary Tree. Else return False

def isFullTree(root):

    #code here

Solutions:
def isFullTree(root):

	def f(root):
		if not root.left and (not root.right):
			return 1
		if not root.left and root.right or (not root.right and root.left):
			return 0
		return f(root.left) and f(root.right)
	return f(root)


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


def tr(root, ans):
	if root is None:
		return -1
	if root.left == root.right == None:
		return 'ok'
	if None in [root.left, root.right]:
		ans[0] = False
	tr(root.left, ans)
	tr(root.right, ans)

def isFullTree(root):
	ans = [True]
	tr(root, ans)
	return ans[0]


def isFullTree(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 isFullTree(root.left) and isFullTree(root.right)


def isFullTree(root):
	if root.left is None and root.right is None:
		return 1
	if root.left is None and root.right is not None or (root.left is not None and root.right is None):
		return 0
	return isFullTree(root.left) * isFullTree(root.right)


def check1(root):
	if root.left == None and root.right == None:
		return 1
	elif root.left != None and root.right != None:
		return check1(root.left) and check1(root.right)
	return 0

def isFullTree(root):
	x = check1(root)
	return x


def isFullTree(root):
	if not root:
		return
	if root.left and (not root.right):
		return 0
	if root.right and (not root.left):
		return 0
	if root.left and root.right:
		return isFullTree(root.left) and isFullTree(root.right)
	return 1


def dfs(root):
	if root == None:
		return True
	if root.left == None and root.right == None:
		return True
	if root.left and root.right:
		return dfs(root.left) and dfs(root.right)

def isFullTree(root):
	return dfs(root)


import collections

def isFullTree(root):
	q = collections.deque()
	q.append(root)
	while q:
		qLen = len(q)
		for i in range(qLen):
			cur = q.popleft()
			if cur.left and cur.right:
				q.append(cur.left)
				q.append(cur.right)
			elif not cur.left and (not cur.right):
				continue
			else:
				return False
	return True


def isFullTree(root):
	if not root:
		return True
	if not root.left and (not root.right):
		return True
	if not root.left or not root.right:
		return False
	return isFullTree(root.left) and isFullTree(root.right)


def isFullTree(root):
	to_search = [root]
	i = 0
	level_no = True
	while i < len(to_search):
		if to_search[i].right is not None and to_search[i].left is not None:
			to_search.append(to_search[i].right)
			to_search.append(to_search[i].left)
		elif to_search[i].right is None and to_search[i].left is None:
			pass
		else:
			level_no = False
			break
		i += 1
	return level_no


def isFullTree(root):
	if root == None:
		return
	lh = isFullTree(root.left)
	rh = isFullTree(root.right)
	if lh == None and rh == None or (lh == True and rh == True):
		return True
	else:
		return False


def isFullTree(root):
	s = []
	cur = root
	while cur or s:
		while cur:
			s.append(cur)
			if cur.right == None and cur.left != None:
				return False
			if cur.left == None and cur.right != None:
				return False
			cur = cur.left
		cur = s.pop()
		cur = cur.right
	return True


def isFullTree(root):
	if root.left == None and root.right == None:
		return True
	if root.left != None and root.right != None:
		l = isFullTree(root.left)
		r = isFullTree(root.right)
		return l and r
	return False


def isFullTree(root):
	if not root:
		return True
	if root.left and (not root.right) or (not root.left and root.right):
		return 0
	return isFullTree(root.left) and isFullTree(root.right)


def depthFirstSearch(root, ifNotFullBinaryTree):
	if ifNotFullBinaryTree[0]:
		return
	if root.left is None and root.right is None:
		return
	if root.left is not None and root.right is not None:
		depthFirstSearch(root.left, ifNotFullBinaryTree)
		depthFirstSearch(root.right, ifNotFullBinaryTree)
	else:
		ifNotFullBinaryTree[0] = True

def isFullTree(root):
	ifNotFullBinaryTree = [False]
	depthFirstSearch(root, ifNotFullBinaryTree)
	return not ifNotFullBinaryTree[0]


def isFullTree(root):
	if root == None:
		return True
	if root.left == None and root.right == None:
		return True
	if root.left != None and root.right != None:
		return isFullTree(root.left) and isFullTree(root.right)
	else:
		return False


def isFullTree(root):
	if not root:
		return False

	def checkTree(root):
		left = False
		right = False
		if root.left:
			left = checkTree(root.left)
		if root.right:
			right = checkTree(root.right)
		if not root.left and (not root.right):
			return True
		return left and right
	return checkTree(root)


def isFullTree(root):
	if not root:
		return True
	queue = deque([root])
	while queue:
		node = queue.popleft()
		if not node.left and (not node.right):
			continue
		if not node.left or not node.right:
			return False
		queue.append(node.left)
		queue.append(node.right)
	return True


def isFullTree(root):
	if root.left is None and root.right is None:
		return 1
	elif root.left is not None and root.right is not None:
		return isFullTree(root.left) * isFullTree(root.right)
	else:
		return 0


def isFullTree(root):
	if root and root.left and root.right:
		return isFullTree(root.left) and isFullTree(root.right)
	elif root and (not root.left) and (not root.right):
		return True
	return False


def get(root, arr):
	if not root:
		return
	if root.right and (not root.left):
		arr.append(False)
	if not root.right and root.left:
		arr.append(False)
	get(root.right, arr)
	get(root.left, arr)

def isFullTree(root):
	if not root:
		return 0
	arr = []
	get(root, arr)
	if len(arr) > 0:
		return 0
	return 1


def isFullTree(root):
	if not root:
		return False
	queue = []
	queue.append(root)
	while queue:
		size = len(queue)
		for i in range(size):
			no_of_child = 0
			cur_ele = queue.pop(0)
			if cur_ele.left:
				queue.append(cur_ele.left)
				no_of_child += 1
			if cur_ele.right:
				queue.append(cur_ele.right)
				no_of_child += 1
			if no_of_child == 1:
				return False
	return True


def isFullTree(root):
	q = [root]
	c = 0
	while c != len(q):
		t = q[c]
		if t.left is None and t.right is None:
			pass
		elif t.left is None or t.right is None:
			return False
		else:
			q.append(t.left)
			q.append(t.right)
		c += 1
	return True


def isFullTree(root):

	def solve(root):
		if root.left == None and root.right == None:
			return 1
		if (root.left == None) ^ (root.right == None):
			return 0
		if solve(root.left) and solve(root.right):
			return 1
		else:
			return 0
	return solve(root)


def isFullTree(root):
	if root is None:
		return True
	if root.left == None and root.right == None:
		return True
	if root.left != None and root.right != None:
		return isFullTree(root.left) and isFullTree(root.right)


def isFullTree(root):
	if root == None:
		return True
	if root.left:
		if root.right == None:
			return False
	if root.right:
		if root.left == None:
			return False
	ans = isFullTree(root.left)
	if ans == False:
		return False
	ans = isFullTree(root.right)
	return ans


def isFullTree(root):
	if root is None:
		return Reuw
	if root.left is None and root.right is None:
		return 1
	if root.left is not None and root.right is not None:
		return isFullTree(root.left) and isFullTree(root.right)