104. Maximum Depth of Binary Tree

Easy

Problem:

Find the maximum depth of a binary tree.

Input: root = [3,9,20,null,null,15,7]
Output: 3

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Solution:

DFS

  1. Base Case:

    • If root is None, the function returns 0. This is the base case for the recursion, which means if we've reached a null node (or leaf node's child), the depth is 0.

  2. Recursive Case:

    • For any given node, the depth of that node is 1 (counting the node itself) plus the maximum depth of its left and right subtrees.

    • So, for the current root, we calculate the depth of its left subtree using the recursive call self.maxDepth(root.left). This call will go down the left subtree and keep calculating the depth until it hits the base case (a leaf node or null node). The result of this call is stored in left_depth.

    • Similarly, we calculate the depth of the right subtree using the recursive call self.maxDepth(root.right). The result of this call is stored in right_depth.

  3. Combining Results:

    • Once we have the depths of the left and right subtrees, we take the maximum of the two (because we want the longest path) and add 1 (for the current node) to get the depth of the current root.

    • The expression 1 + max(left_depth, right_depth) gives us the depth of the tree rooted at the current root.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        
        return 1 + max(left_depth, right_depth)
Before optimization:
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        depth_arr = []

        if root is None:
            return 0

        def dfs(p, node):
            print(p.val, node)

            if p is None:
                return

            if p.right is None:
                depth_arr.append(node)

            if p.left is None:
                depth_arr.append(node)

            if p.right: 
                dfs(p.right, node + 1)

            if p.left: 
                dfs(p.left, node + 1)

        dfs(root, 1)
        return max(depth_arr)

BFS

To determine the depth of a binary tree, use Breadth-First Search (BFS) that adds nodes level by level.

The depth can be found by returning the number of times BFS is iterated. This is because the depth is equivalent to the number of iterations of the while loop in BFS, so the number of iterations directly represents the height of the tree.

Note: Using the deque data structure, which is composed of a doubly linked list, not only allows for the free use of both queue and stack operations, but also offers good performance as it can extract from both directions in O(1) time.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        
        q = collections.deque([root])
        depth = 0

        while q:
            depth += 1
            # Extract the node from the queue and insert its child nodes
            for _ in range(len(q)):
                cur_root = q.popleft()
                if cur_root.left:
                    q.append(cur_root.left)
                if cur_root.right:
                    q.append(cur_root.right)
        # Number of BFS iterations == depth
        return depth

Last updated