Given a Binary Tree of size N, your task is to complete the function countNonLeafNodes(), that should return the count of all the non-leaf nodes of the given binary tree.
Example:
Input: 
Output:
2
Explanation:
Nodes 1 and 2 are the only non leaf nodes.
Your Task:
You don't need to take input or print anything. Your task is to complete the function countNonLeafNodes() that takes root as input and returns the number of non leaf nodes in the tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 ≤ Number of nodes ≤ 10^{5}

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).

Starter code:
#User function Template for python3





# Structure of the node of the tree is as



'''class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None'''













# function should return the count of total number of non leaf nodes in the tree

class Solution:

    def countNonLeafNodes(self, root):

        # add code here

Solutions:
class Solution:

	def countNonLeafNodes(self, root):
		count = 0
		if root is None:
			return 0
		elif root.left is not None or root.right is not None:
			count = 1
		return count + self.countNonLeafNodes(root.left) + self.countNonLeafNodes(root.right)


class Solution:

	def __init__(self):
		self.count = 0

	def countNonLeafNodes(self, root):
		if not root or (not root.right and (not root.left)):
			return 0
		return self.countNonLeafNodes(root.right) + self.countNonLeafNodes(root.left) + 1


class Solution:

	def countNonLeafNodes(self, root):
		num = 0
		if root is None or (root.left is None and root.right is None):
			return num
		else:
			num += self.countNonLeafNodes(root.left)
			num += 1
			num += self.countNonLeafNodes(root.right)
		return num


class Solution:

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


class Solution:

	def countNonLeafNodes(self, root):
		queue = [root]
		ans = 0
		while queue:
			node = queue.pop(0)
			if node.left or node.right:
				ans += 1
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		return ans


class Solution:

	def count(self, root, c):
		if root is None:
			return
		if root.left is None and root.right is None:
			return
		if root.left is not None or root.right is not None:
			c.append(root.data)
		self.count(root.left, c)
		self.count(root.right, c)

	def countNonLeafNodes(self, root):
		c = []
		self.count(root, c)
		return len(c)


class Solution:

	def countNonLeafNodes(self, root):
		stack = [root]
		answer = 0
		while stack:
			node = stack.pop()
			if node.right:
				stack.append(node.right)
			if node.left:
				stack.append(node.left)
			if node.right or node.left:
				answer += 1
		return answer


class Solution:

	def countNonLeafNodes(self, root):
		if root == None or root.left == root.right:
			return 0
		else:
			return 1 + self.countNonLeafNodes(root.left) + self.countNonLeafNodes(root.right)


class Solution:

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


class Solution:

	def countNonLeafNodes(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 0
		leftNonLeaf = self.countNonLeafNodes(root.left)
		rightNonLeaf = self.countNonLeafNodes(root.right)
		return 1 + leftNonLeaf + rightNonLeaf


class Solution:

	def count_leaves(self, root):
		leaves_left = 0
		leaves_right = 0
		if root.left:
			leaves_left = self.count_leaves(root.left)
		if root.right:
			leaves_right = self.count_leaves(root.right)
		if not root.left and (not root.right):
			return 1
		return leaves_left + leaves_right

	def count_nodes(self, root):
		nodes_l = 0
		nodes_r = 0
		if root.left:
			nodes_l = self.count_nodes(root.left)
		if root.right:
			nodes_r = self.count_nodes(root.right)
		if not root.left and (not root.right):
			return 1
		return nodes_l + nodes_r + 1

	def countNonLeafNodes(self, root):
		return self.count_nodes(root) - self.count_leaves(root)


class Solution:

	def countNonLeafNodes(self, root):
		if root.left == None and root.right == None:
			return 0
		if root == None:
			return 0
		global c
		c = 0

		def helper(root):
			global c
			if root == None:
				return
			if root.left == None and root.right == None:
				return
			c += 1
			helper(root.left)
			helper(root.right)
		helper(root)
		return c


class Solution:

	def fun(self, root, arr):
		if root == None:
			return 0
		l = self.fun(root.left, arr)
		r = self.fun(root.right, arr)
		if l == 0 and r == 0:
			pass
		else:
			arr.append(root.data)
		return

	def countNonLeafNodes(self, root):
		arr = []
		self.fun(root, arr)
		return len(arr)


class Solution:

	def countNonLeafNodes(self, root):
		r = 0
		if root:
			if root.left or root.right:
				r += 1
				r += self.countNonLeafNodes(root.left)
				r += self.countNonLeafNodes(root.right)
		return r


class Solution:

	def countNonLeafNodes(self, root):
		l = []
		x = [0]

		def fun(root):
			if root:
				if root.left == None and root.right == None:
					x[0] += 1
				l.append(root.data)
				fun(root.left)
				fun(root.right)
		fun(root)
		return len(l) - x[0]


class Solution:

	def countNonLeafNodes(self, root):
		count = 0
		stack = [root]
		while stack:
			count += 1
			node = stack.pop()
			if node.right is None and node.left is None:
				count -= 1
			if node.right:
				stack.append(node.right)
			if node.left:
				stack.append(node.left)
		return count


class Solution:

	def getSize(self, root, li):
		if root is None:
			return
		self.getSize(root.left, li)
		li[0] += 1
		self.getSize(root.right, li)

	def getNumberOfRoot(self, root, li):
		if root is None:
			return
		self.getNumberOfRoot(root.left, li)
		if root.left is None and root.right is None:
			li[1] += 1
		self.getNumberOfRoot(root.right, li)

	def countNonLeafNodes(self, root):
		li = [0, 0]
		self.getSize(root, li)
		self.getNumberOfRoot(root, li)
		return li[0] - li[1]


class Solution:

	def countNonLeafNodes(self, root):
		self.count = 0

		def count_helper(root):
			if root:
				if root.left or root.right:
					self.count += 1
				count_helper(root.left)
				count_helper(root.right)
		count_helper(root)
		return self.count


class Solution:

	def countNonLeafNodes(self, root):
		q = [root]
		l = []
		while q:
			z = q.pop(0)
			if z.left is not None or z.right is not None:
				l.append(z.data)
			if z.left:
				q.append(z.left)
			if z.right:
				q.append(z.right)
		return len(l)


class Solution:

	def totalNodes(self, root):
		if root is None:
			return 0
		leftTree = self.totalNodes(root.left)
		rightTree = self.totalNodes(root.right)
		return leftTree + rightTree + 1

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

	def countNonLeafNodes(self, root):
		return self.totalNodes(root) - self.leafNodes(root)


class Solution:

	def countNonLeafNodes(self, root):

		def dfs(root):
			if not root:
				return 0
			if not root.left and (not root.right):
				return 0
			else:
				return dfs(root.left) + dfs(root.right) + 1
		ans = dfs(root)
		return ans


class Solution:

	def countNonLeafNodes(self, root):
		if root.right == None and root.left == None:
			return 0
		elif root.left == None:
			return Solution.countNonLeafNodes(self, root.right) + 1
		elif root.right == None:
			return Solution.countNonLeafNodes(self, root.left) + 1
		else:
			return Solution.countNonLeafNodes(self, root.left) + 1 + Solution.countNonLeafNodes(self, root.right)


class Solution:

	def countNonLeafNodes(self, root):
		temp_root = root
		if root == None or (root.left == None and root.right == None):
			return 0
		return 1 + self.countNonLeafNodes(root.left) + self.countNonLeafNodes(root.right)


class Solution:

	def countNonLeafNodes(self, root):
		r = []

		def tr(root, r):
			if root:
				if root.left != None or root.right != None:
					r.append(1)
				tr(root.left, r)
				tr(root.right, r)
			return r
		return sum(tr(root, r))


class Solution:

	def count(self, root, l, l2):
		if root is not None:
			l2.append(root.data)
			if root.left == None and root.right == None:
				l.append(root.data)
			self.count(root.left, l, l2)
			self.count(root.right, l, l2)

	def countNonLeafNodes(self, root):
		l = []
		l2 = []
		self.count(root, l, l2)
		return len(l2) - len(l)


class Solution:

	def countNonLeafNodes(self, root):
		return len(self.non(root, []))

	def non(self, root, value):
		if root == None:
			return
		if root.left or root.right:
			value.append(root.data)
		self.non(root.left, value)
		self.non(root.right, value)
		return value


class Solution:

	def countNonLeafNodes(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 0
		else:
			a = self.countNonLeafNodes(root.left)
			b = self.countNonLeafNodes(root.right)
			return a + b + 1


class Solution:

	def countNonLeafNodes(self, root):
		queue = [root]
		count = 0
		while queue:
			for _ in queue:
				node = queue.pop()
				if node.left or node.right:
					count += 1
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return count


class Solution:

	def countNonLeafNodes(self, root):
		b = []
		c = []
		Solution.bst(root, b, c)
		return abs(len(b) - len(c))

	def bst(root, b, c):
		if root.left == None and root.right == None:
			c.append(root.data)
		if root.left:
			Solution.bst(root.left, b, c)
		b.append(root.data)
		if root.right:
			Solution.bst(root.right, b, c)


class Solution:

	def countNonLeafNodes(self, root):
		stack = []
		tot_count = 0
		leaf_count = 0
		while True:
			if root is not None:
				stack.append(root)
				root = root.left
			else:
				if len(stack) == 0:
					break
				root = stack.pop()
				if root.left is None and root.right is None:
					leaf_count += 1
				tot_count += 1
				root = root.right
		return tot_count - leaf_count


class Solution:

	def countNonLeafNodes(self, root):
		li = []
		rec(root, li)
		return len(li)

def rec(root, li):
	if root != None and (root.left != None or root.right != None):
		li.append(0)
	else:
		return
	if root != None:
		rec(root.left, li)
		rec(root.right, li)


class Solution:

	def countNonLeafNodes(self, root):
		cnt = [0]

		def dp(root):
			if root is None:
				return
			dp(root.left)
			dp(root.right)
			if root.left != None or root.right != None:
				cnt[0] += 1
		dp(root)
		return cnt[0]


class Solution:

	def countNonLeafNodes(self, root):
		c = 0

		def dfs(node):
			nonlocal c
			is_parent = False
			if node.left:
				dfs(node.left)
				is_parent = True
			if node.right:
				dfs(node.right)
				is_parent = True
			if is_parent:
				c += 1
		dfs(root)
		return c


class Solution:

	def countNonLeafNodes(self, root):
		c = []

		def tree(root, c):
			if root == None:
				return
			if root.left != None or root.right != None:
				c += [1]
			tree(root.left, c)
			tree(root.right, c)
		tree(root, c)
		return len(c)


class Solution:

	def countNonLeafNodes(self, root):
		c = []

		def cou(root, c):
			if root == None:
				return
			if root.left != None or root.right != None:
				c.append(1)
			cou(root.left, c)
			cou(root.right, c)
		cou(root, c)
		return len(c)


class Solution:

	def countNonLeafNodes(self, root):
		c = 0

		def mani(root):
			nonlocal c
			if root:
				if root.left == None or root.right == None:
					c += 1
				mani(root.left)
				mani(root.right)
		mani(root)
		return c - 1


class Solution:

	def countNonLeafNodes(self, root):
		(a, b) = (0, 0)

		def mani(root):
			nonlocal a, b
			if root:
				if root.left == None and root.right == None:
					a += 1
				mani(root.left)
				mani(root.right)
				b += 1
		mani(root)
		return b - a


class Solution:

	def countNonLeafNodes(self, root):
		q = []
		count = 0
		q.append(root)
		while len(q) > 0:
			t = q.pop(0)
			if t.left is not None or t.right is not None:
				count += 1
			if t.left is not None:
				q.append(t.left)
			if t.right is not None:
				q.append(t.right)
		return count


class Solution:

	def countNonLeafNodes(self, root):
		que = [root]
		count = 0
		while len(que) != 0:
			root = que.pop(0)
			if root.left != None or root.right != None:
				count += 1
			if root.left != None:
				que.append(root.left)
			if root.right != None:
				que.append(root.right)
		return count


class Solution:

	def countNonLeafNodes(self, root):
		global arr
		arr = []

		def solve(root):
			if root:
				if root.left or root.right:
					arr.append(1)
					solve(root.left)
					solve(root.right)
		solve(root)
		return sum(arr)