Diameter of Binary Tree

Problem

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them. (link)

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [1, 10<sup>4</sup>].

• -100 <= Node.val <= 100

Solution

Brute force Approach

Traverse each node and calculate the height of its left and right children. Then, determine the maximum diameter among all nodes and return that value.

Time - O(n) x O(n) for skewed tree

Space - O(n) for auxiallary stack

class Solution {
    private int depth(TreeNode root){
        if(root==null) return 0;

        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);

        return Math.max(leftDepth, rightDepth) +1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null) return 0;

        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);

        int diameter = leftDepth+rightDepth;

        int leftDiameter = diameterOfBinaryTree(root.left);
        int rightDiameter = diameterOfBinaryTree(root.right);

        return Math.max(Math.max(diameter, leftDiameter),rightDiameter);
    }
}

Optimal Approach

While calculating the depth of the binary tree, maintain a reference to the global diameter. Whenever you compute the left and right depths, compare the new diameter with the global one and update it if necessary.

Time - O(n)

Space - O(n) for Auxillary stack

class Solution {
    private int depth(TreeNode root, int[] diameter){
        if(root==null) return 0;

        int leftDepth = depth(root.left, diameter);
        int rightDepth = depth(root.right, diameter);

        diameter[0] = Math.max(diameter[0], leftDepth+rightDepth);

        return Math.max(leftDepth, rightDepth) +1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        int[] diameter = {0};

        depth(root, diameter);
        return diameter[0];
    }
}