712233. Maximum Depth Of Binary Tree
Easy
Maximum Depth Of Binary Tree
Slug: maximum-depth-of-binary-tree
Difficulty: Easy
Topic Tags: Tree, Data Structures
Company Tags: Amazon, Microsoft, Facebook
Summary
This problem is about finding the maximum depth of a binary tree. Given the root node of a binary tree, we need to find the maximum number of nodes along the longest path from the root node down to any leaf node.
Detailed Explanation
To solve this problem, we can use recursion to traverse the binary tree and calculate the depth at each node. The depth of a node is defined as the number of edges between it and the nearest leaf node.
Here's a step-by-step breakdown of the solution:
- Create a recursive function
maxDepththat takes the root node of the binary tree as input. - If the current node is null, return 0 (since there are no nodes in this case).
- Recursively call
maxDepthon the left and right child nodes and store their depths inleftDepthandrightDepth, respectively. - The maximum depth of the current node is the maximum of the depths of its left and right child nodes, plus 1 (since we're considering the current node as well).
- Return the maximum depth found.
Here's an ASCII art diagram to illustrate the process:
1
/ \
2 3
/ \ / \
4 5 6 7
In this example, the maximum depth of the tree is 4 (from node 1 to leaf nodes 4 and 5).
Time complexity: O(n), where n is the number of nodes in the binary tree. Space complexity: O(h), where h is the height of the binary tree.
Optimized Solutions
Java
class Node {
int val;
Node left, right;
Node(int val) {
this.val = val;
left = null;
right = null;
}
}
public class Main {
public static int maxDepth(Node root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}