You are given the root of a complete binary tree. Your task is to find the count of nodes.
A complete binary tree is a binary tree whose, all levels except the last one are completely filled, the last level may or may not be completely filled and Nodes in the last level are as left as possible.
Design an algorithm that runs better than O(n).
Example:
Input: 
root = [1,2,3,4,5,6]
Output: 
6
Explanation: 
There are a total of 6 nodes in the given tree.
Your Task:
Complete the function int cnt_nodes(Node *root), which takes the pointer of the root of the given Binary tree and returns the count of its number of nodes.
Expected Time Complexity: O((LogN)^{2}).
Expected Auxiliary Space: O(Log N).
Constraints:
0 <= N (number of nodes) <= 5 * 10^{4} 
0 <= value of nodes <= 5 * 10^{4}
The tree is guaranteed to be complete.

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def init(self, val):

        self.data = val

        self.left = None

        self.right = None

'''

class Solution:

    def countNodes(self, root):

        #code here

Solutions:
class Solution:

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


class Solution:

	def countNodes(self, root):
		if root == None:
			return 0
		ln = self.countNodes(root.left)
		rn = self.countNodes(root.right)
		treecount = ln + rn + 1
		return treecount


class Solution:

	def countNodes(self, root):
		lst = [root]
		A = []
		while lst:
			if lst[0].left:
				lst.append(lst[0].left)
			if lst[0].right:
				lst.append(lst[0].right)
			A.append(lst.pop(0))
		return len(A)


class Solution:

	def get_leftheight(self, root):
		count = 0
		while root is not None:
			root = root.left
			count += 1
		return count

	def get_rightheight(self, root):
		count = 0
		while root is not None:
			root = root.right
			count += 1
		return count

	def countNodes(self, root):
		if root is None:
			return 0
		left_height = self.get_leftheight(root.left)
		right_height = self.get_rightheight(root.right)
		if left_height == right_height:
			return 2 ** (left_height + 1) - 1
		return self.countNodes(root.left) + self.countNodes(root.right) + 1


class Solution:

	def cn(self, root, k):
		if not root:
			return
		k.append(root.data)
		self.cn(root.right, k)
		self.cn(root.left, k)

	def countNodes(self, root):
		k = []
		self.cn(root, k)
		return len(k)


from collections import deque

class Solution:

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


class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

class Solution:

	def countNodes(self, root):
		if not root:
			return 0
		height = 0
		node = root
		while node.left:
			height += 1
			node = node.left
		left = 1
		right = 2 ** height
		while left <= right:
			mid = (left + right) // 2
			if self.exists(root, height, mid):
				left = mid + 1
			else:
				right = mid - 1
		return 2 ** height - 1 + left - 1

	def exists(self, node, height, pos):
		left = 1
		right = 2 ** height
		for _ in range(height):
			mid = (left + right) // 2
			if pos <= mid:
				node = node.left
				right = mid
			else:
				node = node.right
				left = mid + 1
		return node is not None


class Solution:

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

		def fun(root):
			if root:
				l[0] = l[0] + 1
				fun(root.left)
				fun(root.right)
		fun(root)
		return l[0]


class Solution:

	def countNodes(self, root):

		def inorder(root, l):
			if root is None:
				return
			if root.left:
				root.left = inorder(root.left, l)
			l.append(root.data)
			if root.right:
				root.right = inorder(root.right, l)
		l = []
		inorder(root, l)
		return len(l)


class Solution:

	def countNodes(self, root):
		(l, r) = (0, 0)
		curr = root
		while curr != None:
			curr = curr.left
			l += 1
		curr = root
		while curr != None:
			curr = curr.right
			r += 1
		if l == r:
			return pow(2, l) - 1
		else:
			return self.countNodes(root.left) + self.countNodes(root.right) + 1


class Solution:

	def left_height(self, root):
		count = 1
		while root:
			count += 1
			root = root.left
		return count

	def right_height(self, root):
		count = 1
		while root:
			count += 1
			root = root.right
		return count

	def countNodes(self, root):
		if not root:
			return 0
		left = self.left_height(root.left)
		right = self.right_height(root.right)
		if left == right:
			return 2 ** left - 1
		return 1 + self.countNodes(root.left) + self.countNodes(root.right)


class Solution:

	def countNodes(self, root):
		if root == None:
			return []
		q = []
		q.append(root)
		ans = []
		while len(q) != 0:
			size = len(q)
			tmp = []
			while size != 0:
				curr = q.pop(0)
				ans.append(curr.data)
				if curr.left != None:
					q.append(curr.left)
				if curr.right != None:
					q.append(curr.right)
				size -= 1
		return len(ans)


class Solution:

	def countNodes(self, root):
		ans = 0

		def f(root):
			nonlocal ans
			if root is None:
				return
			ans += 1
			f(root.left)
			f(root.right)
		f(root)
		return ans


class Solution:

	def leftHeight(self, root):
		hight = 0
		while root:
			root = root.left
			hight += 1
		return hight

	def rightHeight(self, root):
		hight = 0
		while root:
			root = root.right
			hight += 1
		return hight

	def countNodes(self, root):
		if root == None:
			return 0
		lh = self.leftHeight(root)
		rh = self.rightHeight(root)
		if lh == rh:
			return (1 << lh) - 1
		return 1 + self.countNodes(root.left) + self.countNodes(root.right)


class Solution:

	def countNodes(self, root):
		stack = []
		curr = root
		post = []
		while curr != None or len(stack) > 0:
			if curr != None:
				stack.append(curr)
				curr = curr.left
			else:
				temp = stack[-1].right
				if temp == None:
					temp = stack.pop()
					post.append(temp.data)
					while len(stack) > 0 and temp == stack[-1].right:
						temp = stack.pop()
						post.append(temp.data)
				else:
					curr = temp
		return len(post)


class Solution:

	def countNodes(self, root):
		self.ans = 0

		def dfs(root):
			if not root:
				return
			self.ans += 1
			(dfs(root.left), dfs(root.right))
		dfs(root)
		return self.ans


class Solution:

	def countNodes(self, root):
		res = []

		def two(root):
			if not root:
				return
			two(root.left)
			res.append(root.data)
			two(root.right)
		two(root)
		return len(res)


class Solution:

	def countNodes(self, root):
		if root == None:
			return 0
		else:
			ls = self.countNodes(root.left)
			rs = self.countNodes(root.right)
			return ls + rs + 1


class Solution:

	def countNodes(self, root):
		if root == None:
			return 0
		if root.left is None and root.right is None:
			return 1
		l = self.countNodes(root.left)
		r = self.countNodes(root.right)
		return l + r + 1


class Solution:

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


class Solution:

	def countNodes(self, root):
		if root is None:
			return 0
		leftNodes = self.countNodes(root.left)
		rightNodes = self.countNodes(root.right)
		return leftNodes + rightNodes + 1


class Solution:

	def countNodes(self, root):

		def findLHeight(node):
			h = 0
			while node:
				h += 1
				node = node.left
			return h

		def findRHeight(node):
			r = 0
			while node:
				r += 1
				node = node.right
			return r

		def f(node):
			if node is None:
				return 0
			l = findLHeight(node)
			r = findRHeight(node)
			if l == r:
				return 2 ** l - 1
			return 1 + f(node.left) + f(node.right)
		return f(root)


class Solution:

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


class Solution:

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

		def find(root):
			if root:
				cnt[0] += 1
				find(root.left)
				find(root.right)
			return
		find(root)
		return cnt[0]


class Solution:

	def countNodes(self, root):
		queue = [root]
		val = 0
		while queue:
			level = []
			for i in queue:
				if i == None:
					continue
				val += 1
				level.append(i.left)
				level.append(i.right)
			queue = level
		return val


class Solution:

	def countNodes(self, root):
		rh = 0
		lh = 0
		a = root
		while a != None:
			lh += 1
			a = a.left
		a = root
		while a != None:
			rh += 1
			a = a.right
		if rh == lh:
			return int(2 ** rh) - 1
		return 1 + self.countNodes(root.left) + self.countNodes(root.right)


class Solution:
	leaf = 0
	bi = 0

	def gen(self, root):
		if root.left == None or root.right == None:
			self.bi += 1
			if root.left:
				self.leaf += 1
			if root.right:
				self.leaf += 1
			return
		self.bi += 1
		self.gen(root.left)
		self.gen(root.right)

	def countNodes(self, root):
		self.leaf = 0
		self.bi = 0
		self.gen(root)
		return self.bi + self.leaf


class Solution:

	def countNodes(self, root):

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


class Solution:

	def countNodes(self, root):

		def findMaxLevel(node, isLeftMove):
			if node is None:
				return 0
			if isLeftMove:
				return 1 + findMaxLevel(node.left, isLeftMove)
			return 1 + findMaxLevel(node.right, isLeftMove)
		leftMove = findMaxLevel(root, True)
		rightMove = findMaxLevel(root, False)
		if leftMove == rightMove:
			return 2 ** leftMove - 1
		return 1 + self.countNodes(root.left) + self.countNodes(root.right)


class Solution:

	def countNodes(self, root):
		if not root:
			return 0
		l = self.findleft(root)
		r = self.findright(root)
		if l == r:
			return 2 ** l - 1
		else:
			return 1 + self.countNodes(root.left) + self.countNodes(root.right)

	def findleft(self, node):
		if not node:
			return 0
		c = 0
		while node:
			c += 1
			node = node.left
		return c

	def findright(self, node):
		if not node:
			return 0
		c = 0
		while node:
			c += 1
			node = node.right
		return c


class Solution:

	def countNodes(self, root):
		q = []
		q.append(root)
		ret = 0
		while q:
			n = len(q)
			ret += n
			while n > 0:
				tmp = q.pop(0)
				if tmp.left:
					q.append(tmp.left)
				if tmp.right:
					q.append(tmp.right)
				n -= 1
		return ret


class Solution:

	def countNodes(self, root):
		st = [root]
		c = 0
		while st:
			ob = st.pop()
			c += 1
			if ob.left:
				st.append(ob.left)
			if ob.right:
				st.append(ob.right)
		return c


from collections import deque

class Solution:

	def countNodes(self, root):
		if not root:
			return 0
		count = 0
		q = deque()
		q.appendleft((root, 1))
		while q:
			count += q[0][1] - q[-1][1] + 1
			temp = deque()
			while q:
				(root, ind) = q.pop()
				if root.left:
					temp.appendleft((root.left, ind * 2))
				if root.right:
					temp.appendleft((root.right, ind * 2 + 1))
			q = temp
		return count


class Solution:

	def lh(self, root):
		if not root:
			return 0
		return 1 + self.lh(root.left)

	def rh(self, root):
		if not root:
			return 0
		return 1 + self.rh(root.right)

	def countNodes(self, root):
		if not root:
			return 0
		lh = self.lh(root)
		rh = self.rh(root)
		if lh == rh:
			return 2 ** lh - 1
		return 1 + self.countNodes(root.left) + self.countNodes(root.right)


class Solution:

	def countNodes(self, root):

		def count_complete_tree(root):
			if root == None:
				return 0
			(lh, rh) = (0, 0)
			itr = root
			while itr:
				lh += 1
				itr = itr.left
			itr = root
			while itr:
				rh += 1
				itr = itr.right
			if lh == rh:
				import math
				return int(math.pow(2, lh)) - 1
			return 1 + count_complete_tree(root.left) + count_complete_tree(root.right)
		return count_complete_tree(root)


class Solution:

	def countNodes(self, root):
		global c
		c = 0

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


class Solution:

	def countNodes(self, root):

		def leftheight(root):
			ans = 0
			cur = root
			while cur:
				ans += 1
				cur = cur.left
			return ans

		def rightheight(root):
			ans = 0
			cur = root
			while cur:
				ans += 1
				cur = cur.right
			return ans

		def find(root):
			if root == None:
				return 0
			left = leftheight(root)
			right = rightheight(root)
			if left == right:
				return 2 ** left - 1
			else:
				return 1 + find(root.left) + find(root.right)
		return find(root)


def leftheight(root):
	if root == None:
		return
	height = 0
	while root:
		height += 1
		root = root.left
	return height

def rightheight(root):
	if root == None:
		return 0
	height = 0
	while root:
		height += 1
		root = root.right
	return height

class Solution:

	def countNodes(self, root):
		if root == None:
			return 0
		lh = leftheight(root)
		rh = rightheight(root)
		if lh == rh:
			return (1 << lh) - 1
		return 1 + self.countNodes(root.left) + self.countNodes(root.right)


class Solution:

	def countNodes(self, root):
		if not root:
			return 0
		ls = self.countL(root)
		rs = self.countR(root)
		if ls == rs:
			return 2 ** ls - 1
		else:
			return 1 + self.countNodes(root.left) + self.countNodes(root.right)

	def countL(self, root):
		if not root:
			return 0
		h = 0
		while root:
			root = root.left
			h += 1
		return h

	def countR(self, root):
		if not root:
			return 0
		h = 0
		while root:
			root = root.right
			h += 1
		return h


class Solution:

	def countNodes(self, root):
		if root == None:
			return 0
		else:
			num_left_nodes = self.countNodes(root.left)
			num_right_nodes = self.countNodes(root.right)
			return 1 + num_left_nodes + num_right_nodes


class Solution:

	def countNodes(self, root):
		if not root:
			return 0
		return self.countNodesUtil(root)

	def countNodesUtil(self, root):
		if not root:
			return 0
		l = self.countL(root)
		r = self.countR(root)
		if l == r:
			return 2 ** l - 1
		else:
			return 1 + self.countNodesUtil(root.left) + self.countNodesUtil(root.right)

	def countL(self, node):
		if not node:
			return 0
		lh = 0
		while node:
			lh += 1
			node = node.left
		return lh

	def countR(self, node):
		if not node:
			return 0
		rh = 0
		while node:
			rh += 1
			node = node.right
		return rh


from collections import deque

class Solution:

	def countNodes(self, root):
		queue = deque()
		count = 0
		if not root:
			return 0
		queue.append(root)
		while queue:
			e = queue.pop()
			count += 1
			if e.left:
				queue.append(e.left)
			if e.right:
				queue.append(e.right)
		return count


class Solution:

	def countNodes(self, root):
		if not root:
			return 0
		l = self.countNodes(root.left)
		r = self.countNodes(root.right)
		return l + r + 1


class Solution:

	def countNodes(self, root):
		if not root:
			return 0
		lh = helperleft(root)
		rh = helperright(root)
		if lh == rh:
			return 2 ** lh - 1
		lc = self.countNodes(root.left)
		rc = self.countNodes(root.right)
		return 1 + lc + rc

def helperleft(curr):
	c = 0
	while curr:
		c += 1
		curr = curr.left
	return c

def helperright(curr):
	c = 0
	while curr:
		c += 1
		curr = curr.right
	return c


from collections import deque

class Solution:

	def countNodes(self, root):
		count = 0
		q = deque([root])
		while q:
			n = len(q)
			count += n
			for i in range(n):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return count


class Solution:

	def countNodes(self, root):
		if not root:
			return 0

		def lheight(node):
			if not node:
				return 0
			return 1 + lheight(node.left)

		def rheight(node):
			if not node:
				return 0
			return 1 + rheight(node.right)
		(l, r) = (lheight(root), rheight(root))
		if l > r:
			return 1 + self.countNodes(root.left) + self.countNodes(root.right)
		else:
			return 2 ** l - 1


class Solution:

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

	def countNodes(self, root):
		if root is None:
			return 0
		self.count = 0
		self.helper(root)
		return self.count


class Solution:

	def countNodes(self, root):
		c = [0]

		def count(root):
			if root:
				count(root.left)
				c[0] = c[0] + 1
				count(root.right)
		count(root)
		return c[0]


class Solution:

	def countNodes(self, root):
		if root == None:
			return 0
		else:
			x = self.countNodes(root.left)
			y = self.countNodes(root.right)
			return x + y + 1


class Solution:

	def countNodes(self, root):
		if not root:
			return 0
		leftDepth = self.getDepth(root.left)
		rightDepth = self.getDepth(root.right)
		if leftDepth == rightDepth:
			return pow(2, leftDepth) + self.countNodes(root.right)
		else:
			return pow(2, rightDepth) + self.countNodes(root.left)

	def getDepth(self, root):
		if not root:
			return 0
		return 1 + self.getDepth(root.left)


class Solution:

	def __init__(self):
		self.c = 0

	def inorder(self, root):
		if root is None:
			return
		self.c = self.c + 1
		self.inorder(root.left)
		self.inorder(root.right)

	def countNodes(self, root):
		self.inorder(root)
		return self.c


class Solution:

	def countNodes(self, root):

		def findHeightLeft(node):
			ht = 0
			while node:
				ht += 1
				node = node.left
			return ht

		def findHeightRight(node):
			ht = 0
			while node:
				ht += 1
				node = node.right
			return ht

		def fn(root):
			if not root:
				return 0
			(lh, rh) = (findHeightLeft(root), findHeightRight(root))
			if lh == rh:
				return (1 << lh) - 1
			return 1 + fn(root.left) + fn(root.right)
		return fn(root)