Maximum Depth of Binary Tree

To solve this efficiently, I will use a Depth-First Search approach via recursion, which aligns perfectly with the hierarchical nature of binary trees. First, I need to establish my base case. If the current node is null, it contributes zero to the depth, so I return 0 immediately. This handles the edge case of an empty tree or reaching the end of a branch. Next, for any non-null node, the maximum depth is calculated as one, representing the current node itself, plus the greater of the two depths returned by its left and right children. I don't need to track global variables; instead, I let the recursive calls bubble up the maximum value. For instance, if I have a root with a left child having a depth of 2 and a right child with a depth of 3, the root's depth becomes 1 + max(2, 3), which equals 4. This approach ensures we visit every node exactly once, resulting in a time complexity of O(N), where N is the number of nodes. The space complexity is O(H), where H is the height of the tree, due to the recursion stack. In the worst-case scenario of a skewed tree, this becomes O(N), but for balanced trees typical in production systems, it remains logarithmic. This method is clean, easy to debug, and demonstrates a solid understanding of recursive problem decomposition, which is highly valued at Google.