Diameter of Binary Tree

Problem: Given the root of binary tree find its diameter.
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.

Example 1:

Input: root = [5,2,null,3,4,null,null,6,7]
Output: 3

Example 2:

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

Approach:

As in the one of our previous tutorials we calculate height of tree. Here to find diameter of tree, we will calculate the height of left subtree and right subtree recursively and add the obtained height from left or right subtree and store it.

Code Implementation:

• Java

public class DiameterOfBinaryTree {

    public static class Node {

        int val;

        Node left, right;

        // Constructor

        Node(int val) {

            this.val = val;

            left = right = null;

        }

    }

    public static void main(String[] args) {

        /*

         * Creating Binary Tree The created binary tree is same as in the above given

         * figure (refer figure for reference)

         */

        Node root = new Node(5);

        root.left = new Node(2);

        root.left.left = new Node(3);

        root.left.right = new Node(4);

        root.left.right.left = new Node(6);

        root.left.right.right = new Node(7);

        // in this array at index 0 diameter of given binary tree will be stored

        int[] diameter = new int[1];

        // calling findDiameter method

        findDiameter(root, diameter);

        System.out.println("Diameter of Binary Tree: " + diameter[0]);

    }

    private static int findDiameter(Node root, int[] diameter) {

        if (root == null)

            return 0;

        // storing height of leftsubtree in left

        int left = findDiameter(root.left, diameter);

        // storing height of rightsubtree in right

        int right = findDiameter(root.right, diameter);

        // calculating diameter and stroing it in diameter[] array

        diameter[0] = Math.max(diameter[0], left + right);

        // for calculating height

        return Math.max(left, right) + 1;

    }

}

Output:

Diameter of Binary Tree: 3

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in tree.

Space Complexity: Considering the stack space, if the tree is balanced then O(log n) and if tree is unbalanced then O(n).

---

If you want to contribute such articles to solutions2coding.com please click here. Thank you!