Here is solutions for Maximum Depth of Binary Tree.

1. Understand the problem

• You are given the root of a binary tree.

• You must return the maximum depth — the number of nodes along the longest path from the root down to the deepest leaf node.

• Formally:

depth = 1 + max(depth(left subtree), depth(right subtree))

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. What is the size limit of the tree?

• This affects recursion stack and performance, up to 10^4 or 10^5 nodes.

1. Are node values important?

• No. Values do not matter — only tree structure.

1. Is the tree guaranteed to be valid?

• Yes, it is always a valid binary tree.

1. What should we return for an empty tree?

• Return 0.

1. Are there memory constraints that forbid recursion?

• Usually recursion is fine, but stack overflow could happen for extremely skewed trees.

• Iterative solution is acceptable too.

3. Explore examples.

1. Example 1

Input:
    1
   / \
  2   3
     /
    4

- Output: 3
- Longest path: 1 → 3 → 4 → depth = 3.

1. Example 2

Input:
   1
  /
 2
/
3

- Output: 3
- A skewed linked-list tree.

1. Example 3

- Input: root = None
- Output: 0

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Naive solution - Recursive DFS (Top-down or Bottom-up) - Time O(N), Space O(H)

depth(root) = 1 + max(depth(left), depth(right))

• Time: O(N).

• Space: O(H), worst case skewed tree O(N).

4.2. Iterative DFS using stack - Time O(N), Space O(N)

• Useful when avoid recursion. Push (node, depth) to a stack, traverse like DFS, track max depth manually.

• Recursion has call stack overhead:

  • return address

  • saved registers

  • function arguments

  • local variables

  • frame pointer

• A manual stack contains only what you choose to push.

4.3. BFS (Level-order traversal) - Time O(N), Space O(N/2)

• 💡 Key Idea:

  • Use a queue and count the number of levels.

• Time: O(n)

• Space: O(w) where w = max tree width

5. Implement solutions.

5.1. Naive solution - Recursive DFS (Top-down or Bottom-up) - Time O(N), Space O(H)

# 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

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

• Time: O(N).

• Space: O(H)

  • Best case: balanced tree - O(logN).
  • Worst case: skewed tree - O(N).

5.2. Iterative DFS using stack - Time O(N), Space O(N)

# 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:
        stack = [[root, 1]]
        res = 0

        while stack:
            node, depth = stack.pop()

            if node:
                res = max(res, depth)
                stack.append([node.left, depth + 1])
                stack.append([node.right, depth + 1])
        return res

• Time: O(N).

• Space: O(N).

5.3. BFS (Level-order traversal) - Time O(N), Space O(N/2) - Always Space O(N / 2)

# 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:
        q = deque()
        if root:
            q.append(root)

        level = 0
        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)
            level += 1
        return level

• Time: O(N).

• Space: O(N).

6. Dry run testcases.

✔ Testcase 1

    1
   / \
  2   3
     /
    4

Recursive DFS:

• depth(4) = 1

• depth(3) = 1 + max(1, 0) = 2

• depth(1) = 1 + max(1 (node 2), 2) = 3 → Output: 3