Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0104 - Maximum Depth of Binary Tree
    0104 - Maximum Depth of Binary Tree
    0104 - Maximum Depth of Binary Tree
    0104 - Maximum Depth of Binary Tree

    0104 - Maximum Depth of Binary Tree

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/maximum-depth-of-binary-tree/

    Solution 1 - Recursive DFS

    Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Use a simple recursive approach: if the node is None, return 0. Otherwise, return 1 plus the maximum of the left and right subtree depths.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(h)SpaceComplexity: O(h)SpaceComplexity:O(h)

    Solution 2 - Iterative BFS (Level Order Traversal)

    Use a queue to perform a breadth-first traversal of the tree. Process each level entirely before moving to the next, incrementing a depth counter at each level. When the queue is empty, the counter holds the maximum depth.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0104.1 - Maximum Depth of Binary Tree - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        """Maximum Depth of Binary Tree Function"""
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Tree: [3, 9, 20, null, null, 15, 7] -> depth 3
    root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(Solution().maxDepth(root1))  # 3

    # Tree: [1, null, 2] -> depth 2
    root2 = TreeNode(1, None, TreeNode(2))
    print(Solution().maxDepth(root2))  # 2

    # Tree: [] -> depth 0
    print(Solution().maxDepth(None))  # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0104.2 - Maximum Depth of Binary Tree - Solution 2 - Iterative BFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        """Maximum Depth of Binary Tree Function"""
        if not root:
            return 0

        queue = deque([root])
        depth = 0

        while queue:
            depth += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return depth


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Tree: [3, 9, 20, null, null, 15, 7] -> depth 3
    root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(Solution().maxDepth(root1))  # 3

    # Tree: [1, null, 2] -> depth 2
    root2 = TreeNode(1, None, TreeNode(2))
    print(Solution().maxDepth(root2))  # 2

    # Tree: [] -> depth 0
    print(Solution().maxDepth(None))  # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()