Given a Binary Tree and a target key you need to find the level of target key in the given Binary Tree.
Note: The level of the root node is 1.
           3
         /   \
        2     5
      /   \
     1     4
Key: 4
Level: 3  
Note: if no such key exists then return 0.
Example 1:
Input:
        1
      /   \
     2     3
target = 4
Output: 0
Example 2:
Input:
         3
       /   \
      2     5
    /   \
   1     4
target = 4
Output: 3
Your Task:
 You don't have to take input. Just complete the function getLevel() that takes a node and a target as parameters and returns the level of the target value. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(H).
Note: H is the height of the tree and this space is used implicitly for recursion stack.
Constraints:
1 <= Number of nodes<= 10^{5}
1 <= Data of a node<= 10^{5}
1 <= Target <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3


'''
class Node:
    def __init__(self,val):
        self.data = val
        self.left = None
        self.right = None
'''
class Solution:
    def getLevel(self, root,target):
        '''
        :param root: root of given tree.
        :param target: target to find level
        :return: LEVEL NO
        '''
        # code here

Solutions:
class Solution:

	def getLevel(self, root, target):
		q = [root]
		lev = 1
		while q:
			l = len(q)
			for i in range(l):
				p = q.pop(0)
				if p.data == target:
					return lev
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
			lev += 1
		return 0


class Solution:

	def getLevel(self, root, target):
		return find(root, target, [0], 1)[0]

def find(root, target, res, l):
	if root == None:
		return res
	if root.data == target:
		res[0] = l
	find(root.left, target, res, l + 1)
	find(root.right, target, res, l + 1)
	return res


class Solution:

	def getLevel(self, root, target):

		def helper(root, target):
			if root.data == target:
				return 1
			left = right = -1
			if root.left is not None:
				left = helper(root.left, target)
			if root.right is not None:
				right = helper(root.right, target)
			if left == -1 and right == -1:
				return -1
			elif left != -1:
				return left + 1
			return right + 1
		answer = helper(root, target)
		if answer == -1:
			return 0
		return answer


class Solution:

	def getLevel(self, root, target):
		if root == None:
			return 0
		if root.data == target:
			return 1
		left = self.getLevel(root.left, target)
		right = self.getLevel(root.right, target)
		if left or right:
			return 1 + max(left, right)
		return 0


class Solution:

	def getLevel(self, root, target):
		depth = 1
		l = []

		def level(root, target, depth, l):
			if root is None:
				return 0
			if root.data == target:
				l.append(depth)
				return
			level(root.left, target, depth + 1, l)
			level(root.right, target, depth + 1, l)
		level(root, target, depth, l)
		if len(l) == 0:
			return 0
		else:
			return l[-1]


class Solution:

	def getLevel(self, root, target):
		ans = [0]

		def dfs(root, level):
			if not root:
				return
			if root.data == target:
				ans[0] = level + 1
			dfs(root.left, level + 1)
			dfs(root.right, level + 1)
		dfs(root, 0)
		if ans[0] != 0:
			return ans[0]
		else:
			return 0


class Solution:

	def getLevel(self, root, target):
		if not root:
			return 0
		count = 0
		q = []
		q.append(root)
		while q:
			for i in range(len(q)):
				curr = q.pop(0)
				if curr.data == target:
					return count + 1
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			count += 1
		return 0


class Solution:

	def __init__(self):
		self.ans = 0

	def tra(self, root, key, l=1):
		if root is None:
			return None
		if root.data == key:
			self.ans = l
		self.tra(root.left, key, l + 1)
		self.tra(root.right, key, l + 1)

	def getLevel(self, root, target):
		self.tra(root, target)
		return self.ans


class Solution:

	def getLevel(self, root, target):
		global find
		find = 0

		def helper(root, c, target):
			global find
			if root == None:
				return
			if root.data == target:
				find = c
				return
			helper(root.left, c + 1, target)
			helper(root.right, c + 1, target)
		helper(root, 0, target)
		return 0 if find == 0 else find + 1


class Solution:

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

	def getLevel(self, root, target):
		l = [0]
		self.fun(root, 1, target, l)
		return l[0]


class Solution:

	def getLevel(self, root, target, level=1):
		if root is None:
			return 0
		if root.data == target:
			return level
		down = self.getLevel(root.left, target, level + 1)
		if down != 0:
			return down
		down = self.getLevel(root.right, target, level + 1)
		return down


class Solution:

	def solve(self, root, ans, l, target):
		if root == None:
			return
		if root.data == target:
			self.ans = l
			return
		l += 1
		self.solve(root.left, ans, l, target)
		self.solve(root.right, ans, l, target)
		l -= 1

	def getLevel(self, root, target):
		self.ans = 0
		self.solve(root, 0, 1, target)
		return self.ans


class Solution:

	def getLevel(self, root, target):
		q = [root]
		l = [1]
		while q:
			z = q.pop(0)
			lev = l.pop(0)
			if z.data == target:
				return lev
			if z.left:
				q.append(z.left)
				l.append(lev + 1)
			if z.right:
				q.append(z.right)
				l.append(lev + 1)
		return 0


import collections

class Solution:

	def getLevel(self, root, target):
		q = collections.deque()
		q.append(root)
		level = 1
		while q:
			qLen = len(q)
			for i in range(qLen):
				cur = q.popleft()
				if cur.data == target:
					return level
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
			level += 1
		return 0


class Solution:

	def getLevel(self, root, target):
		q = [root]
		level = 0
		ans = 0
		while q:
			level += 1
			for _ in range(len(q)):
				node = q.pop(0)
				if target == node.data:
					ans = level
				if node.left != None:
					q.append(node.left)
				if node.right != None:
					q.append(node.right)
		return ans


class Solution:

	def getLevel(self, root, target):
		level = 1
		q = [(root, level)]
		while len(q) > 0:
			(node, level) = q.pop(0)
			if node.data == target:
				return level
			if node.left:
				q.append((node.left, level + 1))
			if node.right:
				q.append((node.right, level + 1))
		return 0


class Solution:

	def findLevel(self, root, target, level):
		if not root:
			return 0
		if root.data == target:
			return level
		l = self.findLevel(root.left, target, level + 1)
		if l != 0:
			return l
		l = self.findLevel(root.right, target, level + 1)
		return l

	def getLevel(self, root, target):
		return self.findLevel(root, target, 1)


class Solution:

	def getLevel(self, root, target):
		if root is None:
			return 0
		if root.data == target:
			return 1
		ll = self.getLevel(root.left, target)
		lr = self.getLevel(root.right, target)
		if ll:
			return 1 + ll
		elif lr:
			return 1 + lr
		else:
			return 0


def helper(node, data, level):
	if node is None:
		return 0
	if node.data == data:
		return level
	downlevel = helper(node.left, data, level + 1)
	if downlevel != 0:
		return downlevel
	downlevel = helper(node.right, data, level + 1)
	return downlevel

class Solution:

	def getLevel(self, root, target):
		return helper(root, target, 1)


class Solution:

	def getLevel(self, root, target):
		t = 0
		i = 0
		queue = [root]
		level = []
		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 target in l:
				t = i + 1
				break
			queue = level
			level = []
			i += 1
		return t


class Solution:

	def getLevel(self, root, target):
		return self.find(root, target, 1)

	def find(self, root, target, level):
		if root == None:
			return 0
		if root.data == target:
			return level
		l = self.find(root.left, target, level + 1)
		r = self.find(root.right, target, level + 1)
		if l == 0 and r == 0:
			return 0
		if l == 0:
			return r
		return l


class Solution:

	def getLevel(self, root, target):
		queue = [root]
		c = 1
		while queue != []:
			t = []
			for i in range(len(queue)):
				curr = queue[0]
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
				t.append(curr.data)
				queue.pop(0)
			if target in t:
				return c
			c += 1
		return 0


class Solution:

	def getLevel(self, root, target):
		if root.data == target:
			return 1
		q = []
		q.append(root)
		level = 1
		while len(q) > 0:
			for i in range(len(q)):
				temp = q.pop(0)
				if temp.data == target:
					return level
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			level += 1
		return 0


class Solution:

	def getLevel(self, root, target):
		A = []
		self.x(root, A, 1)
		for i in A:
			if i[0] == target:
				return i[1]
		return 0

	def x(self, root, A, level):
		if root is None:
			return
		self.x(root.left, A, level + 1)
		A.append([root.data, level])
		self.x(root.right, A, level + 1)


from collections import deque

class Solution:

	def getLevel(self, root, target):
		if not root:
			return 0
		level = 0
		queue = deque()
		queue.append(root)
		while queue:
			level += 1
			sz = len(queue)
			for _ in range(sz):
				temp = queue.popleft()
				if temp.data == target:
					return level
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
		return 0


class Solution:

	def getLevel(self, root, target):
		to_search = [root]
		level = [1]
		i = 0
		level_no = 0
		while i < len(to_search):
			if to_search[i].data == target:
				level_no = level[i]
				break
			if to_search[i].right is not None:
				to_search.append(to_search[i].right)
				level.append(level[i] + 1)
			if to_search[i].left is not None:
				to_search.append(to_search[i].left)
				level.append(level[i] + 1)
			i += 1
		return level_no


class Solution:

	def sols(self, root, target, x):
		if root == None:
			return 0
		if target > root.data:
			return self.sols(root.right, target, x + 1)
		elif target < root.data:
			return self.sols(root.left, target, x + 1)
		elif target == root.data:
			return x

	def getLevel(self, root, target):
		level = 1
		return self.sols(root, target, level)


class Solution:
	ans = 0

	def recur(self, root, level, target):
		if root == None:
			return
		if root.data == target:
			self.ans = level
		self.recur(root.left, level + 1, target)
		self.recur(root.right, level + 1, target)

	def getLevel(self, root, target):
		self.recur(root, 1, target)
		return self.ans


class Solution:

	def getLevel(self, root, target):
		level = 1
		while root != None:
			if root.data == target:
				return level
			elif root.data < target:
				root = root.right
			else:
				root = root.left
			level += 1
		return 0


def util(root, x, level):
	if root is None:
		return 0
	if root.data == x:
		return level
	ans = util(root.left, x, level + 1)
	if ans != 0:
		return ans
	return util(root.right, x, level + 1)

class Solution:

	def getLevel(self, root, target):
		return util(root, target, 1)


class Solution:

	def getLevel(self, root, target):
		l = 1
		dic = {}
		q = [root]
		while q:
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				dic[node.data] = l
			l += 1
		if target not in dic:
			return 0
		return dic[target]


class Solution:

	def getLevel(self, root, t):
		if root == None:
			return 0
		q = []
		ans = 1
		q.append(root)
		while q:
			n = len(q)
			for i in range(n):
				k = q.pop(0)
				if t == k.data:
					return ans
				if k.left:
					q.append(k.left)
				if k.right:
					q.append(k.right)
			ans += 1
		return 0


class Solution:

	def getLevel(self, root, target):

		def traversal(root, level):
			nonlocal level2
			if root == None:
				return None
			if root.data == target:
				level2 = level
			if root.left:
				traversal(root.left, level + 1)
			if root.right:
				traversal(root.right, level + 1)
		level2 = 0
		traversal(root, 1)
		return level2


class Solution:

	def getLevel(self, root, target):
		q = []
		c = 0
		y = 0
		q.append(root)
		while len(q):
			x = len(q)
			c += 1
			for i in range(x):
				k = q.pop(0)
				if k.data == target:
					y = c
				if k.left:
					q.append(k.left)
				if k.right:
					q.append(k.right)
		if c != 0:
			return y
		return 0


class Solution:

	def getLevel(self, root, target):
		found = False
		foundlevel = 0

		def findKey(root, target, level):
			nonlocal found, foundlevel
			if found == True:
				return
			if root == None:
				return
			if root.data == target:
				found = True
				foundlevel = level
				return
			findKey(root.left, target, level + 1)
			findKey(root.right, target, level + 1)
			return
		findKey(root, target, 1)
		return foundlevel


class Solution:

	def getLevel(self, root, target):
		h = 0
		stack = [root]
		while len(stack) > 0:
			h += 1
			for i in range(len(stack)):
				cur = stack.pop(0)
				if cur.data == target:
					return h
				if cur.left:
					stack.append(cur.left)
				if cur.right:
					stack.append(cur.right)
		return 0


class Solution:

	def getLevel(self, root, target):
		return self.nodeLevel(root, target, 0)

	def nodeLevel(self, root, key, level):
		if not root:
			return 0
		level += 1
		if root.data == key:
			return level
		left = self.nodeLevel(root.left, key, level)
		right = self.nodeLevel(root.right, key, level)
		return left + right


class Solution:

	def getLevel(self, node, data, level=1):
		if node == None:
			return 0
		if node.data == data:
			return level
		downlevel = self.getLevel(node.left, data, level + 1)
		if downlevel != 0:
			return downlevel
		downlevel = self.getLevel(node.right, data, level + 1)
		return downlevel


class Solution:

	def getLevel(self, root, target):
		q = []
		level = 1
		q.append(root)
		q.append('$')
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					q.append('$')
					level += 1
			else:
				if t.data == target:
					return level
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
		return 0


class Solution:

	def getLevel(self, root, target):
		l = 1
		if root is None:
			return 0
		return self.getLevelUtil(root, target, level=l)

	def getLevelUtil(self, root, target, level):
		if root == None:
			return 0
		if root.data == target:
			return level
		downlevel = self.getLevelUtil(root.left, target, level + 1)
		if downlevel != 0:
			return downlevel
		downlevel = self.getLevelUtil(root.right, target, level + 1)
		return downlevel


class Solution:

	def getLevel(self, root, target):
		if root == None:
			return 0
		if root.left == None and root.right == None and (root.data == target):
			return 1

		def helper(root, target):
			if root == None:
				return 0
			dist = 0
			if root.data == target:
				return dist + 1
			dist = helper(root.left, target)
			if dist > 0:
				return dist + 1
			dist = helper(root.right, target)
			if dist > 0:
				return dist + 1
			return dist
		return helper(root, target)


class Solution:

	def trav(self, root, t, l):
		if root != None and root.data == t:
			return l
		if root.left != None:
			a = self.trav(root.left, t, l + 1)
			if a != None:
				return a
		if root.right != None:
			b = self.trav(root.right, t, l + 1)
			if b != None:
				return b

	def getLevel(self, root, target):
		res = self.trav(root, target, 1)
		if res != None:
			return res
		else:
			return 0


class Solution:

	def getLevel(self, root, target):
		d = {}
		level = 1
		self.helper(root, level, d)
		for i in d:
			if target in d[i]:
				return i
		return 0

	def helper(self, root, level, d):
		if not root:
			return
		else:
			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 util(self, root, target, lev):
		if root == None:
			return 0
		if root.data == target:
			return lev
		down = self.util(root.left, target, lev + 1)
		if down != 0:
			return down
		down = self.util(root.right, target, lev + 1)
		return down

	def getLevel(self, root, target):
		return self.util(root, target, 1)


class Solution:

	def getLevel(self, root, target):
		outputValue = []

		def findLevel(root, level):
			if root == None:
				return
			if root.data == target:
				outputValue.append(level)
			findLevel(root.left, level + 1)
			findLevel(root.right, level + 1)
		findLevel(root, 1)
		if len(outputValue) == 0:
			return 0
		return outputValue[0]


class Solution:

	def getLevel(self, root, target):
		lev = 1
		levelFound = self.getLevelUtil(root, target, lev)
		if levelFound:
			return levelFound
		return 0

	def getLevelUtil(self, root, target, lev):
		if not root:
			return None
		if root.data == target:
			return lev
		ltLevel = self.getLevelUtil(root.left, target, lev + 1)
		if ltLevel:
			return ltLevel
		return self.getLevelUtil(root.right, target, lev + 1)


class Solution:

	def getLevel(self, root, target):

		def helper(root, k, target):
			if root:
				if root.data == target:
					return k + 1
				x = helper(root.left, k + 1, target)
				if x:
					return x
				y = helper(root.right, k + 1, target)
				if y:
					return y
		ans = helper(root, 0, target)
		return ans if ans else 0


class Solution:

	def getTree(self, root, arr, d):
		if not root:
			return
		arr.append([root.data, d])
		self.getTree(root.right, arr, d + 1)
		self.getTree(root.left, arr, d + 1)

	def getLevel(self, root, target):
		d = 0
		arr = []
		self.getTree(root, arr, 0)
		for e in arr:
			if target == e[0]:
				return e[1] + 1
		return 0


class Solution:

	def getLevel(self, root, target):
		global k
		k = 0

		def sol(root, level):
			global k
			if root:
				if root.data == target:
					k = level
					return
				sol(root.left, level + 1)
				sol(root.right, level + 1)
		sol(root, 1)
		return k


from collections import deque

class Solution:

	def getLevel(self, root, target):
		q = deque()
		level = 0
		q.append(root)
		while q:
			level += 1
			n = len(q)
			for i in range(n):
				node = q.popleft()
				if node.data == target:
					return level
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return 0


class Solution:

	def getLevel(self, root, k):
		ans = [0]
		lvl = 1
		self.helper(root, k, ans, lvl)
		return ans[0]

	def helper(self, root, k, ans, lvl):
		if root is None:
			return
		if root.data == k:
			ans[0] = lvl
			return
		self.helper(root.left, k, ans, lvl + 1)
		self.helper(root.right, k, ans, lvl + 1)


class Solution:

	def getLevel(self, root, target):

		def helper(x):
			ans = 0
			q = []
			t = 0
			if not x:
				return None
			q.append(x)
			while q:
				l = len(q)
				for i in range(l):
					a = q.pop(0)
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					if a.data == target:
						ans = t + 1
				t += 1
				if ans != 0:
					break
			return ans
		a = helper(root)
		return a


import collections
from collections import deque

class Solution:

	def getLevel(self, root, target):
		res = []
		q = collections.deque()
		q.append(root)
		while q:
			ql = len(q)
			l = []
			for i in range(len(q)):
				x = q.popleft()
				if x:
					l.append(x.data)
					q.append(x.left)
					q.append(x.right)
			if l:
				res.append(l)
		for i in range(len(res)):
			for j in res[i]:
				if j == target:
					return i + 1
		return 0


def calculation(root, target, k):
	if root == None:
		return 0
	if root.data == target:
		return k
	left = calculation(root.left, target, k + 1)
	right = calculation(root.right, target, k + 1)
	return left or right

class Solution:

	def getLevel(self, root, target):
		ans = calculation(root, target, k=1)
		return ans


class Solution:

	def getLevel(self, root, target):
		if root is None:
			return 0
		level = 1
		que = [root]
		while que != []:
			temp = []
			for node in que:
				if node.data == target:
					return level
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
			level += 1
			que = temp
		return 0


class Solution:

	def getLevel(self, root, target):
		if root is None:
			return 0
		q = []
		currLevel = 1
		q.append(root)
		while len(q) > 0:
			size = len(q)
			for i in range(size):
				node = q.pop(0)
				if node.data == target:
					return currLevel
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
			currLevel += 1
		return 0


class Solution:

	def getLevel(self, root, target):

		def helper(root, level, k):
			if not root:
				return 0
			if root.data == k:
				return level
			l = helper(root.left, level + 1, k)
			if l != 0:
				return l
			r = helper(root.right, level + 1, k)
			return r
		res = helper(root, 1, target)
		return res


class Solution:

	def getLevel(self, root, target):

		def rec(root, lvl):
			if not root:
				return 0
			if root.data == target:
				return lvl
			return rec(root.left, lvl + 1) or rec(root.right, lvl + 1)
		return rec(root, 1)


class Solution:

	def getLevel(self, root, target):
		dic = {}
		return self.level(root, dic, target)

	def level(self, root, dic, target):
		q = []
		lev = 0
		i = 0
		q.append(root)
		while q:
			lev += 1
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				dic[node.data] = lev
		if target in dic:
			return dic[target]
		else:
			return 0


class Solution:

	def getLevel(self, root, target):
		stack = [root]
		temp = 1
		while stack:
			k = len(stack)
			for i in range(k):
				p = stack.pop(0)
				if p.data == target:
					return temp
				if p.left:
					stack.append(p.left)
				if p.right:
					stack.append(p.right)
			temp += 1
		return 0


class Solution:

	def getLevel(self, root, target):
		if root is None:
			return 0
		height = self.height(root)
		i = 1
		while i <= height:
			lst = self.levelOrderTrvl(root, i, [])
			if target in lst:
				return i
			i += 1
		return 0

	def levelOrderTrvl(self, root, level, lst):
		if root is None:
			return lst
		if level == 1:
			lst.append(root.data)
		elif level > 1:
			lst = self.levelOrderTrvl(root.left, level - 1, lst)
			lst = self.levelOrderTrvl(root.right, level - 1, lst)
		return lst

	def height(self, root):
		if root is None:
			return 0
		ls = 1 + self.height(root.left)
		rs = 1 + self.height(root.right)
		return max(ls, rs)


class Solution:

	def dump(self, root, target, l):
		if root == None:
			return 0
		if root.data == target:
			return l
		dl = self.dump(root.left, target, l + 1)
		if dl != 0:
			return dl
		dl = self.dump(root.right, target, l + 1)
		return dl

	def getLevel(self, root, target):
		return self.dump(root, target, 1)


class Solution:

	def getLevel(self, root, target):

		def f(root, l):
			if root == None:
				return None
			if root.data == target:
				return l
			x = f(root.left, l + 1)
			if x != None:
				return x
			y = f(root.right, l + 1)
			if y != None:
				return y
		x = f(root, 1)
		if x == None:
			return 0
		return x


class Solution:

	def getLevel(self, root, key):
		q = []
		q.append(root)
		c = 0
		while len(q):
			t = len(q)
			temp = []
			c += 1
			while t > 0:
				t -= 1
				s = q.pop(0)
				if s.data == key:
					return c
				else:
					if s.right:
						q.append(s.right)
					if s.left:
						q.append(s.left)
				temp.append(s.data)
		return 0


class Solution:

	def getLevel(self, root, target):
		if root is None:
			return 0
		if root.data == target:
			return 1
		l = self.getLevel(root.left, target)
		r = self.getLevel(root.right, target)
		if l == 0 and r == 0:
			return 0
		elif l == 0:
			return r + 1
		else:
			return l + 1


class Solution:

	def getLevel(self, root, target):
		q = [[root, 1]]
		c = 0
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			if t.data == target:
				return g
			if t.left:
				q.append([t.left, g + 1])
			if t.right:
				q.append([t.right, g + 1])
			c += 1
		return 0


class Solution:

	def inorder(self, root, target, lvl=1):
		ans = 0
		if root:
			if root.data == target:
				return lvl
			return ans + self.inorder(root.left, target, lvl + 1) + self.inorder(root.right, target, lvl + 1)
		return ans

	def getLevel(self, root, target):
		ans = self.inorder(root, target, 1)
		return ans


class Solution:

	def getLevel(self, root, target, curLevel=1):
		if root.data == target:
			return curLevel
		if root.left is not None:
			leftres = self.getLevel(root.left, target, curLevel + 1)
			if leftres != 0:
				return leftres
		if root.right is not None:
			rightres = self.getLevel(root.right, target, curLevel + 1)
			if rightres != 0:
				return rightres
		return 0


class Node:

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

class Solution:

	def getLevel(self, root, target):
		if root is None:
			return None
		elif root.data == target:
			return 1
		else:
			count = 0
			lst = []
			import collections
			q = collections.deque()
			q.append(root)
			while q:
				for i in range(len(q)):
					node = q.popleft()
					if node.data == target:
						lst.append(count)
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				count = count + 1
			if len(lst) == 0:
				return 0
			else:
				return lst[0] + 1


class Solution:

	def getLevel(self, root, target):
		ans = []
		self.helper(ans, root, target, 1)
		return ans[0] if len(ans) else 0

	def helper(self, ans, root, target, d):
		if not root:
			return
		if root.data == target:
			ans.append(d)
		self.helper(ans, root.right, target, d + 1)
		self.helper(ans, root.left, target, d + 1)


class Solution:

	def getLevel(self, r, t):

		def level(r, t, l):
			if r == None:
				return 0
			if r.data == t:
				return l
			rl = level(r.left, t, l + 1)
			if rl != 0:
				return rl
			return level(r.right, t, l + 1)
		return level(r, t, 1)


class Solution:

	def getLevel(self, root, target):
		(ans, q) = (0, deque())
		q.append(root)
		while q:
			(ans, n) = (ans + 1, len(q))
			for _ in range(n):
				p = q.popleft()
				if p.data == target:
					return ans
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
		return 0