Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 3
Example 2:
Input: root = [1,null,2] Output: 2
Constraints:
[0, 104].-100 <= Node.val <= 100This 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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n) where n is the number of nodes, as each node is visited once. |
| Breadth-First Search (BFS) using Queue | Time Complexity: O(n) due to each node being visited once. |
Maximum Depth of Binary Tree - 3 Solutions - Leetcode 104 - Python • NeetCode • 296,166 views views
Watch 9 more video solutions →Practice Maximum Depth of Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor