Given a binary tree and a node data called target. Find the minimum time required to burn the complete binary tree if the target is set on fire. It is known that in 1 second all nodes connected to a given node get burned. That is its left child, right child, and parent.
Note: The tree contains unique values.
Example 1:
Input:      
          1
        /   \
      2      3
    /  \      \
   4    5      6
       / \      \
      7   8      9
                   \
                   10
Target Node = 8
Output: 7
Explanation: If leaf with the value 
8 is set on fire. 
After 1 sec: 5 is set on fire.
After 2 sec: 2, 7 are set to fire.
After 3 sec: 4, 1 are set to fire.
After 4 sec: 3 is set to fire.
After 5 sec: 6 is set to fire.
After 6 sec: 9 is set to fire.
After 7 sec: 10 is set to fire.
It takes 7s to burn the complete tree.
Example 2:
Input:      
          1
        /   \
      2      3
    /  \      \
   4    5      7
  /    / 
 8    10
Target Node = 10
Output: 5
Your Task:  
You don't need to read input or print anything. Complete the function minTime() which takes the root of the tree and target as input parameters and returns the minimum time required to burn the complete binary tree if the target is set on fire at the 0th second.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
Constraints:
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def minTime(self, root,target):

        # code here



Solutions:
from collections import defaultdict

class Solution:

	def minTime(self, root, target):
		que = deque()
		parentmap = defaultdict(Node)
		que.append(root)
		start = Node
		while que:
			curr = que.popleft()
			if curr.data == target:
				start = curr
			if curr.left:
				que.append(curr.left)
				parentmap[curr.left] = curr
			if curr.right:
				que.append(curr.right)
				parentmap[curr.right] = curr
		visited = set()
		visited.add(start)
		que.append(start)
		time = 0
		while que:
			size = len(que)
			for _ in range(size):
				curr = que.popleft()
				if curr.left and curr.left not in visited:
					que.append(curr.left)
					visited.add(curr.left)
				if curr.right and curr.right not in visited:
					que.append(curr.right)
					visited.add(curr.right)
				if curr in parentmap and parentmap[curr] not in visited:
					que.append(parentmap[curr])
					visited.add(parentmap[curr])
			time += 1
		return time - 1


import collections
from collections import deque

class Solution:

	def minTime(self, root, target):
		d = {}
		q = collections.deque()
		q.append(root)
		s = set()
		d[root] = None
		while q:
			a = q.popleft()
			if a:
				s.add(a.data)
				if a.data == target:
					start = a
				if a.left:
					d[a.left] = a
					q.append(a.left)
				if a.right:
					d[a.right] = a
					q.append(a.right)
		q = collections.deque()
		q.append((start, 0))
		ans = 0
		while q:
			z = q.popleft()
			(a, c) = z
			if a:
				if a.data in s:
					s.remove(a.data)
					if d[a]:
						if d[a].data in s:
							q.append((d[a], c + 1))
					if a.left:
						if a.left.data in s:
							q.append((a.left, c + 1))
					if a.right:
						if a.right.data in s:
							q.append((a.right, c + 1))
		return c


from collections import defaultdict

class Solution:

	def minTime(self, root, target):
		par = {}
		q = deque()
		q.append(root)
		leaf = Node(0)
		while q:
			node = q.popleft()
			if node.data == target:
				leaf = node
			if node.left:
				par[node.left] = node
				q.append(node.left)
			if node.right:
				par[node.right] = node
				q.append(node.right)
		q = deque()
		q.append((leaf, 0))
		vis = set()
		vis.add(leaf.data)
		ans = 0
		while q:
			for _ in range(len(q)):
				(node, count) = q.popleft()
				ans = max(ans, count)
				if node.left and node.left.data not in vis:
					q.append((node.left, count + 1))
					vis.add(node.left.data)
				if node.right and node.right.data not in vis:
					q.append((node.right, count + 1))
					vis.add(node.right.data)
				if node in par and par[node].data not in vis:
					q.append((par[node], count + 1))
					vis.add(par[node].data)
		return ans


class Solution:

	def maxDepth(self, n):
		if n is None:
			return 0
		return 1 + max((self.maxDepth(n.left), self.maxDepth(n.right)))

	def traverse(self, n, target):
		if n is None:
			return (0, 0)
		if n.data == target:
			ans = self.maxDepth(n.right)
			ans = max(ans, self.maxDepth(n.left))
			return (ans, 1)
		(ans, dist) = self.traverse(n.left, target)
		if dist:
			ans = max(ans, dist + self.maxDepth(n.right))
			return (ans, dist + 1)
		(ans, dist) = self.traverse(n.right, target)
		if dist:
			ans = max(ans, dist + self.maxDepth(n.left))
			return (ans, dist + 1)
		return (0, 0)

	def minTime(self, root, target):
		return self.traverse(root, target)[0]


class Solution:

	def minTime(self, root, target):
		ans = []
		l = []
		r = []
		c = 0

		def find(root, target):
			if root:
				if root.data == target:
					ans.append(root)
					return 1
				a = find(root.left, target)
				if a:
					r.append([root, a])
					return a + 1
				b = find(root.right, target)
				if b:
					l.append([root, b])
					return b + 1
			return
		find(root, target)

		def height(root):
			if root:
				left_height = height(root.left)
				right_height = height(root.right)
				return max(left_height + 1, right_height + 1)
			return -1
		for el in ans:
			retn = height(el)
			c = max(c, retn)
		for el in l:
			if el[0].left:
				retn = height(el[0].left)
				c = max(c, retn + el[1] + 1)
		for el in r:
			if el[0].right:
				retn = height(el[0].right)
				c = max(c, retn + el[1] + 1)
		return c


class Solution:

	def minTime(self, root, target):
		d = {}
		from collections import deque
		q = deque()
		v = set()

		def pre(root, par):
			if root.data == target:
				q.append(root)
				v.add(root)
				return
			if root.left:
				d[root.left] = root
				pre(root.left, root)
			if root.right:
				d[root.right] = root
				pre(root.right, root)
		pre(root, None)
		ans = 0
		while q:
			ans += 1
			for i in range(len(q)):
				x = q.popleft()
				if x.left:
					if x.left not in v:
						q.append(x.left)
						v.add(x.left)
				if x.right:
					if x.right not in v:
						q.append(x.right)
						v.add(x.right)
				if x in d:
					if d[x] not in v:
						q.append(d[x])
						v.add(d[x])
		return ans - 1


from collections import defaultdict

class Solution:

	def minTime(self, root, target):
		graph = defaultdict(list)
		trvQ = [(root, None)]
		while trvQ:
			(node, par) = trvQ.pop(0)
			if par:
				graph[node.data].append(par.data)
			if node.left:
				graph[node.data].append(node.left.data)
				trvQ.append((node.left, node))
			if node.right:
				graph[node.data].append(node.right.data)
				trvQ.append((node.right, node))
		bfs = [(target, 0)]
		visit = set()
		n = len(graph)
		while bfs:
			(node, time) = bfs.pop(0)
			visit.add(node)
			if len(visit) == n:
				return time
			for nei in graph[node]:
				if nei not in visit:
					bfs.append((nei, time + 1))
		return 0


class Solution:

	def minTime(self, root, target):
		ans = []
		lft = []
		rgt = []
		c_ans = 0

		def find(root, target):
			if root:
				if root.data == target:
					ans.append(root)
					return 1
				a = find(root.left, target)
				if a:
					rgt.append([root, a])
					return a + 1
				b = find(root.right, target)
				if b:
					lft.append([root, b])
					return b + 1
			return
		find(root, target)

		def height(root):
			if root:
				left_height = height(root.left)
				right_height = height(root.right)
				return max(left_height + 1, right_height + 1)
			return -1
		for el in ans:
			retn = height(el)
			c_ans = max(c_ans, retn)
		for el in lft:
			if el[0].left:
				retn = height(el[0].left)
				c_ans = max(c_ans, retn + el[1] + 1)
		for el in rgt:
			if el[0].right:
				retn = height(el[0].right)
				c_ans = max(c_ans, retn + el[1] + 1)
		return c_ans


class Solution:

	def minTime(self, root, target):
		ans = [0] * 1

		def fun(root):
			if root == None:
				return -1
			return max(1 + fun(root.left), 1 + fun(root.right))

		def fun1(root):
			if root == None:
				return -1
			if root.data == target:
				x = fun(root)
				ans[0] = max(ans[0], x)
				return 1
			left = fun1(root.left)
			if left != -1:
				x = fun(root.right)
				ans[0] = max(ans[0], x + left + 1)
				return left + 1
			right = fun1(root.right)
			if right != -1:
				x = fun(root.left)
				ans[0] = max(ans[0], x + right + 1)
				return right + 1
			return -1
		fun1(root)
		return ans[0]


from collections import defaultdict

class Solution:

	def inorder(self, root, par):
		if root:
			if par.data != -1:
				self.d[root.data].append(par.data)
				self.d[par.data].append(root.data)
			self.inorder(root.left, root)
			self.inorder(root.right, root)

	def minTime(self, root, target):
		self.d = defaultdict(list)
		self.inorder(root, Node(-1))
		x = target
		q = deque()
		q.append(x)
		ans = 0
		s = set()
		s.add(x)
		while q:
			for _ in range(len(q)):
				node = q.popleft()
				for neigh in self.d[node]:
					if neigh not in s:
						s.add(neigh)
						q.append(neigh)
			ans += 1
		return ans - 1


from collections import *

class Solution:

	def minTime(self, root, target):
		p = dict()
		q = deque([])
		q.append(root)
		totalCount = 0
		visited = set()
		targetNode = None
		while q:
			curr = q.popleft()
			if curr.data == target:
				targetNode = curr
			totalCount += 1
			if curr.left:
				p[curr.left] = curr
				q.append(curr.left)
			if curr.right:
				p[curr.right] = curr
				q.append(curr.right)
		q1 = deque([[targetNode, 0]])
		while q1:
			(currNode, currScore) = q1.popleft()
			visited.add(currNode)
			if len(visited) == totalCount:
				return currScore
			if currNode in p and p[currNode] not in visited:
				q1.append([p[currNode], currScore + 1])
			if currNode.left and currNode.left not in visited:
				q1.append([currNode.left, currScore + 1])
			if currNode.right and currNode.right not in visited:
				q1.append([currNode.right, currScore + 1])
		return -1


class Solution:

	def minTime(self, root, target):
		parent = {}
		temp = root

		def traverse(root):
			if not root:
				return
			if root.left:
				parent[root.left] = root
				traverse(root.left)
			if root.right:
				parent[root.right] = root
				traverse(root.right)
		traverse(temp)

		def findNode(root, target):
			if not root:
				return None
			if root.data == target:
				return root
			left = findNode(root.left, target)
			if left:
				return left
			right = findNode(root.right, target)
			if right:
				return right
		node = findNode(root, target)

		def bfs(node):
			q = deque()
			q.append(node)
			visited = set()
			visited.add(node)
			count = 0
			while q:
				count += 1
				for i in range(len(q)):
					curr = q.popleft()
					if curr.left and curr.left not in visited:
						q.append(curr.left)
						visited.add(curr.left)
					if curr.right and curr.right not in visited:
						q.append(curr.right)
						visited.add(curr.right)
					if curr in parent and parent[curr] not in visited:
						q.append(parent[curr])
						visited.add(parent[curr])
			return count
		return bfs(node) - 1


class Solution:

	def minTime(self, root, target):
		parent = {}
		start = None

		def dfs(node, par):
			nonlocal target, parent, start
			if node.data == target:
				start = node
			parent[node] = par
			if node.left != None:
				dfs(node.left, node)
			if node.right != None:
				dfs(node.right, node)
		dfs(root, None)
		queue = [start]
		time = 0
		visited = [start]
		while queue:
			level = len(queue)
			while level > 0:
				x = queue.pop(0)
				if x.left and x.left not in visited:
					queue.append(x.left)
					visited.append(x.left)
				if x.right and x.right not in visited:
					queue.append(x.right)
					visited.append(x.right)
				if parent[x] and parent[x] not in visited:
					queue.append(parent[x])
					visited.append(parent[x])
				level -= 1
			time += 1
		return time - 1


class Solution:

	def minTime(self, root, target):
		d = {}
		tar = None

		def trav(par, root):
			nonlocal target, tar
			if root:
				trav(root, root.left)
				d[root] = par
				if root.data == target:
					tar = root
				trav(root, root.right)
		trav(None, root)
		Q = [(tar, 0)]
		s = set()
		s.add(tar)
		m = 0
		while Q != []:
			(a, b) = Q.pop(0)
			if d[a] and d[a] not in s:
				Q.append((d[a], b + 1))
				s.add(d[a])
			if a.left and a.left not in s:
				Q.append((a.left, b + 1))
				s.add(a.left)
			if a.right and a.right not in s:
				Q.append((a.right, b + 1))
				s.add(a.right)
			m = max(m, b)
		return m


class Solution:

	def minTime(self, root, target):
		result = 0

		def logic(root, target):
			nonlocal result
			if root == None:
				return 0
			left = logic(root.left, target)
			right = logic(root.right, target)
			if root.data == target:
				result = max(left, right)
				return '0'
			if type(left) == str:
				left = int(left)
				result = max(result, left + right + 1)
				return str(left + 1)
			if type(right) == str:
				right = int(right)
				result = max(result, left + right + 1)
				return str(right + 1)
			return max(left, right) + 1
		logic(root, target)
		return result


from collections import deque

class Solution:

	def minTime(self, root, target):
		q = deque([root])
		d = {}
		tar = 0
		while q:
			node = q.popleft()
			if node.left:
				q.append(node.left)
				d[node.left] = node
			if node.right:
				q.append(node.right)
				d[node.right] = node
			if node.data == target:
				tar = node
		q.append(tar)
		c = 0
		visited = set()
		visited.add(tar)
		while q:
			n = len(q)
			for i in range(n):
				node = q.popleft()
				if node in d and d[node] not in visited:
					q.append(d[node])
					visited.add(d[node])
				if node.left and node.left not in visited:
					q.append(node.left)
					visited.add(node.left)
				if node.right and node.right not in visited:
					q.append(node.right)
					visited.add(node.right)
			c += 1
		return c - 1


from collections import deque

class Solution:

	def minTime(self, root, target):

		def addParent(node, parent):
			if not node:
				return
			node.parent = parent
			addParent(node.left, node)
			addParent(node.right, node)

		def findNode(node, target):
			if not node:
				return None
			if node.data == target:
				return node
			left = findNode(node.left, target)
			right = findNode(node.right, target)
			if left:
				return left
			return right
		addParent(root, None)
		node = findNode(root, target)
		queue = deque([node])
		time = 0
		s = {node}
		while queue:
			n = len(queue)
			for i in range(n):
				tempNode = queue.popleft()
				if tempNode.parent and tempNode.parent not in s:
					queue.append(tempNode.parent)
					s.add(tempNode.parent)
				if tempNode.left and tempNode.left not in s:
					queue.append(tempNode.left)
					s.add(tempNode.left)
				if tempNode.right and tempNode.right not in s:
					queue.append(tempNode.right)
					s.add(tempNode.right)
			if queue:
				time += 1
		return time


class Solution:

	def minTime(self, root, target):
		self.parent = {}
		self.target_ref = None

		def bfs(node, target):
			q = [node]
			while q:
				front = q.pop(0)
				if front.data == target:
					self.target_ref = front
				if front.left:
					self.parent[front.left.data] = front
					q.append(front.left)
				if front.right:
					self.parent[front.right.data] = front
					q.append(front.right)
		bfs(root, target)
		vis = {}
		self.maxi = 0

		def dfs(node, t):
			if not node:
				return
			vis[node.data] = 1
			f = 0
			self.maxi = max(self.maxi, t)
			if node.left and (not vis.get(node.left.data)):
				dfs(node.left, t + 1)
				f = 1
			if node.right and (not vis.get(node.right.data)):
				dfs(node.right, t + 1)
				f = 1
			if self.parent.get(node.data) and (not vis.get(self.parent[node.data].data)):
				dfs(self.parent[node.data], t + 1)
				f = 1
		dfs(self.target_ref, 0)
		return self.maxi


class Solution:

	def minTime(self, root, target):

		def parentTrack(root, parent_track, target):
			queue = []
			parent_track[root] = None
			queue.append(root)
			while queue:
				node = queue[0]
				queue.pop(0)
				if node.left:
					parent_track[node.left] = node
					queue.append(node.left)
				if node.right:
					parent_track[node.right] = node
					queue.append(node.right)
				if node.data == target:
					tar = node
			return tar

		def KDN(root, target):
			parent_track = {}
			tar = parentTrack(root, parent_track, target)
			visited = {}
			queue = []
			queue.append(tar)
			visited[tar] = True
			count = 0
			bool_value = False
			while queue:
				for i in range(len(queue)):
					node = queue[0]
					queue.pop(0)
					if node.left and node.left not in visited:
						queue.append(node.left)
						visited[node.left] = True
						bool_value = True
					if node.right and node.right not in visited:
						queue.append(node.right)
						visited[node.right] = True
						bool_value = True
					if parent_track[node] and parent_track[node] not in visited:
						queue.append(parent_track[node])
						visited[parent_track[node]] = True
						bool_value = True
				if bool_value == True:
					count += 1
					bool_value = False
			return count
		return KDN(root, target)


class Solution:
	maxi = -1
	pathfound = 0

	def gen(self, root, visited, dist):
		if root == None:
			return
		self.maxi = max(self.maxi, dist)
		if root.left != None and root.left.data not in visited:
			visited[root.left.data] = 1
			self.gen(root.left, visited, dist + 1)
		if root.right != None and root.right.data not in visited:
			visited[root.right.data] = 1
			self.gen(root.right, visited, dist + 1)

	def pathgen(self, root, target, path, pathele):
		if root == None:
			return
		if root.data == target:
			path.append(root)
			pathele.append(root.data)
			self.pathfound = 1
			return
		if root.left != None and self.pathfound == 0:
			path.append(root)
			pathele.append(root.data)
			self.pathgen(root.left, target, path, pathele)
			if self.pathfound == 0:
				path.pop()
				pathele.pop()
		if root.right != None and self.pathfound == 0:
			path.append(root)
			pathele.append(root.data)
			self.pathgen(root.right, target, path, pathele)
			if self.pathfound == 0:
				path.pop()
				pathele.pop()

	def minTime(self, root, target):
		self.pathfound = 0
		self.maxi = -1
		path = []
		pathele = []
		self.pathgen(root, target, path, pathele)
		dist = 0
		visited = dict()
		for i in pathele:
			visited[i] = 1
		while len(path) != 0:
			node = path.pop()
			self.gen(node, visited, dist)
			dist += 1
		return self.maxi


import math

class Solution:

	def findPath(self, root, path, node):
		if root == None:
			return False
		if root.data == node:
			path.append(root)
			return True
		path.append(root)
		if self.findPath(root.left, path, node):
			return True
		if self.findPath(root.right, path, node):
			return True
		path.pop()

	def dfs(self, root, dist, dic):
		if root == None:
			return
		if root.data in dic:
			if dist < dic[root.data]:
				dic[root.data] = dist
		else:
			dic[root.data] = dist
		self.dfs(root.left, dist + 1, dic)
		self.dfs(root.right, dist + 1, dic)

	def minTime(self, root, target):
		path = []
		dic = {}
		self.findPath(root, path, target)
		for i in range(0, len(path)):
			dist = len(path) - 1 - i
			self.dfs(path[i], dist, dic)
		result = -math.inf
		for (k, v) in dic.items():
			if v > result:
				result = v
		return result


class Solution:

	def findNode(self, root, target):
		if root == None:
			return None
		if root.data == target:
			return root
		l = self.findNode(root.left, target)
		r = self.findNode(root.right, target)
		if l != None:
			return l
		else:
			return r

	def minTime(self, root, target):
		target = self.findNode(root, target)
		q = [root]
		parentDic = {}
		while len(q) > 0:
			parent = q[0]
			q.pop(0)
			if parent.left != None:
				q.append(parent.left)
				parentDic[parent.left] = parent
			if parent.right != None:
				q.append(parent.right)
				parentDic[parent.right] = parent
		visitedDic = {}
		q = [target]
		t = -1
		while len(q) > 0:
			l = len(q)
			t += 1
			for i in range(l):
				node = q[0]
				q.pop(0)
				visitedDic[node] = 1
				if node.left != None:
					if visitedDic.get(node.left) == None:
						q.append(node.left)
				if node.right != None:
					if visitedDic.get(node.right) == None:
						q.append(node.right)
				if parentDic.get(node) != None:
					if visitedDic.get(parentDic[node]) == None:
						q.append(parentDic[node])
		return t


from collections import defaultdict

class Solution:

	def minTime(self, root, target):
		graph = defaultdict(list)
		stack = [(root, None)]
		while stack:
			(n, p) = stack.pop()
			if p:
				graph[p.data].append(n.data)
				graph[n.data].append(p.data)
			if n.left:
				stack.append((n.left, n))
			if n.right:
				stack.append((n.right, n))
		ans = -1
		seen = {target}
		queue = deque([target])
		while queue:
			for _ in range(len(queue)):
				u = queue.popleft()
				for v in graph[u]:
					if v not in seen:
						seen.add(v)
						queue.append(v)
			ans += 1
		return ans


from collections import deque

class Solution:

	def markParent(self, root, parent, start):
		q = deque()
		q.append(root)
		while q:
			cur = q.popleft()
			if cur.data == start:
				start = cur
			if cur.left:
				parent[cur.left] = cur
				q.append(cur.left)
			if cur.right:
				parent[cur.right] = cur
				q.append(cur.right)
		return start

	def minTime(self, root, target):
		parent = {}
		targetNode = self.markParent(root, parent, target)
		visited = {targetNode}
		q = deque()
		q.append(targetNode)
		minTime = 0
		while q:
			size = len(q)
			flag = 0
			for i in range(size):
				cur = q.popleft()
				if cur.left and cur.left not in visited:
					flag = 1
					q.append(cur.left)
					visited.add(cur.left)
				if cur.right and cur.right not in visited:
					flag = 1
					q.append(cur.right)
					visited.add(cur.right)
				if parent.get(cur) and parent.get(cur) not in visited:
					flag = 1
					q.append(parent.get(cur))
					visited.add(parent.get(cur))
			if flag == 1:
				minTime += 1
		return minTime


class Solution:

	def minTime(self, root, target):
		indNodes = {}
		self.targetInd = self.res = 0
		self.findTargetIndex(0, root, target, indNodes)
		vis = set()
		self.dfs(self.targetInd, indNodes[self.targetInd], -1, vis, indNodes)
		return self.res

	def findTargetIndex(self, ind, node, target, indNodes):
		if not node:
			return 0
		indNodes[ind] = node
		if node.data == target:
			self.targetInd = ind
		self.findTargetIndex(2 * ind + 1, node.left, target, indNodes)
		self.findTargetIndex(2 * ind + 2, node.right, target, indNodes)

	def dfs(self, ind, node, k, vis, indNodes):
		if not node or ind in vis:
			self.res = max(self.res, k)
			return
		vis.add(ind)
		self.dfs(2 * ind + 1, node.left, k + 1, vis, indNodes)
		self.dfs(2 * ind + 2, node.right, k + 1, vis, indNodes)
		parentInd = (ind - 1) // 2
		if parentInd >= 0:
			self.dfs(parentInd, indNodes[parentInd], k + 1, vis, indNodes)
		vis.remove(ind)


import queue

class Solution:

	def minTime(self, root, target):
		s = queue.Queue()
		s.put(root)
		parent = {}
		while not s.empty():
			n = s.qsize()
			cur_node = s.get()
			if cur_node.data == target:
				targetAdd = cur_node
			if cur_node.left:
				s.put(cur_node.left)
				parent[cur_node.left] = cur_node
			if cur_node.right:
				s.put(cur_node.right)
				parent[cur_node.right] = cur_node
		vis = set()
		s1 = queue.Queue()
		s1.put(targetAdd)
		vis.add(targetAdd)
		maxi = 0
		while not s1.empty():
			n = s1.qsize()
			flag = False
			for i in range(n):
				cur_node = s1.get()
				if cur_node.left and cur_node.left not in vis:
					s1.put(cur_node.left)
					vis.add(cur_node.left)
					flag = True
				if cur_node.right and cur_node.right not in vis:
					s1.put(cur_node.right)
					vis.add(cur_node.right)
					flag = True
				if cur_node in parent and parent[cur_node] not in vis:
					s1.put(parent[cur_node])
					vis.add(parent[cur_node])
					flag = True
			if flag:
				maxi += 1
		return maxi


class Solution:

	def minTime(self, root, target):
		queue = []
		queue.append(root)
		cpm = {}
		res = 0
		cpm[root] = None
		while queue:
			size = len(queue)
			while size > 0:
				node = queue.pop(0)
				if node.data == target:
					res = node
				if node.left:
					cpm[node.left] = node
					queue.append(node.left)
				if node.right:
					cpm[node.right] = node
					queue.append(node.right)
				size -= 1
		time = 0
		q = []
		q.append(res)
		vis = set()
		while q:
			size = len(q)
			isBurn = False
			while size > 0:
				node = q.pop(0)
				if cpm[node] and cpm[node] not in vis:
					vis.add(cpm[node])
					q.append(cpm[node])
					isBurn = True
				if node.left and node.left not in vis:
					vis.add(node.left)
					q.append(node.left)
					isBurn = True
				if node.right and node.right not in vis:
					vis.add(node.right)
					q.append(node.right)
					isBurn = True
				size -= 1
			if isBurn == True:
				time += 1
		return time


class Solution:

	def findParent(self, root, par):
		que = []
		que.append(root)
		while que:
			node = que[0]
			que.pop(0)
			if node.left:
				par[node.left] = node
				que.append(node.left)
			if node.right:
				par[node.right] = node
				que.append(node.right)

	def findTarRef(self, root, tar_value):
		que = []
		que.append(root)
		while que:
			node = que[0]
			if node.data == tar_value:
				return node
			que.pop(0)
			if node.left:
				que.append(node.left)
			if node.right:
				que.append(node.right)

	def minTime(self, root, target):
		par_dict = {}
		self.findParent(root, par_dict)
		tot = 0
		tar_node = self.findTarRef(root, target)
		que = []
		que.append(tar_node)
		visited = []
		visited.append(tar_node.data)
		while que:
			f = 0
			for i in range(len(que)):
				node = que.pop(0)
				if node in par_dict and par_dict[node].data not in visited:
					f = 1
					visited.append(par_dict[node].data)
					que.append(par_dict[node])
				if node.left:
					if node.left.data not in visited:
						f = 1
						visited.append(node.left.data)
						que.append(node.left)
				if node.right:
					if node.right.data not in visited:
						f = 1
						visited.append(node.right.data)
						que.append(node.right)
			if f == 1:
				tot += 1
		return tot


from collections import defaultdict

class Solution:

	def minTime(self, root, start):
		children_mp = defaultdict(list)

		def find_childrens(root):
			if not root:
				return
			if root.left:
				children_mp[root.data].append(root.left.data)
				children_mp[root.left.data].append(root.data)
			if root.right:
				children_mp[root.data].append(root.right.data)
				children_mp[root.right.data].append(root.data)
			find_childrens(root.left)
			find_childrens(root.right)
		find_childrens(root)
		res = -1
		(q, visited) = (deque([start]), {start})
		while q:
			for _ in range(len(q)):
				childrens = children_mp[q.popleft()]
				for c in childrens:
					if c not in visited:
						q.append(c)
						visited.add(c)
			res += 1
		return res


from collections import defaultdict

class Solution:

	def minTime(self, root, target):
		if not root.left and (not root.right):
			return 0
		gr = defaultdict(list)

		def makeGraph(root, prev):
			if not root:
				return
			if prev:
				gr[root.data].append(prev)
			if root.left:
				gr[root.data].append(root.left.data)
			if root.right:
				gr[root.data].append(root.right.data)
			makeGraph(root.left, root.data)
			makeGraph(root.right, root.data)
		makeGraph(root, None)
		count = 0
		res = [target]
		visited = set(res)
		while len(visited) != len(gr):
			new_result = []
			for parent_node in res:
				for child_node in gr[parent_node]:
					if child_node not in visited:
						new_result.append(child_node)
			res = new_result
			visited |= set(res)
			count += 1
		return count


def dfsparent(root, mpp, start):
	q = []
	q.append(root)
	res = None
	while len(q) > 0:
		node = q[0]
		if node.data == start:
			res = node
		q.pop(0)
		if node.left:
			mpp[node.left] = node
			q.append(node.left)
		if node.right:
			mpp[node.right] = node
			q.append(node.right)
	return res

def findtime(mpp, target):
	q = []
	q.append(target)
	vis = {}
	vis[target] = True
	maxi = 0
	while len(q) > 0:
		sz = len(q)
		fl = 0
		for i in range(sz):
			node = q.pop(0)
			if node.left and node.left not in vis:
				fl = 1
				vis[node.left] = True
				q.append(node.left)
			if node.right and node.right not in vis:
				fl = 1
				vis[node.right] = True
				q.append(node.right)
			if mpp.get(node) and mpp.get(node) not in vis:
				fl = 1
				vis[mpp.get(node)] = True
				q.append(mpp[node])
		if fl:
			maxi += 1
	return maxi

class Solution:

	def minTime(self, root, start):
		mpp = {}
		target = dfsparent(root, mpp, start)
		maxi = findtime(mpp, target)
		return maxi