Diameter of Binary Tree in Java
In this tutorial, we are going to learn about diameter of binary tree in Java. The number of nodes on the longest path connecting two end nodes determines a tree's diameter and width. Note that there are multiple paths of length nine in each tree, but no path longer than nine nodes. The diagram below depicts two trees, each with a diameter of nine. The leaves that constitute the ends of the longest path are shaded.
Give the length of the tree's diameter and the binary tree's root.
Example:
Input: [6, 7, 8, 9, 10]
Output: 3
Explanation: 3 is the length of the path [9, 7, 6, 8] or [10, 7, 6, 8].
![Diameter of Binary Tree in Java/>
<!-- /wp:html -->
<!-- wp:heading -->
<h2 class=](https://static.tutorialandexample.com/java/diameter-of-binary-tree-in-java1.png)
ALGORITHM:
Step 1: Print the diameter.
Step 2: Determine the diameter and then put it back in the main.
Step 3: Determine the heights of left and right sub-trees.
Step 4: Determine the diameter of left and right sub-trees.
Step 5: Maximize the diameter of the left subtree.
Step 6: Maximize the diameter of the right subtree.
Step 7: Get the maximum height of the left subtree + the height of the right.
Step 8: Make a binary tree.
Step 9: Enter the nodes.
Filename: DiameterOfBinaryTree.java
class TreeNode { int value; TreeNode left, right; public TreeNode(int item) { value = item; left = right = null; } } // Diameter to be printed by class public class DiameterOfBinaryTree { TreeNode root; // The diameter can be calculated and returned to the main int findDiameter(TreeNode root) { if (root == null) return 0; // measure the depth of the left and right subtrees. int leftHeight = height(root.left); int rightHeight = height(root.right); // determine each sub-tree's diameter, left and right. int leftDiameter = findDiameter(root.left); int rightDiameter = findDiameter(root.right); return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter)); } // a covering for the diameter (Node root) int findDiameter() { return findDiameter(root); } // The role Find a tree's "height" by computation. The length of the path that connects the root node to the farthest leaf node, measured in nodes, is called the height. static int height(TreeNode node) { // the basic case tree is empty. if (node == null) return 0; // Height is equal to 1 + the maximum of the left and right heights if the tree is not empty. return (1 + Math.max(height(node.left), height(node.right))); } public static void main(String args[]) { // building a binary tree and adding nodes to it DiameterOfBinaryTree tree = new DiameterOfBinaryTree(); tree.root = new TreeNode(1); tree.root.left = new TreeNode(2); tree.root.right = new TreeNode(3); tree.root.left.left = new TreeNode(4); tree.root.left.right = new TreeNode(5); System.out.println("Given binary tree of the diameter of is : " + tree.findDiameter()); } }
Output:
Given binary tree of the diameter of is : 4
Complexity analysis:
Time complexity: The time complexity of the program is O(N2).
Space complexity: The space complexity of the program is O(N), for call stack.
Approach2: Using height – depth approach
ALGORITHM:
Step 1: Determine the height of each subtree rooted at the current node.
Step 2: Add one for the current node to the total height of the left and right subtrees.
Step 3: Calculate the diameter for each node by adding the heights of its left and right subtrees, which could result in computational inefficiencies.
Filename: DiameterOfBinaryTree.java
class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } // A class of utility to pass height objects class Height { int height; } // To print the diameter, select the class. public class DiameterOfBinaryTree { Node root; int diameterOpt(Node root, Height height) { Height leftHeight = new Height(), rightHeight = new Height(); if (root == null) { height.height = 0; return 0; // Moreover, diameter is 0. } /* leftDiameter --> Left subtree diameter --> Right subtree diameterDiameter --> Right subtree's diameter Find the left and right subtree heights. Both in the left and right heights. Additionally, keep the returned values in ldiameter and ldiameter */ int leftDiameter = diameterOpt(root.left, leftHeight); int rightDiameter = diameterOpt(root.right, rightHeight); // The maximum height of the left and right subtrees plus one equals the height of the current node. height.height = Math.max(leftHeight.height, rightHeight.height) + 1; return Math.max(leftHeight.height + rightHeight.height + 1, Math.max(leftDiameter, rightDiameter)); } // a covering for the diameter (Node root) int diameter() { Height height = new Height(); return diameterOpt(root, height); } // The role Find a tree's "height" by computation. The number of nodes along the longest path from the root node to the farthest leaf node is known as the height. static int height(Node node) { // base case tree has nothing in it. if (node == null) return 0; // Height is equal to 1 + the maximum of the left and right heights if the tree is not empty. return (1 + Math.max(height(node.left), height(node.right))); } public static void main(String args[]) { // building a binary tree and adding nodes to it DiameterOfBinaryTree tree = new DiameterOfBinaryTree(); tree.root = new Node(6); tree.root.left = new Node(7); tree.root.right = new Node(8); tree.root.left.left = new Node(9); tree.root.left.right = new Node(10); System.out.println("Given binary tree of the diameter of is : " + tree.diameter()); } }
Output:
Given binary tree of the diameter of is : 4
Complexity analysis:
Time complexity: The program has an O(N) time complexity.
Space complexity: The space complexity of the program is O(N), due to recursive calls.
Approach 3: Using morris traversal algorithm
ALGORITHM:
Step 1: Use a current node that has been initialized as the binary tree's root to traverse the tree.
Step 2: Take the following action when the current_node is not NULL.
Step 2.1: Proceed to the right child of the current node if the left child is NULL.
Step 2.2: If the current node's left child is not NULL, locate the node that is farthest to the right in its left subtree.
Step 2.3: Move to the left child of the current node and set the right child of the rightmost node to the current node if its right child is NULL.
Step 2.4: Go to the current node, set its right child back to NULL, and then go to the right child if the rightmost node's right child is not NULL.
Step 2.5: Use the maximum function to get the left and right subtree heights of each visited node, then update the diameter to be the maximum of the sum of those heights plus the current diameter.
Step 3: Return the diameter.
Filename: DiameterOfBinaryTree.java
class Node { int data; Node left, right; public Node(int data) { this.data = data; this.left = null; this.right = null; } } public class DiameterOfBinaryTree { // Make a new node public static Node newNode(int data) { Node node = new Node(data); return node; } // Finding the binary tree's diameter using the Morris traversal public static int calculateDiameter(Node root) { if(root==null) return 0; if(root.left==null && root.right==null) return 1; int diameter = 0; Node current = root; while (current != null) { if (current.left == null) { current = current.right; } else { Node predecessor = current.left; while (predecessor.right != null && predecessor.right != current) { predecessor = predecessor.right; } if (predecessor.right == null) { predecessor.right = current; current = current.left; } else { predecessor.right = null; int leftHeight = 0, rightHeight = 0; Node temp = current.left; while (temp != null) { leftHeight++; temp = temp.right; } temp = current.right; while (temp != null) { rightHeight++; temp = temp.left; } diameter = Math.max(diameter, leftHeight + rightHeight + 1); current = current.right; } } } return diameter; } public static void main(String[] args) { // Make the specified binary tree. Node root = newNode(6); root.left = newNode(7); root.right = newNode(8); root.left.left = newNode(9); root.left.right = newNode(10); // Use the Morris traversal to get the binary tree's diameter. int diameter = calculateDiameter(root); // Output the binary tree's diameter. System.out.println("Given binary tree of the diameter of is " + diameter); } }
Output:
Given binary tree of the diameter of is : 4
Complexity analysis:
Time complexity: The time complexity of the program is O(N), where N is the number of nodes in the binary tree
Space complexity: The space complexity of the program is O(h).