Given a binary tree, find its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input:
 root  -->     1
                      /   \
                    3      2
                  /
                4           
Output: 3
Explanation:
Maximum depth is between nodes 1 and 4, which is 3.
Example 2:
Input:
 root -->    10
           /    \
          20    30
           \      \  
           40     60
                  /
                 2 
Output: 4
Explanation:
Maximum depth is between nodes 10 and 2, which is 4
Your Task:  
You don't need to read input or print anything. Complete the function maxDepth() which takes the root node as an input parameter and returns the maximum depth.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of the tree)
 
Constraints:
1 ≤ N ≤ 10^5

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of the tree)

Starter code:
#User function Template for python3



class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None



class Solution:

    def maxDepth(self,root):

        pass

    

Solutions:
import sys
sys.setrecursionlimit(10 ** 6)

class Node:

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

class Solution:

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


class Node:

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

class Solution:

	def maxDepth(self, root):
		if root:
			level = 0
			q = []
			q.append(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)
				level += 1
		return level


class Node:

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

class Solution:

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


class Node:

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

class Solution:

	def maxDepth(self, root):
		m = 0
		s = [(root, 1)]
		while len(s) > 0:
			(curr, depth) = s.pop()
			if depth > m:
				m = depth
			if curr.left:
				s.append((curr.left, depth + 1))
			if curr.right:
				s.append((curr.right, depth + 1))
		return m


class Node:

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

class Solution:

	def maxDepth(self, root):
		if not root:
			return 0
		queue = [[root]]
		height = 1
		while queue:
			level = queue.pop(0)
			temp = []
			for node in level:
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
			if temp:
				queue.append(temp)
				height += 1
		return height


class Node:

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

class Solution:

	def maxDepth(self, root):
		queue = [root]
		h = 0
		while queue:
			size = len(queue)
			h += 1
			for i in range(size):
				node = queue.pop(0)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return h


class Node:

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

class Solution:

	def maxDepth(self, root: Node) -> int:
		if root is None:
			return 0
		stack = [(root, 1)]
		max_depth = 0
		while stack:
			(node, depth) = stack.pop()
			if node.left is None and node.right is None:
				max_depth = max(max_depth, depth)
			if node.left:
				stack.append((node.left, depth + 1))
			if node.right:
				stack.append((node.right, depth + 1))
		return max_depth


from collections import deque

class Node:

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

class Solution:

	def maxDepth(self, root):
		if not root:
			return 0
		else:
			queue = deque()
			queue.append(root)
			level = 0
			while queue:
				n = len(queue)
				for i in range(n):
					node = queue.popleft()
					if node.left is not None:
						queue.append(node.left)
					if node.right is not None:
						queue.append(node.right)
				level += 1
		return level


import sys
sys.setrecursionlimit(150000)

class Node:

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

class Solution:

	def maxDepth(self, root):
		if not root:
			return 0
		return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1


class Node:

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

class Solution:

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

	def maxDepth(self, root):
		arr = []
		try:
			self.depthT(root, arr, 1)
		except Exception as e:
			return 10000
		l = len(arr)
		d = arr[len(arr) - 1][1]
		if l > 1:
			d2 = arr[l - 2][1]
		if d2 > d:
			return d2
		return d


class Node:

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

class Solution:

	def maxDepth(self, root):
		stack = [root]
		node_at_each_level = 1
		height = 0
		while len(stack) > 0:
			x = stack.pop(0)
			node_at_each_level -= 1
			if x.left:
				stack.append(x.left)
			if x.right:
				stack.append(x.right)
			if node_at_each_level == 0:
				height += 1
				node_at_each_level = len(stack)
		return height


class Node:

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

class Solution:

	def maxDepth(self, root):
		stack = [root]
		node_at_each_level = 1
		height = 0
		while len(stack) > 0:
			n = len(stack)
			for i in range(n):
				x = stack.pop(0)
				if x.left:
					stack.append(x.left)
				if x.right:
					stack.append(x.right)
			height += 1
		return height


import sys
sys.setrecursionlimit(10 ** 5 + 1)

class Node:

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

class Solution:

	def maxDepth(self, root):
		if root is None:
			return 0
		x = self.maxDepth(root.left)
		y = self.maxDepth(root.right)
		return max(x, y) + 1


import sys
sys.setrecursionlimit(100000)

class Node:

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

class Solution:

	def solve(self, root):
		if root == None:
			return 0
		return 1 + max(self.solve(root.left), self.solve(root.right))

	def maxDepth(self, root):
		if root == None:
			return 0
		return self.solve(root)


class Node:

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

class Solution:

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


from collections import deque

class Node:

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

class Solution:

	def maxDepth(self, root):
		if root is None:
			return 0
		(q, depth) = (deque(), 1)
		q.append(root)
		while q:
			size = len(q)
			for _ in range(size):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if q:
				depth += 1
		return depth


class Node:

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

class Solution:

	def maxDepth(self, root):
		main = [root]
		lev = 0
		while main:
			c = main.copy()
			main.clear()
			lev += 1
			for x in c:
				if x.left != None:
					main.append(x.left)
				if x.right != None:
					main.append(x.right)
		return lev


class Node:

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

class Solution:

	def maxDepth(self, root):
		if root == None:
			return 0
		level = 0
		curLevel = [root]
		nextLevel = []
		while curLevel:
			for node in curLevel:
				if node.left != None:
					nextLevel.append(node.left)
				if node.right != None:
					nextLevel.append(node.right)
			level += 1
			curLevel = nextLevel
			nextLevel = []
		return level


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
from collections import deque

class Solution:

	def maxDepth(self, root):
		if not root:
			return 1
		q = deque()
		q.append(root)
		hgt = 0
		while q:
			l = len(q)
			for i in range(l):
				k = q.popleft()
				if k.left:
					q.append(k.left)
				if k.right:
					q.append(k.right)
			hgt += 1
		return hgt


class Solution:

	def maxDepth(self, root):
		pass
		(c, l) = (0, 1)
		s = [root, None]
		while s != []:
			a = s.pop(0)
			if a == None and len(s) == 0:
				break
			elif a == None:
				l += 1
				s += [None]
				continue
			if a.left != None:
				s += [a.left]
			if a.right != None:
				s += [a.right]
		return l


class Node:

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

class Solution:

	def maxDepth(self, root):
		queue = deque([(root, 1)])
		height = 0
		while queue:
			(node, h) = queue.popleft()
			if node.left is None and node.right is None:
				height = max(height, h)
			if node.left is not None:
				queue.append((node.left, h + 1))
			if node.right is not None:
				queue.append((node.right, h + 1))
		return height


class Node:

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

class Solution:

	def maxDepth(self, root):
		queue = []
		level = 0
		queue.append(root)
		while queue:
			curl = len(queue)
			for i in range(curl):
				currnode = queue.pop(0)
				if currnode.left != None:
					queue.append(currnode.left)
				if currnode.right != None:
					queue.append(currnode.right)
			level += 1
		return level


class Node:

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

class Solution:

	def maxDepth(self, root):
		level = {}
		level[root] = 1
		maxi = 0
		stack = [root]
		while stack:
			top = stack.pop()
			if top.left:
				stack.append(top.left)
				level[top.left] = level[top] + 1
				maxi = max(maxi, level[top.left])
			if top.right:
				stack.append(top.right)
				level[top.right] = level[top] + 1
				maxi = max(maxi, level[top.right])
		return maxi


from collections import deque

class Node:

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

class Solution:

	def maxDepth(self, root):
		if root is None:
			return 0
		level = 0
		q = deque([root])
		while q:
			for i in range(len(q)):
				temp = q.popleft()
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			level += 1
		return level


class Node:

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

class Solution:

	def maxDepth(self, root):
		import sys
		sys.setrecursionlimit(10000000)
		if not root:
			return 0
		l = self.maxDepth(root.left)
		r = self.maxDepth(root.right)
		return 1 + max(l, r)


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
from collections import deque

class Solution:

	def maxDepth(self, root):
		if not root:
			return 0
		nodes = [[root, 1]]
		res = 1
		while nodes:
			(node, depth) = nodes.pop()
			if node:
				res = max(res, depth)
				if node.left:
					nodes.append([node.left, depth + 1])
				if node.right:
					nodes.append([node.right, depth + 1])
		return res


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
from collections import deque

class Solution:

	def maxDepth(self, root):
		nodes = deque([root])
		res = 0
		while nodes:
			for element in range(len(nodes)):
				node = nodes.popleft()
				if node.left:
					nodes.append(node.left)
				if node.right:
					nodes.append(node.right)
			res += 1
		return res


class Node:

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

class Solution:

	def maxDepth(self, root):
		q = []
		level = 1
		q.append(root)
		q.append('$')
		leaf = {}
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					level += 1
					q.append('$')
			else:
				if t.left is None and t.right is None:
					leaf[t] = level
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
		return max(leaf.values())


class Node:

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

class Solution:

	def maxDepth(self, root):
		if not root:
			return
		queue = deque()
		queue.append(root)
		level = 0
		while queue:
			level_size = len(queue)
			for i in range(level_size):
				temp = queue.popleft()
				if temp.left is not None:
					queue.append(temp.left)
				if temp.right is not None:
					queue.append(temp.right)
			level += 1
		return level


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
from collections import deque

class Solution:

	def maxDepth(self, root):
		queue = deque()
		queue.append((root, 1))
		maxi = 1
		while queue:
			(node, depth) = queue.popleft()
			maxi = max(maxi, depth)
			if node.left:
				queue.append((node.left, depth + 1))
			if node.right:
				queue.append((node.right, depth + 1))
		return maxi


class Node:

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

class Solution:

	def maxDepth(self, root):
		max_ = 0
		q = deque()
		q.append(root)
		while q:
			max_ += 1
			for _ in range(len(q)):
				p = q.popleft()
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
		return max_


class Node:

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

def isLeaf(node):
	return node.left == 'N' and node.right == 'N'

class Solution:

	def maxDepth(self, root):
		if not root:
			return 0
		level = 0
		q = deque([root])
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
		return level


class Node:

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

class Solution:

	def maxDepth(self, root):
		q = deque()
		q.append(root)
		res = 0
		if root is None:
			return 0
		while q:
			for _ in range(len(q)):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			res += 1
		return res


import sys
sys.setrecursionlimit(10 ** 6)

class Node:

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

class Solution:

	def maxDepth(self, root):
		if root is None:
			return 0
		else:
			lh = self.maxDepth(root.left)
			rh = self.maxDepth(root.right)
			if lh > rh:
				return 1 + lh
			else:
				return 1 + rh


import sys
sys.setrecursionlimit(10 ** 6)

class Node:

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

class Solution:

	def maxDepth(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		left_d = self.maxDepth(root.left)
		right_d = self.maxDepth(root.right)
		if left_d > right_d:
			return left_d + 1
		else:
			return right_d + 1


class Node:

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

class Solution:

	def maxDepth(self, root):
		if root is None:
			return 0
		d = 0
		m = 0
		current = root
		stack = []
		while True:
			if current:
				d += 1
				stack.append((d, current))
				current = current.left
			elif stack:
				m = max(d, m)
				node = stack.pop()
				current = node[1]
				d = node[0]
				current = current.right
			else:
				break
		return m


class Node:

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

class Solution:

	def maxDepth(self, root):
		if root == None:
			return 0
		curr = root
		level = 0
		q = []
		q.append(root)
		while q:
			n = len(q)
			while n > 0:
				temp = q.pop(0)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
				n -= 1
			level += 1
		return level


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
from sys import setrecursionlimit
setrecursionlimit(100000000)

def ht(root):
	if not root:
		return 0
	return 1 + max(ht(root.left), ht(root.right))

class Solution:

	def maxDepth(self, root):
		return ht(root)


class Node:

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

class Solution:

	def maxDepth(self, root):

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