Given a Binary Tree of size N, You have to count leaves in it. For example, there are two leaves in following tree
        1
     /      \
   10      39
  /
5
 
Example 1:
Input:
Given Tree is 
               4
             /   \
            8     10
           /     /   \
          7     5     1
         /
        3 
Output:
3
Explanation: 
Three leaves are 3 , 5 and 1.
 
Your Task:
You don't have to take input. Complete the function countLeaves() that takes root node of the given tree as parameter and returns the count of leaves in tree. The printing is done by the driver code.
 
Constraints:
1<= N <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''

# your task is to complete this function

# function should return the count of Leaf node's

# Note: You required to print a new line after every test case

def countLeaves(root):

    # Code here



Solutions:
def countLeaves(root):
	i = 0

	def rec(root):
		nonlocal i
		if root:
			if root.left is None and root.right is None:
				i += 1
			rec(root.right)
			rec(root.left)
	rec(root)
	return i


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


def countLeaves(root):
	if root.left == None and root.right == None:
		return 1
	q = []
	q.append(root)
	ans = 0
	while len(q) > 0:
		top = q.pop(0)
		if top.left is not None:
			q.append(top.left)
		if top.right is not None:
			q.append(top.right)
		if top.left is None and top.right is None:
			ans += 1
	return ans


def countLeaves(root):
	global ans
	ans = [0]

	def in_order(root):
		if root and root.left:
			in_order(root.left)
		if root and (not root.left) and (root.right == None):
			ans[0] = ans[0] + 1
		if root and root.right:
			in_order(root.right)
		return
	in_order(root)
	return ans[0]


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


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


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


def countLeaves(root):
	leaf = 0
	if root is None:
		return 0
	if root.left is None and root.right is None:
		leaf += 1
	lleaf = countLeaves(root.left)
	rleaf = countLeaves(root.right)
	return lleaf + rleaf + leaf


def countLeaves(root):
	q = []
	q.append(root)
	count = 0
	while q:
		for x in range(0, len(q)):
			cur = q[0]
			q.remove(cur)
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)
			if not cur.left and (not cur.right):
				count += 1
	return count


def countLeaves(root):
	a = []
	leaves = 0

	def rec(root):
		nonlocal leaves
		if root:
			rec(root.left)
			a.append(root.data)
			if root.left == None and root.right == None:
				leaves += 1
			rec(root.right)
	rec(root)
	return leaves


def countLeaves(root):
	queue = [root]
	ans = 0
	while queue:
		node = queue.pop(0)
		if not node.left and (not node.right):
			ans += 1
		if node.left:
			queue.append(node.left)
		if node.right:
			queue.append(node.right)
	return ans


def countLeaves(root):

	def tree(node):
		if not node.right and (not node.left):
			return 1
		elif node.right and node.left:
			return tree(node.right) + tree(node.left)
		elif node.right:
			return tree(node.right)
		else:
			return tree(node.left)
	return tree(root)


def countLeaves(root):
	leaf_nodes = 0

	def helper(root):
		if root is None:
			return 0
		left_nodes = helper(root.left)
		right_nodes = helper(root.right)
		if root.left is None and root.right is None:
			return 1
		return left_nodes + right_nodes
	return helper(root)


def countLeaves(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 not node.right and (not node.left):
			answer += 1
	return answer


def count(root, res):
	if root is None:
		return
	if root.left is None and root.right is None:
		res.append(root.data)
	if root:
		count(root.left, res)
		count(root.right, res)

def countLeaves(root):
	res = []
	count(root, res)
	return len(res)


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

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


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

def countLeaves(root):
	if root == None:
		return 0
	return traverseLeaves(root, 0)


def countLeaves(root):
	if root == None:
		return 0
	l = countLeaves(root.left)
	r = countLeaves(root.right)
	if root.left == None and root.right == None:
		return l + r + 1
	else:
		return l + r


def countLeaves(root):
	count = 0
	flagLeft = False
	flagRight = False
	if not root.left == None:
		count += countLeaves(root.left)
	else:
		flagLeft = True
	if not root.right == None:
		count += countLeaves(root.right)
	else:
		flagRight = True
	if flagLeft and flagRight:
		count += 1
	return count


def countLeaves(root):

	def dfs(node):
		if not node:
			return 0
		if not (node.left or node.right):
			return 1
		return dfs(node.left) + dfs(node.right)
	return dfs(root)


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


count = 0

def countLeaves(root):
	if not root:
		return 0
	elif not root.left and (not root.right):
		return 1
	else:
		return countLeaves(root.right) + countLeaves(root.left)


def countLeaves(root):
	return __countLeaves(root)

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


def countLeaves(root):
	count = [0]

	def counting(node):
		if not node.left and (not node.right):
			count[0] += 1
			return
		if node.left:
			counting(node.left)
		if node.right:
			counting(node.right)
	counting(root)
	return count[0]


def countLeaves(root):

	def h(root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		a = h(root.left)
		b = h(root.right)
		return a + b
	return h(root)


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


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


def countLeaves(root):
	if root == None:
		return 0
	elif root.left == None and root.right == None:
		return 1
	else:
		ls = countLeaves(root.left)
		rs = countLeaves(root.right)
		return ls + rs


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


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

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


def fun(root, c):
	if root == None:
		return 0
	l = fun(root.left, c)
	r = fun(root.right, c)
	if l == 0 and r == 0:
		c.append(1)

def countLeaves(root):
	c = []
	fun(root, c)
	return sum(c)


def countLeaves(root):
	level = [root]
	leaves = []
	while level:
		next = []
		for node in level:
			if node.right:
				next.append(node.right)
			if node.left:
				next.append(node.left)
			elif node.right == None:
				leaves.append(node)
		level = next
	return len(leaves)


def countLeaves(root):
	tot = 0

	def count(node):
		nonlocal tot
		if node is None:
			return
		if not node.left and (not node.right):
			tot += 1
		count(node.left)
		count(node.right)
	count(root)
	return tot