## 104. Maximum Depth of Binary Tree

Interviewer: Good afternoon! How are you today?

Interviewee: I'm doing well, thank you! How about you?

Interviewer: Great, thanks for asking. Let's jump right into the technical question, shall we? Do you have any experience with binary trees?

Interviewee: Yes, I've worked with binary trees in some of my past projects.

Interviewer: Great! Then, you should find this question quite interesting. Imagine you're working on a software project that needs to analyze a tree-based data structure. Your task is to write a function in C that calculates the maximum depth of a binary tree. The depth of a tree is the length of the longest path from the root to a leaf. For example, a tree with a single node has a depth of 1.

Here's the struct definition for a binary tree node(I will show it in the doc):

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

Can you write a C function to find the maximum depth of such a binary tree?

Interviewee: Sure! I can write a recursive function that traverses the tree and computes the maximum depth. Would you like me to explain my approach before coding it?

Interviewer: That sounds like a good plan. Please go ahead.

Interviewee: The idea is to recursively explore the left and right subtrees of a given node, calculating their depths. The depth of the current node would then be the maximum of the depths of its left and right subtrees plus 1. If we reach a null node, we return 0 as its depth.

Interviewer: Excellent! Please proceed to write the code.

Interviewee: Here's the C code for finding the maximum depth of a binary tree.

#define max(a, b) ((a) > (b) ? (a) : (b))

int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    
    return max(leftDepth, rightDepth) + 1;
}

Interviewer: The code looks great, and your explanation is clear. Do you see any potential issues with this approach?

Interviewee: Since this is a recursive approach, it could result in a stack overflow for extremely large trees. However, for most practical cases, this should work just fine.

Interviewer: Excellent! You've addressed the problem well. Thank you for your time today.

Interviewee: Thank you! It was a pleasure discussing this problem with you.