Given a Binary Tree of N nodes. Find the vertical width of the tree.
Example 1:
Input:
          1
       /    \
      2      3
     / \    / \
    4   5  6   7
            \   \
             8   9
Output: 6
Explanation: The width of a binary tree is
the number of vertical paths in that tree.
The above tree contains 6 vertical lines.
 
Example 2:
Input:
      1
    /  \
   2    3
Output: 3
 
Your Task:
You don't have to read input or print anything. Your task is to complete the function verticalWidth() which takes root as the only parameter, and returns the vertical width of the binary tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
0 <= Number of nodes <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3





#Function to find the vertical width of a Binary Tree.

def verticalWidth(root):

    # code here

Solutions:
def verticalWidth(root):
	if not root:
		return 0
	queue = [(root, 0)]
	(l, r, hd) = (0, 0, 0)
	(maxi, mini) = (0, 0)
	while queue:
		(node, hd) = queue.pop(0)
		(l, r) = (hd, hd)
		if node.left:
			l -= 1
			mini = min(l, mini)
			queue.append((node.left, l))
		if node.right:
			r += 1
			maxi = max(r, maxi)
			queue.append((node.right, r))
	return maxi - mini + 1


def verticalWidth(root):
	if root == None:
		return 0
	maxLevel = 0
	minLevel = 0
	q = []
	q.append([root, 0])
	while len(q) != 0:
		(cur, count) = q.pop(0)
		if cur.left:
			minLevel = min(minLevel, count - 1)
			q.append([cur.left, count - 1])
		if cur.right:
			maxLevel = max(maxLevel, count + 1)
			q.append([cur.right, count + 1])
	return maxLevel + abs(minLevel) + 1


def verticalWidth(root):
	if root is None:
		return 0
	(q, l) = (deque(), deque())
	q.append(root)
	l.append(0)
	(vw_min, vw_max) = (float('inf'), float('-inf'))
	while q:
		s = len(q)
		for i in range(s):
			node = q.popleft()
			vw = l.popleft()
			vw_min = min(vw_min, vw)
			vw_max = max(vw_max, vw)
			if node.left:
				l.append(vw - 1)
				q.append(node.left)
			if node.right:
				l.append(vw + 1)
				q.append(node.right)
	return vw_max - vw_min + 1


def verticalWidth(root):
	s = set([0])
	h = 0
	if root is None:
		return 0
	s = count(root, h, s)
	return len(s)

def count(root, h, s):
	if root is None:
		return
	s.add(h)
	count(root.left, h - 1, s)
	count(root.right, h + 1, s)
	return s


def verticalWidth(root):
	if root == None:
		return 0
	dict = {}
	q = []
	q1 = []
	q.append(root)
	q1.append(0)
	while len(q) > 0:
		curr = q.pop(0)
		hd = q1.pop(0)
		if hd not in dict:
			dict[hd] = []
		dict[hd].append(curr.data)
		if curr.left != None:
			q.append(curr.left)
			q1.append(hd - 1)
		if curr.right != None:
			q.append(curr.right)
			q1.append(hd + 1)
	return len(dict)


def verticalWidth(root):
	minhd = [100000.0]
	maxhd = [-100000.0]
	if root == None:
		return 0

	def traver(root, hd):
		if root == None:
			return
		nonlocal minhd
		nonlocal maxhd
		minhd[0] = min(minhd[0], hd)
		maxhd[0] = max(maxhd[0], hd)
		traver(root.left, hd - 1)
		traver(root.right, hd + 1)
	traver(root, 0)
	return maxhd[0] - minhd[0] + 1


def verticalWidth(root):

	def width(root, c, d):
		if root == None:
			return
		if c not in d:
			d.append(c)
		width(root.left, c - 1, d)
		width(root.right, c + 1, d)
	d = []
	width(root, 0, d)
	return len(d)


def verticalWidth(root):
	(minm, maxm) = (0, 0)
	if root == None:
		return 0

	def dfs(node, hl):
		nonlocal minm, maxm
		if node == None:
			return
		minm = min(minm, hl)
		maxm = max(maxm, hl)
		if node.left != None:
			dfs(node.left, hl - 1)
		if node.right != None:
			dfs(node.right, hl + 1)
	dfs(root, 0)
	return maxm - minm + 1


def verticalWidth(root):
	minHD = [100000.0]
	maxHD = [-100000.0]
	if root is None:
		return 0

	def traversal(root, hd):
		if root is None:
			return
		nonlocal minHD
		nonlocal maxHD
		minHD[0] = min(minHD[0], hd)
		maxHD[0] = max(maxHD[0], hd)
		traversal(root.left, hd - 1)
		traversal(root.right, hd + 1)
	traversal(root, 0)
	return maxHD[0] - minHD[0] + 1


def verticalWidth(root):
	(a, b) = (0, -1)

	def trav(root, l):
		nonlocal a, b
		if root:
			if root.left:
				trav(root.left, l - 1)
			if root.right:
				trav(root.right, l + 1)
			a = min(a, l)
			b = max(b, l)
	if root:
		trav(root, 0)
	return b - a + 1


def fun(root, n, l):
	if root == None:
		return
	if n not in l:
		l.append(n)
	fun(root.left, n - 1, l)
	fun(root.right, n + 1, l)

def verticalWidth(root):
	l = []
	fun(root, 0, l)
	return len(l)


def solve(root, mx, curr):
	if root == None:
		return
	mx.append(curr)
	solve(root.left, mx, curr - 1)
	solve(root.right, mx, curr + 1)

def verticalWidth(root):
	mx = []
	solve(root, mx, 0)
	mx = set(mx)
	return len(mx)


def verticalWidth(root):

	def solve(root, maxa, cur):
		if root == None:
			return
		maxa.append(cur)
		solve(root.left, maxa, cur - 1)
		solve(root.right, maxa, cur + 1)
		return maxa
	ans = solve(root, [], 0)
	if ans:
		ans = set(ans)
		return len(ans)
	return 0