Given a Binary Search Tree that contains positive integer values greater than 0. The task is to complete the function isDeadEnd which returns true if the BST contains a dead end else returns false. Here Dead End means, we are not able to insert any element after that node.
Example 1:
Input :   
               8
             /   \ 
           5      9
         /  \     
        2    7 
       /
      1     
          
Output : 
Yes
Explanation : 
Node "1" is the dead End because after that 
              we cant insert any element.
Example 2: 
Input :     
              8
            /   \ 
           7     10
         /      /   \
        2      9     13
Output : 
Yes
Explanation : 
We can't insert any element at 
              node 9.   
Your Task:
You don't have to input or print anything. Complete the function isDeadEnd() which takes the input parameter head and returns a boolean value.
Expected Time Complexity: O(N) where N is the Number of nodes in a given binary tree.Expected Space Complexity: O(N)
Constraints:
1<=T<=100
1<=N<=200

Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries
Skill types: Data structures

Range queries
Expected Time Complexity: O(N) where N is the Number of nodes in a given binary tree.Expected Space Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
# Your task is to complete this function

# function should return true/false or 1/0

def isdeadEnd(root):

    # Code here

Solutions:
def slove(root, mini, maxi):
	if root is None:
		return
	if mini == maxi:
		return True
	return slove(root.left, mini, root.data - 1) or slove(root.right, root.data + 1, maxi)

def isdeadEnd(root):
	return slove(root, 1, 9999999)


def slove(root, all, leaf):
	if root is None:
		return
	all.add(root.data)
	if root.left is None and root.right is None:
		leaf.add(root.data)
		return
	slove(root.left, all, leaf)
	slove(root.right, all, leaf)

def isdeadEnd(root):
	if root is None:
		return
	all = set()
	leaf = set()
	all.add(0)
	slove(root, all, leaf)
	for i in leaf:
		if i + 1 in all and i - 1 in all:
			return True
	return False


def isdeadEnd(root):

	def isDead(root, mini, maxi):
		if root is None:
			return False
		if mini == maxi:
			return True
		return isDead(root.left, mini, root.data - 1) or isDead(root.right, root.data + 1, maxi)
	return isDead(root, 1, float('inf'))


def solve(root, mini, mx):
	if root == None:
		return False
	if mini == mx:
		return True
	return solve(root.left, mini, root.data - 1) or solve(root.right, root.data + 1, mx)

def isdeadEnd(root):
	mini = 1
	mx = 99999
	return solve(root, mini, mx)


from sys import maxsize

def solve(root, INT_MIN, INT_MAX):
	if root is None:
		return False
	if root.left is None and root.right is None:
		if abs(INT_MAX - root.data) == 1 and abs(INT_MIN - root.data) == 1:
			return True
	first = solve(root.left, INT_MIN, root.data)
	second = solve(root.right, root.data, INT_MAX)
	return first or second

def isdeadEnd(root):
	INT_MAX = maxsize
	INT_MIN = 0
	return solve(root, INT_MIN, INT_MAX)


def isdeadEnd(root):
	allnodes = {}

	def findallNodes(root):
		if root is None:
			return
		allnodes[root.data] = 1
		findallNodes(root.left)
		findallNodes(root.right)

	def check(root):
		if root is None:
			return False
		if root.left is None and root.right is None:
			pre = root.data - 1
			next = root.data + 1
			if allnodes.get(pre) is not None and allnodes.get(next) is not None:
				return True
		return check(root.left) or check(root.right)

	def isDeadEnd(root):
		if root is None:
			return False
		allnodes[0] = 1
		findallNodes(root)
		return check(root)
	return isDeadEnd(root)


def isdeadEnd(root):

	def solve(root, lb, ub):
		if not root:
			return False
		if lb == ub:
			return True
		left = solve(root.left, lb, root.data - 1)
		right = solve(root.right, root.data + 1, ub)
		if left or right:
			return True
		return False
	return solve(root, 1, float('inf'))


def isdeadEnd(root):
	s1 = set()
	s2 = set()

	def helper(root):
		if root == None:
			return
		if root.left == None and root.right == None:
			s2.add(root.data)
		s1.add(root.data)
		helper(root.left)
		helper(root.right)
	helper(root)
	s1.add(0)
	for i in s2:
		if i - 1 in s1 and i + 1 in s1:
			return True
	return False


def maximin(root, mini, maxi):
	if not root:
		return False
	if mini == maxi:
		return True
	return maximin(root.left, mini, root.data - 1) or maximin(root.right, root.data + 1, maxi)

def isdeadEnd(root):
	return maximin(root, 1, float('inf'))

def isleaf(root, leaf):
	if not root:
		return leaf
	if not root.left and (not root.right):
		leaf.append(root.data)
	isleaf(root.left, leaf)
	isleaf(root.right, leaf)
	return leaf

def issolution(root, res, leaf):
	if not root:
		return (res, leaf)
	issolution(root.left, res, leaf)
	if not root.left and (not root.right):
		leaf.append(root.data)
	else:
		res.append(root.data)
	issolution(root.right, res, leaf)
	return (res, leaf)


def isdeadEnd(root):
	(res, leaf) = ([], [])
	(res, leaf) = issolution(root, res, leaf)
	for i in leaf:
		if i == 1 and i + 1 in res:
			return True
		if i - 1 in res and i + 1 in res:
			return True
	return False

def isleaf(root, leaf):
	if not root:
		return leaf
	if not root.left and (not root.right):
		leaf.append(root.data)
	isleaf(root.left, leaf)
	isleaf(root.right, leaf)
	return leaf

def issolution(root, res, leaf):
	if not root:
		return (res, leaf)
	issolution(root.left, res, leaf)
	if not root.left and (not root.right):
		leaf.append(root.data)
	else:
		res.append(root.data)
	issolution(root.right, res, leaf)
	return (res, leaf)


def isdeadEnd(root):
	result_arr = [False]
	in_order_util(root, 1, float('inf'), result_arr)
	return result_arr[0]

def in_order_util(root, lowest_range, highest_range, result_arr: []):
	if root is None:
		return
	in_order_util(root.left, lowest_range, root.data - 1, result_arr)
	if root.left is None and root.right is None:
		if lowest_range == root.data and highest_range == root.data:
			result_arr[0] = True
	in_order_util(root.right, root.data + 1, highest_range, result_arr)


def isdeadEnd(root):

	def helper(root, lower, higher):
		if not root:
			return False
		if lower == higher:
			return True
		return helper(root.left, lower, root.data - 1) or helper(root.right, root.data + 1, higher)
	return helper(root, 1, 57777)


def isdeadEnd(root):
	inc = set()
	inc.add(0)

	def inor(root):
		if root == None:
			return True
		if root.left == None and root.right == None and (root.data - 1 in inc) and (root.data + 1 in inc):
			return False
		inc.add(root.data)
		return inor(root.left) and inor(root.right)
	return not inor(root)


def isdeadEnd(root):

	def helper(root, lower, upper):
		if not root:
			return False
		x = root.data
		if lower == upper or x in seen:
			return True
		seen[x] = 1
		left = helper(root.left, lower, x - 1)
		right = helper(root.right, x + 1, upper)
		return left or right
	seen = {}
	return helper(root, 1, 1000.0)


def isdeadEnd(root):

	def helper(root, lower, upper):
		if not root:
			return False
		if lower == upper:
			return True
		if root.data in seen:
			return True
		seen[root.data] = 1
		left = helper(root.left, lower, root.data - 1)
		right = helper(root.right, root.data + 1, upper)
		return left or right
	seen = {}
	return helper(root, 1, 120)


def isdeadEnd(root):

	def helper(root, lower, upper):
		if not root:
			return False
		if lower == upper:
			return True
		if root.data in seen:
			return True
		seen.add(root.data)
		left = helper(root.left, lower, root.data - 1)
		right = helper(root.right, root.data + 1, upper)
		return left or right
	seen = set()
	return helper(root, 1, 200)


import sys

def f(root, mini, maxi):
	if root == None:
		return False
	if root.left == None and root.right == None:
		if root.data - mini - 1 <= 0 and maxi - root.data - 1 <= 0:
			return True
	return f(root.left, mini, root.data) or f(root.right, root.data, maxi)

def isdeadEnd(root):
	return f(root, 1, sys.maxsize)


def isdeadEnd(root):
	res = []
	de = []
	(de, res) = dead(root, de, res)
	for i in de:
		if i == 1 and i + 1 in res:
			return True
		if i - 1 in res and i + 1 in res:
			return True
	return False

def dead(root, de, res):
	if not root:
		return (de, res)
	if not root.left and (not root.right):
		de.append(root.data)
		return (de, res)
	else:
		res.append(root.data)
	dead(root.left, de, res)
	dead(root.right, de, res)
	return (de, res)


def Preorder(root, allnodes, leafnodes):
	if root == None:
		return
	allnodes[root.data] = 1
	if root.left == None and root.right == None:
		leafnodes[root.data] = 1
		return
	Preorder(root.left, allnodes, leafnodes)
	Preorder(root.right, allnodes, leafnodes)

def isdeadEnd(root):
	allnodes = {}
	leafnodes = {}
	allnodes[0] = 1
	Preorder(root, allnodes, leafnodes)
	for key in leafnodes:
		if key - 1 in allnodes and key + 1 in allnodes:
			return True
	return False


def isdeadEnd(root):
	leaf_nodes = []
	node_dict = {}
	queue = []
	if root.left is not None or root.right is not None:
		node_dict[root.data] = 1
	if root.left is not None:
		queue.append(root.left)
	if root.left is not None:
		queue.append(root.right)
	while queue != []:
		temp = queue.pop(0)
		if temp and temp.left is None and (temp.right is None):
			leaf_nodes.append(temp.data)
		elif temp:
			node_dict[temp.data] = 1
			if temp.left is None and temp.right is not None:
				queue.append(temp.right)
			elif temp.right is None and temp.left is not None:
				queue.append(temp.left)
			else:
				queue.append(temp.left)
				queue.append(temp.right)
	for i in leaf_nodes:
		if i == 1 and i + 1 in node_dict:
			return 1
		if i - 1 in node_dict and i + 1 in node_dict:
			return 1
	return 0


def isdeadEnd(root):
	if root is None:
		return False
	num = set()
	leaf = set()
	q = []
	q.append(root)
	while len(q) > 0:
		num.add(q[0].data)
		node = q.pop(0)
		if node.left is None and node.right is None:
			leaf.add(node.data)
		if node.left is not None:
			q.append(node.left)
		if node.right is not None:
			q.append(node.right)
	num.add(0)
	for i in leaf:
		if i + 1 in num and i - 1 in num:
			return True
	return False


def isdeadEnd(root):
	d = {}
	d[0] = True

	def filld(root, d):
		if not root:
			return
		d[root.data] = True
		filld(root.left, d)
		filld(root.right, d)

	def check(d, root):
		if not root:
			return False
		r = root
		if not (r.left or r.right):
			if r.data - 1 in d and r.data + 1 in d:
				return True
			else:
				return False
		return check(d, root.left) or check(d, root.right)
	filld(root, d)
	return 1 if check(d, root) else 0


def isdeadEnd(root):

	def helper(mn, mx, node):
		if not node:
			return False
		if mn >= mx:
			return True
		else:
			return helper(mn, node.data - 1, node.left) or helper(node.data + 1, mx, node.right)
	return helper(1, 1000000000.0, root)


def isdeadEnd(root):
	stack = [root]
	map1 = {}
	lnodes = []
	while stack:
		x = stack.pop(0)
		if x.data in map1:
			map1[x.data] += 1
		else:
			map1[x.data] = 1
		if x.right:
			stack.append(x.right)
		if x.left:
			stack.append(x.left)
		if x.left == None and x.right == None:
			lnodes += [x.data]
	lnodes.sort()
	for item in lnodes:
		if item == 1 and item + 1 in map1:
			return True
		elif item + 1 in map1 and item - 1 in map1:
			return True
	return False


def isdeadEnd(root):
	nodes = []
	leaf = []

	def inorder(node):
		if not node:
			return
		inorder(node.left)
		if not node.left and (not node.right):
			leaf.append(node.data)
		else:
			nodes.append(node.data)
		inorder(node.right)
	inorder(root)
	for i in leaf:
		if (i - 1 == 0 or i - 1 in nodes) and i + 1 in nodes:
			return True
	return False


def isdeadEnd(root):
	array = [0]
	leafnodes = []
	inorder(root, array, leafnodes)
	for i in leafnodes:
		if i + 1 in array and i - 1 in array:
			return True
	return False

def inorder(root, array, leafnodes):
	if root is not None:
		inorder(root.left, array, leafnodes)
		array.append(root.data)
		if root.left is None and root.right is None:
			leafnodes.append(root.data)
		inorder(root.right, array, leafnodes)


import math as m

def helper(root, mini, maxi):
	if not root:
		return False
	if mini == maxi:
		return True
	left = helper(root.left, mini, root.data - 1)
	right = helper(root.right, root.data + 1, maxi)
	return left or right

def isdeadEnd(root):
	return helper(root, 1, m.inf)


def solve(root, q, leaf):
	if root is None:
		return
	solve(root.left, q, leaf)
	if root.left is None and root.right is None:
		leaf.append(root.data)
	else:
		q.append(root.data)
	solve(root.right, q, leaf)

def isdeadEnd(root):
	q = []
	isdead = False
	leaf = []
	solve(root, q, leaf)
	for i in leaf:
		if (i - 1 == 0 or i - 1 in q) and i + 1 in q:
			return 1
	return 0


def find(root, mi, ma):
	if root is None:
		return 0
	if ma - mi <= 2:
		return 1
	return find(root.left, mi, root.data) or find(root.right, root.data, ma)

def isdeadEnd(root):
	return find(root, 0, 10000000)


def isdeadEnd(root):
	visited = set()

	def fun(node):
		if not node:
			return
		visited.add(node.data)
		fun(node.left)
		fun(node.right)
	fun(root)
	visited.add(0)

	def fun2(node):
		if not node:
			return False
		if not node.left and (not node.right):
			prev = node.data - 1
			nextv = node.data + 1
			if prev in visited and nextv in visited:
				return True
		return fun2(node.left) or fun2(node.right)
	return fun2(root)


def isdeadEnd(root):

	def check(node, left, right, flag):
		if node is None:
			return
		if flag[0] == True:
			return
		if node.left is None and node.right is None:
			if left == right:
				flag[0] = True
				return
		check(node.left, left, node.data - 1, flag)
		check(node.right, node.data + 1, right, flag)
	flag = [False]
	check(root, 1, float('inf'), flag)
	return flag[0]


def isdeadEnd(root):

	def dfs(root, s, r):
		if root == None:
			return False
		if s == r:
			return True
		return dfs(root.left, s, root.data - 1) or dfs(root.right, root.data + 1, r)
	return dfs(root, s=1, r=float('inf'))


def solve(root, mini, maxi):
	if not root:
		return False
	if mini == maxi:
		return True
	return solve(root.left, mini, root.data - 1) or solve(root.right, root.data + 1, maxi)

def isdeadEnd(root):
	return solve(root, 1, float('inf'))


def isdeadEnd(root):

	def func(root, mini, maxi):
		if root is None:
			return 0
		if root.data - 1 <= mini and root.data + 1 >= maxi:
			return 1
		left = func(root.left, mini, root.data)
		right = func(root.right, root.data, maxi)
		if left or right:
			return 1
		return 0
	return func(root, 0, float('inf'))


def isdeadEnd(root):

	def solve(root, min, max):
		if root == None:
			return False
		if min == max:
			return True
		return solve(root.left, min, root.data - 1) or solve(root.right, root.data + 1, max)
	min = 1
	max = 99999
	return solve(root, min, max)


def isdeadEnd(root):
	arr = []
	flag = 0
	flag = is_dead(arr, root, flag)
	return flag

def is_dead(arr, root, flag):
	if root is None:
		return 0
	arr.append(root.data)
	temp_1 = 0
	temp_2 = 0
	if root.left is None:
		if root.data - 1 in arr or root.data == 1:
			temp_1 = 1
	if root.right is None:
		if root.data + 1 in arr:
			temp_2 = 1
	if temp_1 == 1 and temp_2 == 1:
		return 1
	flag = is_dead(arr, root.left, flag)
	if flag == 1:
		return 1
	flag = is_dead(arr, root.right, flag)
	if flag == 1:
		return 1
	return 0


def isdeadEnd(root):
	A = []
	B = []
	s(root, A, B)
	for i in B:
		if i == 1 and 2 in A:
			return 1
		elif i + 1 in A and i - 1 in A:
			return 1
	return 0

def s(root, A, B):
	if root is None:
		return
	if root.left is None and root.right is None:
		B.append(root.data)
		A.append(root.data)
		return
	s(root.left, A, B)
	A.append(root.data)
	s(root.right, A, B)


def isLeaf(root):
	if root.left == root.right == None:
		return 1
	return 0

def makeSet(root, s):
	if not root:
		return
	s.add(root.data)
	makeSet(root.left, s)
	makeSet(root.right, s)

def check(root, s):
	if not root:
		return 0
	if root.left == root.right == None:
		prev = root.data - 1
		nex = root.data + 1
		if prev in s and nex in s:
			return 1
	left = check(root.left, s)
	right = check(root.right, s)
	return left or right

def isdeadEnd(root):
	if not root:
		return 0
	s = set()
	makeSet(root, s)
	s.add(0)
	return check(root, s)


def isdeadEnd(root):
	left = 1
	right = float('inf')

	def check_deadend(root, left, right):
		if root == None:
			return 0
		if left == right:
			return 1
		return check_deadend(root.left, left, root.data - 1) or check_deadend(root.right, root.data + 1, right)
	return check_deadend(root, left, right)


def isdeadEnd(root):
	all_nodes = set()
	leaf_nodes = set()
	_in_order_traversal(root, all_nodes, leaf_nodes)
	all_nodes.add(0)
	return _check_dead_end(all_nodes, leaf_nodes)

def _check_dead_end(all_nodes, leaf_nodes):
	_dead_end = False
	for _ in leaf_nodes:
		if _ + 1 in all_nodes and _ - 1 in all_nodes:
			_dead_end = True
			break
	return _dead_end

def _in_order_traversal(root, all_nodes, leaf_nodes):
	if root:
		_in_order_traversal(root.left, all_nodes, leaf_nodes)
		all_nodes.add(root.data)
		if not root.left and (not root.right):
			leaf_nodes.add(root.data)
		_in_order_traversal(root.right, all_nodes, leaf_nodes)


def isdeadEnd(root):
	l = 1
	r = float('inf')

	def check(root, l, r):
		if root is None:
			return 0
		if l == r or l > r:
			return 1
		return check(root.left, l, root.data - 1) or check(root.right, root.data + 1, r)
	return check(root, l, r)


import math
ans = False

def dfs(root, s=1, e=math.inf):
	if root is None:
		return False
	(ls, le) = [s, root.data]
	(rs, re) = [root.data + 1, e]
	if ls == le and rs == re:
		return True
	if dfs(root.left, ls, le):
		return True
	if dfs(root.right, rs, re):
		return True
	return False

def isdeadEnd(root):
	return dfs(root)


def solve(node, minR, maxR):
	if not node:
		return False
	if minR == maxR:
		return True
	return solve(node.left, minR, node.data - 1) or solve(node.right, node.data + 1, maxR)

def isdeadEnd(node):
	if not node:
		return
	return solve(node, 1, float('Inf'))


def isdeadEnd(root):
	setti = set([0])
	return itemsInTree(root, setti)

def itemsInTree(root, setti):
	if not root:
		return 0
	if root.data + 1 in setti and root.data - 1 in setti:
		return 1
	setti.add(root.data)
	check1 = itemsInTree(root.left, setti)
	check2 = itemsInTree(root.right, setti)
	return any([check1, check2])


def seroot(root, all, leaf):
	if not root:
		return
	all.add(root.data)
	if not root.left and (not root.right):
		leaf.add(root.data)
		return
	seroot(root.left, all, leaf)
	seroot(root.right, all, leaf)

def isdeadEnd(root):
	if not root:
		return
	all = set()
	all.add(0)
	leaf = set()
	seroot(root, all, leaf)
	for i in leaf:
		if i - 1 in all and i + 1 in all:
			return True
	return False


def isdeadEnd(root):

	def helper(node):
		if not node:
			return
		all_nodes.add(node.data)
		if not node.left and (not node.right):
			leaf_nodes.add(node.data)
			return
		helper(node.left)
		helper(node.right)
	if not root:
		return False
	all_nodes = set()
	leaf_nodes = set()
	all_nodes.add(0)
	helper(root)
	for l in leaf_nodes:
		if l + 1 in all_nodes and l - 1 in all_nodes:
			return True
	return False


def isdeadEnd(root):

	def storeNodes(root):
		if not root:
			return
		all_nodes.add(root.data)
		if not root.left and (not root.right):
			leaf_nodes.add(root.data)
			return
		storeNodes(root.left)
		storeNodes(root.right)
	all_nodes = set()
	leaf_nodes = set()
	if root == None:
		return False
	all_nodes.add(0)
	storeNodes(root)
	for x in leaf_nodes:
		if x + 1 in all_nodes and x - 1 in all_nodes:
			return True
	return False


def isdeadEnd(root):

	def insert(node, key):
		if not node:
			return newNode(key)
		if key < node.data:
			node.left = insert(node.left, key)
		elif key > node.data:
			node.right = insert(node.right, key)
		return node

	def storeNodes(root):
		if not root:
			return
		all_nodes.add(root.data)
		if not root.left and (not root.right):
			leaf_nodes.add(root.data)
			return
		storeNodes(root.left)
		storeNodes(root.right)
	all_nodes = set()
	leaf_nodes = set()
	if root == None:
		return False
	all_nodes.add(0)
	storeNodes(root)
	for x in leaf_nodes:
		if x + 1 in all_nodes and x - 1 in all_nodes:
			return True
	return False


def isdeadEnd(root):
	res = []
	leaf = []

	def dfs(root):
		if root == None:
			return
		dfs(root.left)
		if not root.left and (not root.right):
			leaf.append(root.data)
		else:
			res.append(root.data)
		dfs(root.right)
	dfs(root)
	for i in leaf:
		if (i - 1 == 0 or i - 1 in res) and i + 1 in res:
			return True
	return False


def isdeadEnd(root):
	MINI = 1
	MAXI = float('inf')

	def dfs(node, mini, maxi):
		if node.left == None and node.right == None:
			if mini >= maxi:
				return True
		if node.left != None and dfs(node.left, mini, node.data - 1):
			return True
		if node.right != None and dfs(node.right, node.data + 1, maxi):
			return True
		return False
	ans = dfs(root, MINI, MAXI)
	return ans


def isdeadEnd(root):
	hash = set()
	hash.add(0)

	def dfs(root):
		if not root:
			return False
		hash.add(root.data)
		if root.data + 1 in hash and root.data - 1 in hash:
			return True
		left = dfs(root.left)
		right = dfs(root.right)
		if left or right:
			return True
		return False
	return dfs(root)


def isdeadEnd(root):
	return dfs(root, float('inf'), float('-inf'))

def dfs(n, mn, mx):
	if not n:
		return False
	if n.left is None and n.right is None:
		return (n.data - 1 == mn or n.data == 1) and n.data + 1 == mx
	return dfs(n.left, mn, n.data) or dfs(n.right, n.data, mx)


def Util(root, nodes, leaves):
	if root == None:
		return
	nodes[root.data] = 1
	if root.left == None and root.right == None:
		leaves.append(root.data)
	Util(root.left, nodes, leaves)
	Util(root.right, nodes, leaves)

def isdeadEnd(root):
	nodes = {}
	leaves = []
	Util(root, nodes, leaves)
	for l in leaves:
		if l != 1:
			if l + 1 in nodes.keys() and l - 1 in nodes.keys():
				return 1
		elif l + 1 in nodes.keys():
			return 1
	return 0


def sol(root, min, max):
	if not root:
		return False
	if min == max:
		return True
	return sol(root.left, min, root.data - 1) or sol(root.right, root.data + 1, max)

def isdeadEnd(root):
	return sol(root, 1, float('inf'))


def isdeadEnd(root):

	def dfs(root, l, r):
		if not root:
			return False
		if root.data + 1 == r and root.data - 1 == l:
			return True
		x = dfs(root.left, l, root.data)
		y = dfs(root.right, root.data, r)
		return x or y
	return dfs(root, 0, float('inf'))


def isdeadEnd(root):

	def solve(root, minn, maxx):
		if root == None:
			return False
		if minn == maxx:
			return True
		return solve(root.left, minn, root.data - 1) or solve(root.right, root.data + 1, maxx)
	return solve(root, 1, 10000000000.0)


def isdeadEnd(root):

	def fun(root, minn, maxx):
		if root == None:
			return False
		if minn == maxx:
			return True
		return fun(root.left, minn, root.data - 1) or fun(root.right, root.data + 1, maxx)
	return fun(root, 1, 100000000)


import math

def helper(root, left_range, right_range):
	if not root:
		return False
	if not root.right and (not root.left):
		return left_range == right_range
	left = helper(root.left, left_range, root.data - 1)
	right = helper(root.right, root.data + 1, right_range)
	if left or right:
		return True
	else:
		return False

def isdeadEnd(root):
	return helper(root, 1, math.inf)


def getnodes(root, fullBST, leafNode):
	if not root:
		return
	if not root.left and (not root.right):
		leafNode.append(root.data)
	fullBST.append(root.data)
	getnodes(root.left, fullBST, leafNode)
	getnodes(root.right, fullBST, leafNode)

def isdeadEnd(root):
	fullBST = []
	leafNode = []
	getnodes(root, fullBST, leafNode)
	setfullBST = set(fullBST)
	for i in range(len(leafNode)):
		if (leafNode[i] - 1 in setfullBST or leafNode[i] - 1 == 0) and leafNode[i] + 1 in setfullBST:
			return True
	return False


def isdeadEnd(root):
	if root is None:
		return False

	def solve(root, res):
		if root is None:
			return False
		if root.left is None and root.right is None:
			if root.data - 1 in res and root.data + 1 in res:
				return True
			return False
		res.append(root.data)
		temp = solve(root.left, res) or solve(root.right, res)
		return temp
	res = [0]
	return solve(root, res)


def isdeadEnd(root):

	def dfs(root, l, r):
		if not root:
			return False
		if l >= r:
			return True
		return dfs(root.left, l, root.data - 1) or dfs(root.right, root.data + 1, r)
	return dfs(root, 1, 1000000000.0)


def isdeadEnd(root):
	nodes = []
	leafs = []

	def inorder(root):
		if root == None:
			return
		inorder(root.left)
		if root.left == None and root.right == None:
			leafs.append(root.data)
		else:
			nodes.append(root.data)
		inorder(root.right)
	inorder(root)
	for i in leafs:
		if (i - 1 == 0 or i - 1 in nodes) and i + 1 in nodes:
			return True
	return False