This approach involves using a recursive function that traverses the tree in a depth-first manner. For each node, calculate the maximum depth of its left and right subtrees, and add 1 for the current node itself. The function returns the maximum of these two values. This provides an elegant and intuitive solution, leveraging the inherent recursive structure of trees.
Time Complexity: O(n) where n is the number of nodes, as each node is visited once.
Space Complexity: O(h) where h is the height of the tree, due to the stack space in recursion.
1#include <stdio.h>
2typedef struct TreeNode {
3 int val;
4 struct TreeNode *left;
5 struct TreeNode *right;
6} TreeNode;
7
8int maxDepth(struct TreeNode* root) {
9 if (root == NULL) return 0;
10 int leftDepth = maxDepth(root->left);
11 int rightDepth = maxDepth(root->right);
12 return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
13}The function maxDepth checks if the current node is null. If so, it returns 0, indicating no depth. Otherwise, it recursively computes the depth of the left and right subtrees, takes their maximum, and adds 1 to include the current node.
This approach involves using a queue to perform a Breadth-First Search (BFS) on the tree. By iterating level by level, we increment the depth counter with each level traversed completely.
Time Complexity: O(n) due to each node being visited once.
Space Complexity: O(n) where n is the maximum number of nodes at any level.
1#include <stdio.h>
2#include <stdlib.h>
3#define MAX_Q_SIZE 500
4
5typedef struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9} TreeNode;
10
11TreeNode** createQueue(int* front, int* rear) {
12 TreeNode** queue = (TreeNode**)malloc(sizeof(TreeNode*) * MAX_Q_SIZE);
13 *front = *rear = 0;
14 return queue;
15}
16
17void enqueue(TreeNode** queue, int* rear, TreeNode* new_node) {
18 queue[*rear] = new_node;
19 (*rear)++;
20}
21
22TreeNode* dequeue(TreeNode** queue, int* front) {
23 (*front)++;
24 return queue[*front - 1];
25}
26
27int maxDepth(TreeNode* root) {
28 if (!root) return 0;
29 int depth = 0;
30 int front, rear;
31 TreeNode** queue = createQueue(&front, &rear);
32 enqueue(queue, &rear, root);
33 while (front < rear) {
34 int count = rear - front;
35 for (int i = 0; i < count; i++) {
36 TreeNode* node = dequeue(queue, &front);
37 if (node->left) enqueue(queue, &rear, node->left);
38 if (node->right) enqueue(queue, &rear, node->right);
39 }
40 depth++;
41 }
42 free(queue);
43 return depth;
44}The implementation expands upon queue operations for nodes. A queue holds nodes level-wise. Traverse nodes, extract them, and access their children for the new level until the queue is empty. Increment the depth after processing each level.