104.Maximum_Depth_of_Binary_Tree_(Easy).md

104. Maximum Depth of Binary Tree (Easy)

Date and Time: May 28, 2024 (EST)

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

Question:

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.

Example 1:

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

Output: 3

Example 2:

Input: root = [1, null, 2]

Output: 2

KeyPoints:

For recursion version solution, we use left, right to store the depth of root's left-subtree and root's right-subtree. Then we just repeatly call the function with root.left and root.right and in the end we just return 1 + max(left, right)

For the alternative solution (DFS), we use stack to store [root, 1] first, then while stack is not empty, we pop() the element from the stack with its depth, we then check if the node we pop from stack is not None, we can append [node.left, depth+1], [node.right, depth+1] to stack, and we repeat this process for DFS.

Recursion Solution:

# 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:
        # Base case
        if root is None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return 1 + max(left, right)

DFS Solution:

# 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:
        # Pre-order DFS
        stack = [[root, 1]]   # Start with the root node, depth 1
        result = 0
        while stack:
            root, depth = stack.pop()
            # Check if root node is not null
            if root:
                result = max(result, depth)
                stack.append([root.left, depth + 1])    # Add left node to stack
                stack.append([root.right, depth + 1])   # Add right node to stack
        return result

Time Complexity: $O(n)$, n is the total nodes.
Space Complexity: $O(n)$