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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7def maxDepth(root: TreeNode) -> int:
8 if not root:
9 return 0
10 return max(maxDepth(root.left), maxDepth(root.right)) + 1This Python solution verifies if the tree root exists. If not, it returns 0. Otherwise, it recursively calculates the maximum depth of both subtrees, adding 1 to account for 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.
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 let q = [root];
10 let depth = 0;
11 while (q.length > 0) {
12 let levelSize = q.length;
13 for (let i = 0; i < levelSize; i++) {
14 let node = q.shift();
15 if (node.left) q.push(node.left);
16 if (node.right) q.push(node.right);
17 }
18 depth++;
19 }
20 return depth;
21};JavaScript implements Array-based queue-like structures for breadth-first traversal. The process entails checking node existence, pushing children into arrays, and incrementing depth post-level due completion.