DEV Community

Cover image for Solving "Diameter of Binary Tree" Leet code Question
Bollam Shiva Shankara
Bollam Shiva Shankara

Posted on

Solving "Diameter of Binary Tree" Leet code Question

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

Happy coding,
shiva

Top comments (0)