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.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var maxDepth = function(root) {
8 if (!root) return 0;
9 return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
10};In JavaScript, similar strategies apply, using recursive function calls to determine the maximum depth by comparing subtree depths. If the node is null, return 0.
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.