Maximum Depth of Binary Tree - Leetcode 104 - Python 3 Easy Ways [Recursion, BFS, DFS]

Maximum Depth of Binary Tree  

Given the root of a binary tree, return 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.

Recusive DFS

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))

BFS

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        lvl = 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)
            lvl += 1
        return lvl

Iterative DFS

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        s = [[root,1]] #stack
        ans = 0
        
        while s:
            n, d = s.pop()
            
            if n:
                ans = max(ans, d)
                s.append([n.left, d+1])
                s.append([n.right, d+1])
                
        return ans

Explaination :