Intuition
We want to find the diameter of a binary tree, which is the length of the longest path between any two nodes. This path may or may not pass through the root.
Approach
We perform a depth-first traversal of the tree and calculate the height of each subtree. While calculating the height of each node, we also update the diameter if a longer path is found. The final result will be stored in the diameter variable.
Time complexity
O(n) - We visit each node once.
Space complexity
O(h) - Recursive call stack space, where h is the height of the tree.
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return diameter;
}
public int height(TreeNode node){
if(node == null) {
return 0;
}
int lh = height(node.left);
int rh = height(node.right);
diameter = Math.max(diameter,lh+rh);
return 1 + Math.max(lh,rh);
}
}
Happy coding,
shiva
Top comments (0)