Maximum Depth of Binary Tree

Problem Summary

• Given a tree, return the maximum depth of the tree

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Trees
• Depth First Search

Time & Space Complexity

• Time: $O(n)$ → Reason: Going through each node
• Space: $O(n)$ → Reason: Recursive call stack

Code

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        maxCount = 0

        def bfs(node, count):
            if not node:
                nonlocal maxCount
                maxCount = max(count, maxCount)
                return

            bfs(node.left, count + 1)
            bfs(node.right, count + 1)

        bfs(root, 0)
        return maxCount

Common Mistakes / Things I Got Stuck On

• Didn't return after setting max
• Forgot about nonlocal