Given a Binary Tree, check if all leaves are at same level or not.
Example 1:
Input: 
            1
          /   \
         2     3
Output: 1
Explanation: 
Leaves 2 and 3 are at same level.
Example 2:
Input:
            10
          /    \
        20      30
       /  \        
     10    15
Output: 0
Explanation:
Leaves 10, 15 and 30 are not at same level.
Your Task:  
You dont need to read input or print anything. Complete the function check() which takes root node as input parameter and returns true/false depending on whether all the leaf nodes are at the same level or not.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
 
Constraints:
1 ≤ N ≤ 10^3

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    #Your task is to complete this function
    #function should return True/False or 1/0
    def check(self, root):
        #Code here


Solutions:
class Solution:

	def check(self, root):
		s = set()

		def dfs(x, h):
			if x.left:
				dfs(x.left, h + 1)
			if x.right:
				dfs(x.right, h + 1)
			if not x.left and (not x.right):
				s.add(h)
		dfs(root, 0)
		return len(s) == 1


class Solution:

	def check(self, root):
		ans = 1
		m = -1

		def solve(root, h):
			nonlocal ans, m
			if root is None:
				return
			if ans == 0:
				return
			if root.left is None and root.right is None:
				if m == -1:
					m = h
				elif m != h:
					ans = 0
				return
			solve(root.left, h + 1)
			solve(root.right, h + 1)
		solve(root, 0)
		return ans


class Solution:

	def check(self, root):

		def leafLeveel(root, firstLeafLevel, level):
			if root == None:
				return True
			elif root.left == None and root.right == None:
				if firstLeafLevel[0] == 0:
					firstLeafLevel[0] = level
					return True
				else:
					if firstLeafLevel[0] == level:
						return True
					return False
			return leafLeveel(root.left, firstLeafLevel, level + 1) and leafLeveel(root.right, firstLeafLevel, level + 1)
		return leafLeveel(root, [0], 0)


class Solution:

	def check(self, root):
		x = []
		l = 0

		def leaf(rt, l, x):
			if rt is None:
				return
			if rt.left is None and rt.right is None:
				x.append(l)
			leaf(rt.left, l + 1, x)
			leaf(rt.right, l + 1, x)
		leaf(root, l, x)
		return len(set(x)) == 1


class Solution:

	def check(self, root):
		x = 0
		y = [root]
		if root.left == None and root.right == None:
			return 1
		while y != []:
			a = len(y)
			b = 0
			for i in range(0, a):
				c = 0
				if y[0].left:
					y.append(y[0].left)
					c = 1
				if y[0].right:
					y.append(y[0].right)
					c = 1
				if c == 0:
					b = 1
				y.pop(0)
			x += b
		if x == 1:
			return 1
		return 0


class Solution:

	def check(self, root):
		x = []
		level = 0

		def checkleaf(root, level, x):
			if root is None:
				return
			if root.left is None and root.right is None:
				x.append(level)
			checkleaf(root.left, level + 1, x)
			checkleaf(root.right, level + 1, x)
		checkleaf(root, level, x)
		return len(set(x)) == 1


from collections import deque

class Solution:

	def check(self, root):
		q = deque()
		q.appendleft(root)
		q.appendleft(None)
		boo = False
		empty = False
		while q:
			p = q.pop()
			if boo and empty:
				return 0
			if p:
				if p.left:
					q.appendleft(p.left)
				if p.right:
					q.appendleft(p.right)
				if not p.left and (not p.right):
					boo = True
			else:
				if q:
					q.appendleft(None)
				if boo:
					empty = True
		return 1


def slove(root, level, ans):
	if root is None:
		return
	if root.left is None and root.right is None:
		ans.append(level)
	slove(root.left, level + 1, ans)
	slove(root.right, level + 1, ans)

class Solution:

	def check(self, root):
		ans = []
		slove(root, 0, ans)
		s = set(ans)
		return len(s) == 1


class Solution:

	def __init__(self):
		self.level = None

	def check(self, root):
		return self.util(root, 0)

	def util(self, root, depth):
		if not root:
			return True
		if not root.left and (not root.right):
			if self.level == None:
				self.level = depth
				return True
			else:
				return self.level == depth
		else:
			return self.util(root.left, depth + 1) and self.util(root.right, depth + 1)


def samelevel(root, level, ans):
	if root == None:
		return
	if root.left == None and root.right == None:
		ans.append(level)
		return
	samelevel(root.left, level + 1, ans)
	samelevel(root.right, level + 1, ans)

class Solution:

	def check(self, root):
		ans = []
		samelevel(root, 0, ans)
		return len(set(ans)) == 1


class Solution:

	def rec_sol(self, root, curr_level, level):
		if root.left == None and root.right == None:
			if len(level) > 0:
				if curr_level != level[0]:
					return 0
				else:
					return 1
			else:
				level.append(curr_level)
		if root.left != None and self.rec_sol(root.left, curr_level + 1, level) == 0:
			return 0
		if root.right != None and self.rec_sol(root.right, curr_level + 1, level) == 0:
			return 0
		return 1

	def check(self, root):
		level = []
		return self.rec_sol(root, 1, level)


class Solution:

	def check(self, root):
		if root == None:
			return True
		return bool(self.find(root))

	def find(self, root, level=1):
		if root == None:
			return None
		left = self.find(root.left, level + 1)
		right = self.find(root.right, level + 1)
		if left == None or right == None:
			return level if left == None and right == None else right if left == None else left
		if left and right:
			return left if left == right else False
		return False


class Solution:

	def check(self, root):

		def same_level(root, level):
			if root is None:
				return True
			if root.left is None and root.right is None:
				if same_level.leaf_level is None:
					same_level.leaf_level = level
				elif level != same_level.leaf_level:
					return False
			return same_level(root.left, level + 1) and same_level(root.right, level + 1)
		same_level.leaf_level = None
		return same_level(root, 0)


class Solution:

	def check(self, root):
		arr = []
		level = 0

		def sameLevel(root, arr, level):
			if root is None:
				return
			if root.left is None and root.right is None:
				arr.append(level)
			sameLevel(root.left, arr, level + 1)
			sameLevel(root.right, arr, level + 1)
		sameLevel(root, arr, level)
		return len(set(arr)) == 1


class Solution:

	def check(self, root):
		s = []
		level = 0

		def solve(root, level, s):
			if root == None:
				return
			if root.left == None and root.right == None:
				s.append(level)
			solve(root.left, level + 1, s)
			solve(root.right, level + 1, s)
		solve(root, level, s)
		s = set(s)
		return len(s) == 1


class Solution:

	def check(self, root):
		self.level = -1

		def rec(root, lev):
			if root == None:
				return True
			elif root.left == None and root.right == None:
				if self.level != -1 and self.level != lev:
					return False
				self.level = lev
				return True
			return rec(root.left, lev + 1) and rec(root.right, lev + 1)
		return rec(root, 0)


from collections import defaultdict

class Solution:

	def solve(self, root, level, _map):
		if root is None:
			return
		if root.left is None and root.right is None:
			_map[level] += 1
		self.solve(root.left, level + 1, _map)
		self.solve(root.right, level + 1, _map)

	def check(self, root):
		if root is None:
			return True
		_map = defaultdict(int)
		level = 0
		self.solve(root, level, _map)
		if len(_map.keys()) == 1:
			return True
		else:
			return False


class Solution:

	def solve(self, root, h):
		if root == None or not self.flg:
			return
		if root.left == None and root.right == None:
			if self.mxh == -1:
				self.mxh = h
			if self.mxh != h:
				self.flg = False
		self.solve(root.left, h + 1)
		self.solve(root.right, h + 1)

	def check(self, root):
		self.flg = 1
		h = 0
		self.mxh = -1
		self.solve(root, h)
		return self.flg


def traverse(root, h, hash_map):
	if root == None:
		return
	else:
		if root.left == None and root.right == None:
			if h not in hash_map:
				hash_map[h] = [root.data]
			else:
				hash_map[h].append(root.data)
		elif root.left == None:
			traverse(root.right, h + 1, hash_map)
		elif root.right == None:
			traverse(root.left, h + 1, hash_map)
		else:
			traverse(root.right, h + 1, hash_map)
			traverse(root.left, h + 1, hash_map)
		return

class Solution:

	def check(self, root):
		if root == None:
			return True
		h = 0
		hash_map = {}
		traverse(root, h, hash_map)
		if len(list(hash_map.keys())) > 1:
			return False
		else:
			return True


class Solution:

	def check(self, root):
		q = [[root, 0]]
		max_level = None
		while q:
			t = q.pop(0)
			temp = t[0]
			level = t[1]
			if not temp.left and (not temp.right):
				if max_level is None:
					max_level = level
				if max_level != level:
					return False
			if temp.left:
				q.append([temp.left, level + 1])
			if temp.right:
				q.append([temp.right, level + 1])
		return True


class Solution:

	def check(self, root):
		q = [[root, 0]]
		end = []
		while q:
			t = q.pop(0)
			temp = t[0]
			level = t[1]
			if not temp.left and (not temp.right):
				end.append(level)
			if temp.left:
				q.append([temp.left, level + 1])
			if temp.right:
				q.append([temp.right, level + 1])
		return len(set(end)) == 1


class Solution:

	def fun(self, root, level, l):
		if root.left == None and root.right == None:
			if level not in l:
				l.append(level)
			return
		if root.left != None:
			self.fun(root.left, level + 1, l)
		if root.right != None:
			self.fun(root.right, level + 1, l)

	def check(self, root):
		l = []
		if root == None:
			return True
		self.fun(root, 0, l)
		return len(l) == 1


class Solution:

	def check(self, root):
		if not root:
			return True
		q = [(root, 0)]
		leaflevel = None
		while q:
			(node, level) = q.pop(0)
			if not node.left and (not node.right):
				if leaflevel is None:
					leaflevel = level
				elif leaflevel != level:
					return False
			if node.left:
				q.append((node.left, level + 1))
			if node.right:
				q.append((node.right, level + 1))
		return True


class Solution:

	def check(self, root):
		if not root:
			return 1
		q = [(root, 0)]
		res = -1
		while q:
			(node, level) = q.pop(0)
			if not node.left and (not node.right):
				if res == -1:
					res = level
				elif res != level:
					return False
			if node.left:
				q.append((node.left, level + 1))
			if node.right:
				q.append((node.right, level + 1))
		return 1


class Solution:

	def check(self, root):
		global firstcheck
		firstcheck = 0

		def helper(root, level):
			global firstcheck
			if root == None:
				return True
			if root.left == None and root.right == None:
				if firstcheck == 0:
					firstcheck = level
				return firstcheck == level
			return helper(root.left, level + 1) and helper(root.right, level + 1)
		return helper(root, 0)


class Solution:

	def check(self, root):
		leafLevel = []

		def dfs(root, depth):
			if not root:
				return [root, 0]
			if not root.left and (not root.right):
				return leafLevel.append(depth)
			l = dfs(root.left, depth + 1)
			r = dfs(root.right, depth + 1)
			return leafLevel
		dfs(root, 0)
		for i in range(1, len(leafLevel)):
			if leafLevel[i] != leafLevel[i - 1]:
				return 0
		return 1


class Solution:

	def check(self, root):
		ans = {}

		def helper(root, lvl):
			if root is None:
				return
			if root.left is None and root.right is None:
				if lvl not in ans.keys():
					ans[lvl] = [root.data]
				else:
					ans[lvl].append(root.data)
			helper(root.left, lvl + 1)
			helper(root.right, lvl + 1)
		helper(root, 0)
		if len(ans) > 1:
			return 0
		return 1


class Solution:

	def check(self, root):
		if not root:
			return 1
		q = [(root, 0)]
		res = set()
		while q:
			(node, level) = q.pop(0)
			if not node.left and (not node.right):
				res.add(level)
			if node.left:
				q.append((node.left, level + 1))
			if node.right:
				q.append((node.right, level + 1))
		return 1 if len(res) == 1 else 0


class Solution:

	def check(self, root):
		self.leave_height = None
		return self._check(root, 0)

	def _check(self, root, height):
		if root is None:
			return True
		if root.left == root.right is None:
			if self.leave_height and height != self.leave_height:
				return False
			else:
				self.leave_height = height
				return True
		return self._check(root.left, height + 1) and self._check(root.right, height + 1)


class Solution:

	def check(self, root):
		q = deque()
		q.append(root)
		while q:
			flag = 0
			i = len(q)
			while i > 0:
				n = q.popleft()
				if n.left == None and n.right == None:
					flag = 1
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
				i -= 1
			if flag == 1:
				if q:
					return False
				else:
					return True


class Solution:

	def check(self, root):
		q = [(root, 0)]
		x = 0
		while q:
			n = len(q)
			for i in range(n):
				curr = q.pop(0)
				node = curr[0]
				level = curr[1]
				if node.left:
					q.append((node.left, level + 1))
				if node.right:
					q.append((node.right, level + 1))
				if node.right == None and node.left == None:
					if x == 0:
						x = level
					elif level != x:
						return 0
		return 1


class Solution:

	def check(self, root):
		self.level = 0

		def checklevel(root, currentlevel):
			if root is None:
				return True
			if root.left is None and root.right is None:
				if self.level == 0:
					self.level = currentlevel
				else:
					return self.level == currentlevel
			return checklevel(root.left, currentlevel + 1) and checklevel(root.right, currentlevel + 1)
		return checklevel(root, 0)


class Solution:

	def solve(self, root, l, dic):
		if root == None:
			return
		if root.left == None and root.right == None:
			if l not in dic:
				dic[l] = [root.data]
			else:
				dic[l].append(root.data)
		l += 1
		self.solve(root.left, l, dic)
		self.solve(root.right, l, dic)

	def check(self, root):
		if root == None:
			return 1
		dic = {}
		self.solve(root, 0, dic)
		if len(dic) > 1:
			return 0
		return 1


from collections import deque

class Solution:

	def check(self, root):
		s = []
		level = 0

		def solve(root, level, s):
			if root == None:
				return
			if root.left == None and root.right == None:
				s.append(level)
			solve(root.left, level + 1, s)
			solve(root.right, level + 1, s)
		solve(root, level, s)
		s = set(s)
		return len(s) == 1


class Solution:

	def check(self, root):
		ans = False
		q = []
		q.append(root)
		while len(q) > 0:
			if ans == True:
				return 0
			else:
				for i in range(len(q)):
					temp = q.pop(0)
					if temp.right == None and temp.left == None:
						ans = True
					if temp.left:
						q.append(temp.left)
					if temp.right:
						q.append(temp.right)
		return 1


class Solution:

	def __init__(self):
		self.check_lvl = 0

	def checkUtil(self, root, level):
		if root is None:
			return True
		if root.left is None and root.right is None:
			if self.check_lvl == 0:
				self.check_lvl = level
				return True
			return level == self.check_lvl
		return self.checkUtil(root.left, level + 1) and self.checkUtil(root.right, level + 1)

	def check(self, root):
		level = 0
		return self.checkUtil(root, level)


class Solution:

	def check(self, root):
		levels = []
		queue = [root]
		level = 0
		while queue:
			val = []
			for i in queue:
				if i == None:
					continue
				if i.left == None and i.right == None:
					levels.append(level)
				val.append(i.left)
				val.append(i.right)
			level += 1
			queue = val
		if len(list(set(levels))) == 1:
			return True
		return False


class Solution:

	def check(self, root):
		level_dict = {}
		self.add_leaf_nodes(root, 0, level_dict)
		if len(level_dict.keys()) > 1:
			return False
		else:
			return True

	def add_leaf_nodes(self, root, level: int, level_dict: {}):
		if root is None:
			return
		self.add_leaf_nodes(root.left, level + 1, level_dict)
		if root.left is None and root.right is None:
			if level in level_dict:
				level_dict[level].append(root.data)
			else:
				level_dict[level] = [root.data]
		self.add_leaf_nodes(root.right, level + 1, level_dict)


class Solution:

	def check(self, root):
		level = [-1]

		def findlevel(root, currlevel):
			if root == None:
				return True
			if root.left == None and root.right == None:
				if level[0] == -1 or level[0] == currlevel:
					level[0] = currlevel
					return True
				else:
					return False
			left = findlevel(root.left, currlevel + 1)
			right = findlevel(root.right, currlevel + 1)
			return left and right
		return findlevel(root, 0)


class Solution:

	def check(self, root):
		global level
		level = -1

		def rec(root, count):
			if not root:
				return True
			global level
			if not root.left and (not root.right):
				if level == -1:
					level = count
				if level != count:
					return False
				return True
			left = rec(root.left, count + 1)
			right = rec(root.right, count + 1)
			return left and right
		return rec(root, 0)


class Solution:

	def check(self, root):
		q = [(root, 0)]
		temp = -1
		while q:
			(node, level) = q.pop(0)
			if not node.left and (not node.right):
				if temp == -1:
					temp = level
				if temp != level:
					return False
			if node.left:
				q.append((node.left, level + 1))
			if node.right:
				q.append((node.right, level + 1))
		return True


class Solution:

	def check(self, root):
		l = []
		depth = 1
		chg(root, l, depth)
		if len(set(l)) == 1:
			return 1
		else:
			return 0

def chg(root, l, depth):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		l.append(depth)
	chg(root.left, l, depth + 1)
	chg(root.right, l, depth + 1)


class Solution(object):

	def check(self, root):

		def DFS(node, level):
			if not node:
				return True
			if not node.left and (not node.right):
				if self.checklevel is None:
					self.checklevel = level
				return self.checklevel == level
			return DFS(node.left, level + 1) and DFS(node.right, level + 1)
		self.checklevel = None
		return DFS(root, 0)


class Solution:

	def check(self, root):
		hmap = {}

		def new(root, level):
			if root is None:
				return
			if root.left is None and root.right is None:
				if level not in hmap:
					hmap[level] = 1
				else:
					hmap[level] += 1
				return
			l = new(root.left, level + 1)
			r = new(root.right, level + 1)
		new(root, 0)
		return len(list(hmap.keys())) == 1


class Solution:

	def f(self, root, x, level):
		if root == None:
			return True
		if root.left == None and root.right == None:
			if x[0] == 1:
				x[0] = level
			elif x[0] != level:
				return False
		return self.f(root.left, x, level + 1) and self.f(root.right, x, level + 1)

	def check(self, root):
		x = [1]
		return self.f(root, x, 1)


class Solution:

	def check(self, root):
		q = []
		q.append(root)
		global dic
		dic = {}
		x = 1
		while q:
			l = len(q)
			for i in range(l):
				temp = q.pop(0)
				if temp.left == None and temp.right == None:
					dic[temp.data] = x
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			x += 1
		lis = []
		for i in dic:
			if dic[i] not in lis:
				lis.append(dic[i])
		if len(lis) == 1:
			return True
		else:
			return False


class Queue:

	def __init__(self):
		self.list_queue = []

	def put(self, data):
		self.list_queue.append(data)

	def get(self):
		return self.list_queue.pop(0)

	def length(self):
		return len(self.list_queue)

	def is_empty(self):
		if len(self.list_queue) > 0:
			return False
		else:
			return True

class Solution:

	def check_if_at_same_level_or_not(self, root, level):
		if root is None:
			return True
		if not root.left and (not root.right):
			if self.leaf_level == 0:
				self.leaf_level = level
			return self.leaf_level == level
		return self.check_if_at_same_level_or_not(root.left, level + 1) and self.check_if_at_same_level_or_not(root.right, level + 1)

	def check(self, root):
		self.leaf_level = 0
		level = 1
		out = self.check_if_at_same_level_or_not(root, level)
		if out:
			return True
		else:
			return False


class Solution:

	def check(self, root):
		boundary = [None]

		def fun(root, level):
			if root == None:
				return True
			if root.left == None and root.right == None:
				if boundary[0] == None:
					boundary[0] = level
				return boundary[0] == level
			return fun(root.right, level + 1) and fun(root.left, level + 1)
		return fun(root, 0)


class Solution:

	def check(self, root):
		flag = True
		return_flag = True
		q = [root]
		while q:
			if not flag:
				return_flag = False
				break
			for _ in range(len(q)):
				node = q.pop(0)
				if not node.left and (not node.right):
					flag = False
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return return_flag


class Solution:

	def check(self, root):
		dir = {}

		def level(root, dir, length):
			if not root:
				return
			if not root.left and (not root.right):
				dir[length] = root.data
			level(root.left, dir, length + 1)
			level(root.right, dir, length + 1)
		level(root, dir, 0)
		return len(dir) == 1