Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null. 

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).



Example 2:

Input: 

          1
         /  
        3    
       / \       
      5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).



Example 3:

Input: 

          1
         / \
        3   2 
       /        
      5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).


Example 4:

Input: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).




Note:
Answer will in the range of 32-bit signed integer.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph traversal

Starter code: # Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        

Solutions:
class Solution:

	def widthOfBinaryTree(self, root):
		if not root:
			return 0
		s = 1
		a = [[root, 1]]
		while 1:
			b = []
			for p in a:
				if p[0].left:
					b.append([p[0].left, 2 * p[1] - 1])
				if p[0].right:
					b.append([p[0].right, 2 * p[1]])
			a = b
			if a:
				s = max(s, a[-1][1] - a[0][1] + 1)
			else:
				break
		return s


class Solution:

	def widthOfBinaryTree(self, root):
		widths = []

		def traverse(root, height, pos):
			nonlocal widths
			if root is None:
				return
			if len(widths) < height + 1:
				widths.append([height, pos, pos])
			else:
				if widths[height][1] > pos:
					widths[height][1] = pos
				if widths[height][2] < pos:
					widths[height][2] = pos
			if pos == 0:
				traverse(root.left, 1, -1)
				traverse(root.right, 1, 1)
			else:
				traverse(root.left, height + 1, 2 * pos - 1 if pos > 0 else 2 * pos)
				traverse(root.right, height + 1, 2 * pos if pos > 0 else 2 * pos + 1)
		traverse(root, 0, 0)
		ret = 0
		for width in widths:
			ret = max(ret, width[2] - width[1] if width[2] * width[1] < 0 else width[2] - width[1] + 1)
		return ret


class Solution:

	def widthOfBinaryTree(self, root):
		if root is None:
			return 0
		q = [(root, 0)]
		left = 0
		right = 0
		res = 1
		while q:
			qLength = len(q)
			for i in range(qLength):
				(node, index) = q.pop(0)
				if i == 0:
					left = index
				if i == qLength - 1:
					right = index
				if node.left is not None:
					q.append((node.left, 2 * index + 1))
				if node.right is not None:
					q.append((node.right, 2 * index + 2))
			res = max(res, right - left + 1)
		return res


class Solution:

	def widthOfBinaryTree(self, root):
		queue = [(root, 0, 0)]
		cur_depth = left = ans = 0
		for (node, depth, pos) in queue:
			if node:
				queue.append((node.left, depth + 1, pos * 2))
				queue.append((node.right, depth + 1, pos * 2 + 1))
				if cur_depth != depth:
					cur_depth = depth
					left = pos
				ans = max(pos - left + 1, ans)
		return ans


class Solution:

	def widthOfBinaryTree(self, root):
		if not root:
			return 0
		queue = collections.deque([[root, 0]])
		ret = 0
		while queue:
			size = len(queue)
			level = []
			for _ in range(size):
				(node, pos) = queue.pop()
				level.append(pos)
				if node.left:
					queue.appendleft([node.left, pos * 2])
				if node.right:
					queue.appendleft([node.right, 1 + pos * 2])
			print(level)
			ret = max(ret, level[-1] - level[0] + 1)
		return ret


class Solution:

	def widthOfBinaryTree(self, root):

		def get_max_width(root, width, level, d):
			if not root:
				return
			d[level].append(width)
			get_max_width(root.left, 2 * width, level + 1, d)
			get_max_width(root.right, 2 * width + 1, level + 1, d)
		from collections import defaultdict
		d = defaultdict(list)
		get_max_width(root, 0, 0, d)
		print(d)
		max_width = 0
		for (level, elements) in list(d.items()):
			if elements:
				elements.sort()
				curr_width = elements[-1] - elements[0] + 1
				max_width = max(max_width, curr_width)
		return max_width


class Solution:

	def widthOfBinaryTree(self, root):
		if not root:
			return 0
		maxlen = 1
		start = 1
		end = 1
		tlen = 1
		l = [[root, 1]]
		while tlen:
			llen = tlen
			tlen = 0
			while llen:
				cur = l.pop(0)
				llen -= 1
				if cur[0]:
					l.append([cur[0].left, 2 * cur[1] - 1])
					l.append([cur[0].right, 2 * cur[1]])
					tlen += 2
			if len(l) > 0:
				for item in reversed(l):
					if item[0]:
						end = item[1]
						break
				if end != item[1]:
					return maxlen
				for item in l:
					if item[0]:
						start = item[1]
						break
				end = end - start + 1
				if end > maxlen:
					maxlen = end
				start = end = -1
		return maxlen


class Solution:

	def isInt(self, e):
		return type(e).__name__ == 'int'

	def testNode(self, node, newStack):
		acc = 0
		if node:
			newStack.append(node)
			acc += 1
		elif len(newStack):
			acc += 1
			if self.isInt(newStack[-1]):
				newStack[-1] += 1
			else:
				newStack.append(1)
		return acc

	def widthOfBinaryTree(self, root):
		if not root:
			return 0
		stack = [root]
		res = 1
		while len(stack):
			newStack = []
			acc = 0
			for node in stack:
				if self.isInt(node):
					if len(newStack):
						if self.isInt(newStack[-1]):
							newStack[-1] += 2 * node
						else:
							newStack.append(2 * node)
						acc += 2 * node
				else:
					acc += self.testNode(node.left, newStack)
					acc += self.testNode(node.right, newStack)
			stack = newStack
			if len(newStack) and self.isInt(newStack[-1]):
				acc -= stack.pop()
			res = max(res, acc)
		return res


class Solution:

	def widthOfBinaryTree(self, root):
		table = {}
		stack = [(root, [])]
		while stack:
			(node, path) = stack.pop()
			if not node:
				continue
			table.setdefault(len(path), []).append(path)
			stack.append((node.left, path + ['0']))
			stack.append((node.right, path + ['1']))
		maxwidth = 0
		for n in sorted(table):
			paths = table[n]
			if len(paths) < 1:
				continue
			if len(paths) == 1:
				maxwidth = max(1, maxwidth)
				continue
			values = list(map(lambda p: int(''.join(p), 2), paths))
			width = max(values) - min(values) + 1
			maxwidth = max(maxwidth, width)
		return maxwidth