700616. Maximum Node Level
Maximum Node Level
Slug: maximum-node-level
Difficulty: Easy
Id: 700616
Topic Tags: Tree, Data Structures
Company Tags: VMWare, Amazon
Summary
Given a binary tree, find the maximum node level in the tree. A node's level is defined as its distance from the root node. This problem involves traversing a tree and keeping track of the maximum level encountered so far.
Detailed Explanation
To solve this problem, we can use a simple recursive function that calculates the maximum level for each node. We start by defining a helper function maxLevel that takes the root node as an argument. This function returns the maximum level found in the subtree rooted at the given node.
Here's the step-by-step breakdown of the solution:
- Initialize the maximum level to 0.
- If the current node is null, return the maximum level (which remains 0).
- Calculate the current level by adding 1 to the depth of the current node from the root.
- Update the maximum level if the current level is greater than the previously found maximum level.
- Recursively call
maxLevelfor each child node and update the maximum level accordingly.
The time complexity of this solution is O(n), where n is the number of nodes in the tree, since we visit each node once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.
Optimized Solutions
Java
class Node {
int val;
Node left, right;
public Node(int val) {
this.val = val;
left = right = null;
}
}
public class Main {
public static int maxLevel(Node root) {
if (root == null) return 0;
int maxLevel = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
maxLevel++;
for (int i = 0; i < levelSize; i++) {
Node node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
return maxLevel;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
System.out.println(maxLevel(root)); // Output: 3
}
}