Given a binary tree of size N, you have to count number of nodes in it. For example, count of nodes in below tree is 4.
        1
     /      \
   10      39
  /
5
Input:
First line of input contains the number of test cases T. For each test case, there will be only a single line of input which is a string representing the tree as described below: 
	
	The values in the string are in the order of level order traversal of the tree where, numbers denote node values, and a character “N” denotes NULL child.
	
	
	For example:
	
	For the above tree, the string will be: 1 2 3 N N 4 6 N 5 N N 7 N
	
Output:
For each testcase in new line, print the number of nodes.
User Task:
Since this is a functional problem you don't have to worry about input, you just have to complete the function getSize().
Constraints:
1 <= T <= 30
1 <= N <= 10^{4}
Example:
Input:
2
1 2 3
10 5 9 N 1 3 6 
Output:
3
6
Explanation:
Testcase 2: Given Tree is :
                                10
                             /        \
                           5          9
                             \       /     \
                              1    3       6
There are six nodes in the tree .

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: # Your task to complete this function

# function should return size of the binary tree as integer

def getSize(node):

    # code here

Solutions:
def getSize(node):
	if not node:
		return 0
	return 1 + getSize(node.left) + getSize(node.right)


def getSize(node):
	if node is None:
		return 0
	else:
		size = 1
	return size + getSize(node.left) + getSize(node.right)


def getSize(root):
	sum = 0
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return 1
	lsum = getSize(root.left)
	rsum = getSize(root.right)
	return 1 + lsum + rsum


def getSize(node):
	if node is None:
		return 0
	left = getSize(node.left)
	right = getSize(node.right)
	count = 0
	if node is not None:
		count = 1
	return left + right + count


def getSize(node):

	def re(w, i):
		if w:
			i += 1
			i = re(w.right, i)
			i = re(w.left, i)
		return i
	return re(node, 0)


def getSize(node):
	if node is None:
		return 0
	l = getSize(node.left)
	r = getSize(node.right)
	return l + r + 1


def traverse(root):
	traversal = []
	if root is not None:
		traversal.extend(traverse(root.left))
		traversal.append(root.data)
		traversal.extend(traverse(root.right))
	return traversal

def getSize(node):
	if root is not None:
		data = traverse(root)
		return len(data)
	else:
		return 0


def getSize(node):
	queue = [node]
	ans = []
	while queue:
		node = queue.pop(0)
		ans.append(node.data)
		if node.left:
			queue.append(node.left)
		if node.right:
			queue.append(node.right)
	return len(ans)


def getSize(node):
	if node is None:
		return 0
	return 1 + getSize(node.left) + getSize(node.right)


def getSize(root):
	stack = []
	sum = 0
	while True:
		if root:
			sum += 1
			stack.append(root)
			root = root.left
		elif stack:
			root = stack.pop()
			root = root.right
		else:
			break
	return sum


def getSize(node):
	res = []
	temp = []
	current = node
	counter = 0
	total = 0
	max_temp = 0
	node_count = 0
	while True:
		if current is not None:
			node_count += 1
			if current.left is None and current.right is None:
				counter += 1
			res.append(current.data)
			temp.append(current)
			if max_temp < len(temp):
				max_temp = len(temp)
			total = total + current.data
			current = current.left
		elif temp:
			current = temp.pop()
			current = current.right
		else:
			break
	return node_count


def getSize(root):
	if root is None:
		return 0
	node_left = getSize(root.left)
	node_right = getSize(root.right)
	return 1 + node_left + node_right


def getSize(node):
	count = 0
	if node == None:
		return 0
	else:
		count += getSize(node.left)
		count += 1
		count += getSize(node.right)
	return count


def cou(node, res):
	if node is None:
		return
	res.append(node.data)
	cou(node.left, res)
	cou(node.right, res)

def getSize(node):
	res = []
	cou(node, res)
	return len(res)


def getSize(node):
	stack = []
	n = 0
	current = root
	while True:
		if current:
			stack.append(current)
			current = current.left
		elif stack:
			node = stack.pop()
			n += 1
			current = node.right
		else:
			break
	return n


def getSize(node):
	if node == None:
		return 0
	if node.left == None and node.right == None:
		return 1
	return getSize(node.left) + getSize(node.right) + 1


def getSize(node):
	if node == None:
		return 0
	lh = 1 + getSize(node.left)
	rh = 1 + getSize(node.right)
	return lh + rh - 1


def getSize(node):
	if not node:
		return 0
	left_count = getSize(node.left)
	right_count = getSize(node.right)
	return left_count + right_count + 1


def getSize(node):
	if node == None:
		return 0
	left_nodes = getSize(node.left)
	right_nodes = getSize(node.right)
	return left_nodes + right_nodes + 1


def getSize(node):

	def h(root):
		if not root:
			return 0
		return 1 + h(root.left) + h(root.right)
	return h(root)


def getSize(node):
	from collections import deque
	q = deque()
	q.append(root)
	count = 0
	while q:
		current = q.popleft()
		count += 1
		if current.left:
			q.append(current.left)
		if current.right:
			q.append(current.right)
	return count


def getSize(node):
	if node == None:
		return 0
	else:
		ls = getSize(node.left)
		rs = getSize(node.right)
		return ls + rs + 1


def getSize(root):
	global c
	c = 0

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


def fun(root, l):
	if root:
		l.append(root.data)
		fun(root.left, l)
		fun(root.right, l)

def getSize(node):
	l = []
	fun(root, l)
	return len(l)


def getSize(node):
	if node is None:
		return 0
	leftNodes = getSize(node.left)
	rightNodes = getSize(node.right)
	return leftNodes + rightNodes + 1


def getSize(node):
	r = 0
	if node:
		r += getSize(node.left)
		r += 1
		r += getSize(node.right)
	return r


def getSize(node):
	stack = [node]
	count = 0
	while stack:
		root = stack.pop()
		count += 1
		if root.right:
			stack.append(root.right)
		if root.left:
			stack.append(root.left)
	return count


def getSize(node):
	count = 0
	if node is None:
		return count
	a = getSize(node.left)
	count += 1
	b = getSize(node.right)
	count += 1
	return a + b + 1


def getSize(node):
	size = []
	size_helper(root, size)
	return len(size)

def size_helper(root, count):
	if root:
		count.append(root.data)
		size_helper(root.left, count)
		size_helper(root.right, count)


def getSize(node):
	return 1 + getSize(node.left) + getSize(node.right) if node else 0


def getSize(node):

	def t(rt):
		if rt is None:
			return 0
		else:
			return 1 + t(rt.left) + t(rt.right)
	return t(root)


def getSize(node):
	if node is None:
		return 0
	leftTree = getSize(node.left)
	rightTree = getSize(node.right)
	return 1 + leftTree + rightTree


def getSize(node):
	if node is None:
		return 0
	elif node.left is None and node.right is None:
		return 1
	return 1 + getSize(node.left) + getSize(node.right)


def getSize(node):
	re = []

	def trav(r):
		if r.left is not None:
			trav(r.left)
		if r.right is not None:
			trav(r.right)
		re.append(r.data)
	trav(root)
	return len(re)


def getSize(node):
	if node is None:
		return 0
	left_count = getSize(node.left)
	right_count = getSize(node.right)
	return left_count + right_count + 1


def getSize(root):
	return getSize(root.left) + 1 + getSize(root.right) if root else 0


def getSize(node):
	l = []

	def ino(node):
		if node is not None:
			ino(node.left)
			l.append(node.data)
			ino(node.right)
	ino(node)
	return len(l)


def getSize(node):

	def size(root):
		if root == None:
			return 0
		left = size(root.left)
		right = size(root.right)
		return left + right + 1
	return size(node)


def getSize(root):
	if root == None:
		return 0
	return getSize(root.left) + getSize(root.right) + 1


def getSize(node):
	count = 0

	def size(node):
		nonlocal count
		if node == None:
			return None
		count += 1
		if node.left:
			size(node.left)
		if node.right:
			size(node.right)
	size(node)
	return count


def getSize(node):
	return count(node, [])

def count(root, value):
	if root == None:
		return 0
	count(root.left, value)
	value.append(root.data)
	count(root.right, value)
	return len(value)


def getSize(node):
	return count(node)

def count(root):
	if root == None:
		return 0
	return count(root.left) + count(root.right) + 1


def getSize(node):

	def count(node):
		if node is None:
			return 0
		left_node = count(node.left)
		right_node = count(node.right)
		return 1 + left_node + right_node
	return count(node)


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


def getSize(node):
	count = 0
	stack = []
	while stack or node:
		while node:
			count += 1
			stack.append(node)
			node = node.left
		el = stack.pop()
		node = el.right
	return count


def getSize(node):
	count = 1
	queue = [node]
	while queue:
		for _ in range(len(queue)):
			el = queue.pop(0)
			if el.left != None:
				count += 1
				queue.append(el.left)
			if el.right != None:
				count += 1
				queue.append(el.right)
	return count


def getSize(node):
	nodes = 0

	def inorder(node):
		nonlocal nodes
		if not node:
			return
		inorder(node.left)
		nodes += 1
		inorder(node.right)
	inorder(node)
	return nodes


def getSize(node):
	b = []
	bst(root, b)
	return len(b)

def bst(root, b):
	if root.left:
		bst(root.left, b)
	b.append(root.data)
	if root.right:
		bst(root.right, b)


def getSize(root):
	count = 0
	stack = []
	while True:
		if root is not None:
			stack.append(root)
			root = root.left
		else:
			if len(stack) == 0:
				break
			root = stack.pop()
			count += 1
			root = root.right
	return count