Given a Binary Tree, find the maximum width of it. Maximum width is defined as the maximum number of nodes at any level.
For example, the maximum width of the following tree is 4 as there are 4 nodes at the 3^{rd} level.
          1
       /     \
     2        3
   /    \    /    \
  4    5   6    7
    \
      8
Example 1:
Input:
       1
     /    \
    2      3
Output: 2
On the first level there is only
one node 1
On the second level there are
two nodes 2, 3 clearly it is the 
maximum number of nodes at any level
Example 2:
Input:
        10
      /     \
    20      30
   /    \
  40    60
Output: 2
There is one node on level 1(10)
There is two node on level 2(20, 30)
There is two node on level 3(40, 60)
Hence the answer is 2
Your Task:
You don't have to read any input. Complete the function getMaxWidth() that takes the node as a parameter and returns the maximum width. The driver code does the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Width of the tree).
Constraints:
1 <= Number of Nodes<= 10^{5}
0 <= nodes values <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

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:

    #Function to get the maximum width of a binary tree.

    def getMaxWidth(self,root):

       

        #code here



Solutions:
class Solution:

	def getMaxWidth(self, root):
		d = {}
		l = []
		level = 1
		self.helper(root, level, d)
		for i in d:
			l.append(len(d[i]))
		return max(l)

	def helper(self, root, level, d):
		if not root:
			return 0
		if level not in d:
			d[level] = [root.data]
		else:
			d[level].append(root.data)
		self.helper(root.left, level + 1, d)
		self.helper(root.right, level + 1, d)


class Solution:

	def getMaxWidth(self, root):
		stack = []
		if root is None:
			return 0
		stack.append(root)
		stack.append(None)
		count = 0
		max_width = 0
		while len(stack) != 1:
			node = stack.pop(0)
			if node != None:
				count += 1
				if node.left:
					stack.append(node.left)
				if node.right:
					stack.append(node.right)
			else:
				max_width = max(count, max_width)
				count = 0
				stack.append(None)
		max_width = max(count, max_width)
		return max_width


class Solution:

	def getMaxWidth(self, root):
		q = [root]
		res = 0
		while q:
			l = len(q)
			res = max(res, l)
			for i in range(l):
				p = q.pop(0)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
		return res


class Solution:

	def getMaxWidth(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		maxwidth = 0
		queue = [[root]]
		while queue:
			level = queue.pop(0)
			temp = []
			for node in level:
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
			if temp:
				maxwidth = max(len(temp), maxwidth)
				queue.append(temp)
		return maxwidth


from collections import deque

class Node:

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

class Solution:

	def getMaxWidth(self, root):
		if root is None:
			return 0
		max_width = 0
		queue = deque()
		queue.append(root)
		while queue:
			level_width = len(queue)
			max_width = max(max_width, level_width)
			for _ in range(level_width):
				node = queue.popleft()
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return max_width


from collections import deque

class Solution:

	def getMaxWidth(self, root):
		maxw = 0
		if root is None:
			return maxw
		queue = deque()
		queue.append(root)
		while len(queue) != 0:
			size = len(queue)
			maxw = max(maxw, size)
			for i in range(size):
				top = queue[0]
				queue.popleft()
				if top.left is not None:
					queue.append(top.left)
				if top.right is not None:
					queue.append(top.right)
		return maxw


from collections import deque

class Solution:

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


class Solution:

	def getMaxWidth(self, root):
		(q, ans) = ([], 0)
		q.append(root)
		while len(q) != 0:
			l = len(q)
			ans = max(ans, l)
			for i in range(l):
				temp = q.pop(0)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
		return ans


class Solution:

	def getMaxWidth(self, root):
		if root is None:
			return 0
		q = []
		maxWidth = 0
		q.insert(0, root)
		while q != []:
			count = len(q)
			maxWidth = max(count, maxWidth)
			while count > 0:
				count = count - 1
				temp = q[-1]
				q.pop()
				if temp.left is not None:
					q.insert(0, temp.left)
				if temp.right is not None:
					q.insert(0, temp.right)
		return maxWidth


class Solution:

	def getMaxWidth(self, root):
		maxWidth = 0
		h = self.maxDepth(root)
		for i in range(1, h + 1):
			width = self.getWidth(root, i)
			if width > maxWidth:
				maxWidth = width
		return maxWidth

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

	def getWidth(self, root, level):
		if root is None:
			return 0
		if level == 1:
			return 1
		elif level > 1:
			return self.getWidth(root.left, level - 1) + self.getWidth(root.right, level - 1)


import queue

class Solution:

	def getMaxWidth(self, root):
		maxlen = 0
		q = queue.Queue()
		if not root:
			return 0
		q.put(root)
		while q.qsize():
			currlen = q.qsize()
			for i in range(currlen):
				node = q.get()
				if node.left:
					q.put(node.left)
				if node.right:
					q.put(node.right)
			maxlen = max(maxlen, currlen)
		return maxlen


class Solution:

	def getMaxWidth(self, root):
		if root is None:
			return []
		result = []
		final = []
		queue = deque([root])
		level = 0
		max1 = 0
		while queue:
			level_size = len(queue)
			level_nodes = []
			for _ in range(level_size):
				node = queue.popleft()
				level_nodes.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			max1 = max(max1, len(level_nodes))
			result.append(level_nodes)
			level += 1
		return max1


class Solution:

	def getMaxWidth(self, root):
		if root is None:
			return 0
		max_width = float('-inf')
		q = deque()
		q.append(root)
		while q:
			count = len(q)
			max_width = max(max_width, count)
			for _ in range(count):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return max_width


class Solution:

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


class Solution:

	def getMaxWidth(self, root):

		def getMaxWidthUtil(root, visited, level):
			nonlocal max_width
			if not root:
				return
			if len(visited) < level:
				visited.append(1)
			else:
				visited[level - 1] += 1
			max_width = max(visited[level - 1], max_width)
			getMaxWidthUtil(root.left, visited, level + 1)
			getMaxWidthUtil(root.right, visited, level + 1)
		max_width = 0
		visited = []
		getMaxWidthUtil(root, visited, 1)
		return max_width


class Solution:

	def getMaxWidth(self, root):
		que = []
		ans = 0
		que.append(root)
		if root is None:
			return []
		while len(que) != 0:
			size = len(que)
			tmp = []
			while size != 0:
				current = que.pop(0)
				tmp.append(current.data)
				if current.left != None:
					que.append(current.left)
				if current.right != None:
					que.append(current.right)
				size -= 1
			if len(tmp) > ans:
				ans = len(tmp)
		return ans


class Solution:

	def getMaxWidth(self, root):
		queue = [root]
		answer = 0
		while queue:
			size = len(queue)
			if size > answer:
				answer = size
			for i in range(size):
				node = queue.pop(0)
				if node.right:
					queue.append(node.right)
				if node.left:
					queue.append(node.left)
		return answer


class Solution:

	def getMaxWidth(self, root):

		def levelOrderTraversal(root):
			ans = []
			queue = []
			queue.append(root)
			while queue:
				level = []
				for i in range(len(queue)):
					root = queue[0]
					queue.pop(0)
					if root.left:
						queue.append(root.left)
					if root.right:
						queue.append(root.right)
					level.append(root.data)
				ans.append(level)
			maxWidth = 0
			for i in range(len(ans)):
				maxWidth = max(maxWidth, len(ans[i]))
			return maxWidth
		return levelOrderTraversal(root)


class Solution:

	def getMaxWidth(self, root):
		res = 0
		if root is None:
			return 0
		q = deque()
		q.append(root)
		while q:
			count = len(q)
			res = max(res, count)
			for i in range(count):
				curr = q.popleft()
				if curr.left != None:
					q.append(curr.left)
				if curr.right != None:
					q.append(curr.right)
		return res


class Solution:

	def getMaxWidth(self, root):
		w = 0
		queue = [root]
		level = []
		res = []
		while queue != [] and root is not None:
			l = []
			for node in queue:
				l.append(node.data)
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			if w < len(l):
				w = len(l)
			queue = level
			level = []
		return w


class Solution:

	def getMaxWidth(self, root):
		if root == None:
			return
		res = 0
		q = [root]
		while len(q) > 0:
			n = len(q)
			if n > res:
				res = n
			for i in range(n):
				temp = q.pop(0)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
		return res


def level_order(root):
	res = []
	q = []
	q.append(root)
	while q:
		count = len(q)
		p = []
		while count:
			temp = q.pop(0)
			p.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
			count -= 1
		res.append(p)
	return res

class Solution:

	def getMaxWidth(self, root):
		res = level_order(root)
		maxi = 0
		for i in res:
			if len(i) > maxi:
				maxi = len(i)
		return maxi


from collections import deque

class Solution:

	def getMaxWidth(self, root):
		maxlength = 0
		dQ = deque()
		dQ.append(root)
		while dQ:
			times = len(dQ)
			maxlength = max(maxlength, times)
			while times:
				holdnode = dQ.popleft()
				if holdnode.left != None:
					dQ.append(holdnode.left)
				if holdnode.right != None:
					dQ.append(holdnode.right)
				times -= 1
		return maxlength


class Solution:

	def getT(self, root, dic, dep):
		if not root:
			return
		try:
			ar = dic[dep]
			ar.append(root.data)
			dic[dep] = ar
		except:
			dic[dep] = [root.data]
		self.getT(root.right, dic, dep + 1)
		self.getT(root.left, dic, dep + 1)

	def getMaxWidth(self, root):
		dic = {}
		self.getT(root, dic, 1)
		maxx = 1
		for (i, ar) in dic.items():
			if len(ar) > maxx:
				maxx = len(ar)
		return maxx


from collections import deque

class Solution:

	def getMaxWidth(self, root):
		q = deque()
		if root == None:
			return 0
		q.append(root)
		max_len = 1
		while q:
			temp = deque()
			while q:
				node = q.popleft()
				if node.left != None:
					temp.append(node.left)
				if node.right != None:
					temp.append(node.right)
			q = temp.copy()
			if len(q) > max_len:
				max_len = len(q)
		return max_len


class Solution:

	def fun(self, root, level, l):
		if root == None:
			return
		if level >= len(l):
			l.append([])
		l[level].append(root.data)
		self.fun(root.left, level + 1, l)
		self.fun(root.right, level + 1, l)

	def getMaxWidth(self, root):
		l = []
		self.fun(root, 0, l)
		m = 0
		for i in l:
			m = max(m, len(i))
		return m


class Solution:

	def getMaxWidth(self, root):
		q = deque([root])
		r = 0
		while q:
			l = []
			for i in range(len(q)):
				n = q.popleft()
				if n:
					l.append(n.data)
					q.append(n.left)
					q.append(n.right)
			if l:
				r = max(r, len(l))
		return r


class Solution:

	def getMaxWidth(self, root):
		from collections import deque
		if root is None:
			return 0
		q = deque()
		maxWidth = 0
		q.append(root)
		while q:
			count = len(q)
			maxWidth = max(count, maxWidth)
			while count is not 0:
				count = count - 1
				temp = q.popleft()
				if temp.left is not None:
					q.append(temp.left)
				if temp.right is not None:
					q.append(temp.right)
		return maxWidth


from collections import deque

class Solution:

	def getMaxWidth(self, root):
		if not root:
			return 0
		queue = deque()
		queue.append(root)
		maxi = -1
		while queue:
			sz = len(queue)
			if maxi < sz:
				maxi = sz
			for i in range(sz):
				node = queue.popleft()
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return maxi


class Solution:

	def getMaxWidth(self, root):
		if root == None:
			return 0
		l = [root]
		g = 0
		while l:
			r = []
			c = 0
			for i in l:
				c += 1
				if i.left:
					r.append(i.left)
				if i.right:
					r.append(i.right)
			if c > g:
				g = c
			l = r
		return g


from collections import deque

class Solution:

	def getMaxWidth(self, root):
		mx = 0
		q = deque([root])
		while len(q):
			mx = max(mx, len(q))
			n = len(q)
			for i in range(n):
				k = q.popleft()
				if k.left:
					q.append(k.left)
				if k.right:
					q.append(k.right)
		return mx


class Solution:

	def getMaxWidth(self, root):
		stack = [root]
		node_at_each_level = 1
		prev = 1
		while len(stack) > 0:
			x = stack.pop(0)
			if x.left:
				stack.append(x.left)
			if x.right:
				stack.append(x.right)
			node_at_each_level -= 1
			if node_at_each_level == 0:
				node_at_each_level = len(stack)
				prev = max(prev, node_at_each_level)
		return prev


class Solution:

	def getMaxWidth(self, root):
		stack = [root]
		node_at_each_level = 0
		prev = 0
		while len(stack) > 0:
			node_at_each_level = len(stack)
			prev = max(prev, node_at_each_level)
			for i in range(node_at_each_level):
				x = stack.pop(0)
				if x.left:
					stack.append(x.left)
				if x.right:
					stack.append(x.right)
		return prev


class Solution:

	def getMaxWidth(self, root):
		node = root
		stack = []
		stack.append(node)
		length = 0
		while stack:
			if len(stack) > length:
				length = len(stack)
			temp = []
			while stack:
				n = stack.pop()
				if n.left:
					temp.append(n.left)
				if n.right:
					temp.append(n.right)
			stack = temp
		return length


class Solution:

	def getMax(self, root):
		maximum = 0
		q = [root]
		while q:
			level_node = []
			size = len(q)
			for _ in range(size):
				node = q.pop(0)
				level_node.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			maximum = max(maximum, len(level_node))
		return maximum

	def getMaxWidth(self, root):
		if root:
			return self.getMax(root)
		else:
			return


class Solution:

	def getMaxWidth(self, root):
		maxi = 0
		queue = []
		queue.append([root, 0])
		while len(queue):
			n = len(queue)
			first = 0
			last = 0
			mmin = queue[0][1]
			for i in range(n):
				p = queue.pop(0)
				curr = p[1] - mmin
				node = p[0]
				if i == 0:
					first = i
				if i == n - 1:
					last = i
				if node.left:
					queue.append([node.left, 2 * curr + 1])
				if node.right:
					queue.append([node.right, 2 * curr + 1])
			maxi = max(maxi, last - first + 1)
		return maxi


class Solution:

	def getMaxWidth(self, root):
		if not root:
			return -1
		queue = []
		queue.append(root)
		max_width = 1
		while queue:
			another = []
			while queue:
				node = queue.pop(0)
				if node.left:
					another.append(node.left)
				if node.right:
					another.append(node.right)
			max_width = max(max_width, len(another))
			queue = another
		return max_width


class Solution:

	def solve(self, root, l, dic):
		if root == None:
			return
		if l not in dic:
			dic[l] = 1
		else:
			dic[l] += 1
		l += 1
		self.solve(root.left, l, dic)
		self.solve(root.right, l, dic)

	def getMaxWidth(self, root):
		dic = {}
		self.solve(root, 0, dic)
		ans = float('-inf')
		for i in dic:
			ans = max(ans, dic[i])
		return ans


from collections import deque

class Solution:

	def getMaxWidth(self, root):
		q = deque()
		q.append(root)
		ans = -1
		while q:
			n = len(q)
			if n > ans:
				ans = n
			for j in range(n):
				p = q.pop()
				if p.left:
					q.appendleft(p.left)
				if p.right:
					q.appendleft(p.right)
		return ans


class Solution:

	def getMaxWidth(self, root):

		def pre(root, l):
			if root is None:
				l -= 1
				return
			if l not in d.keys():
				d[l] = 1
			else:
				d[l] += 1
			pre(root.left, l + 1)
			pre(root.right, l + 1)
		d = {}
		l = 0
		pre(root, l)
		l = []
		for (i, j) in d.items():
			l.append(j)
		return max(l)


class Solution:

	def getMaxWidth(self, root):
		(queue, width) = ([root], 0)
		if root is None:
			return 0
		while queue:
			size = len(queue)
			width = max(width, size)
			for i in range(size):
				node = queue.pop(0)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return width


class Solution:
	d = dict()

	def gen(self, root, level):
		if root == None:
			return
		if level in self.d:
			self.d[level] += 1
		else:
			self.d[level] = 1
		self.gen(root.left, level + 1)
		self.gen(root.right, level + 1)

	def getMaxWidth(self, root):
		self.d = dict()
		self.gen(root, 0)
		maxi = 0
		for i in self.d:
			if self.d[i] > maxi:
				maxi = self.d[i]
		return maxi


class Solution:

	def getMaxWidth(self, root):
		max_count = float('-inf')
		queue = [root]
		while len(queue):
			n = len(queue)
			temp = 0
			while n > 0:
				node = queue.pop(0)
				temp = temp + 1
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
				n = n - 1
			max_count = max(max_count, temp)
		return max_count


class Solution:

	def getMaxWidth(self, root):
		mp = {}
		lev = 1

		def width(root, lev, mp):
			if root == None:
				return
			try:
				mp[lev].append(root.data)
			except:
				mp[lev] = [root.data]
			lev = lev + 1
			width(root.left, lev, mp)
			width(root.right, lev, mp)
		width(root, lev, mp)
		maxi = 0
		for i in range(min(mp.keys()), max(mp.keys()) + 1):
			cnt = 0
			for ele in mp[i]:
				cnt = cnt + 1
			maxi = max(maxi, cnt)
		return maxi
		return 1