# Python Solutions with Detailed Explanations

• Solution

Maximum Depth of Binary Tree https://leetcode.com/problems/maximum-depth-of-binary-tree/

Depth First Search: Post Order

• Empty tree i.e. root is None: Depth = 0
• maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1
• Time and Space Complexity: O(N)
``````class Solution_DFS_Post_Order(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
else:
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
``````

Depth First Search: PreOrder

• Perform pre-order traversal and pass a variable to track the level
• Time and Space Complexity: O(N)
``````from collections import deque
class Solution_BFS_Iterative(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
q, depth = deque(), 0
if root:
q.append(root)
while len(q):
depth += 1
for _ in range(len(q)):
x = q.popleft()
if x.left:
q.append(x.left)
if x.right:
q.append(x.right)
return depth
``````

Depth First Search: Iterative Version

• Push the root and the level on the stack.
• Pop and push left and right kids of root. Update the max_level variable.
• Time and Space Complexity: O(N)
``````class Solution_DFS_Pre_Order(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.max_level = 0
self.helper(root, 0)
return self.max_level

def helper(self, root, level):
self.max_level = max(self.max_level, level)
if root:
self.helper(root.left, level+1)
self.helper(root.right, level+1)
return
``````

• Traverse level by level and keep a counter to track level count
• Time and Space Complexity: O(N)
``````class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
st, max_level = [], 0
if root:
st.append((root, 1))
while st:
x, level = st.pop()
max_level = max(max_level, level)
if x.left:
st.append((x.left, level+1))
if x.right:
st.append((x.right, level+1))
return max_level
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.