Find the diameter of a binary tree
Given a binary tree, write an efficient algorithm to compute the diameter of it. A binary tree diameter equals the total number of nodes on the longest path between any two leaves in it.
The following figure shows two binary trees with diameters 6 and 5, respectively (nodes highlighted in blue). The binary tree diameter shown on the left side passes through the root node, while the diameter of the binary tree shown on the right side does not pass through the root node.
A simple solution would be to calculate the left and right subtree’s height for each node in the tree. The maximum node path that passes through a node will have a value one more than the sum of the height of its left and right subtree. Finally, the diameter is maximum among all maximum node paths for every node in the tree. The time complexity of this solution is O(n2) as there are n
nodes in the tree, and for every node, we are calculating the height of its left and right subtree that takes O(n) time.
We can solve this problem in linear time by doing a postorder traversal on the tree. Instead of calculating the height of the left and the right subtree for every node in the tree, get the height in constant time. The idea is to start from the bottom of the tree and return the height of the subtree rooted at a given node to its parent. The height of a subtree rooted at any node is one more than the maximum height of the left or right subtree.
The algorithm can be implemented as follows in C++, Java, and Python. Here, we pass diameter by reference to the function (instead of returning it) and update its value within the function itself using the left and right subtree height.
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Function to find the diameter of the binary tree. Note that the function // returns the height of the subtree rooted at a given node, and the diameter // is updated within the function as it is passed by reference int getDiameter(Node* root, int &diameter) { // base case: tree is empty if (root == nullptr) { return 0; } // get heights of left and right subtrees int left_height = getDiameter(root->left, diameter); int right_height = getDiameter(root->right, diameter); // calculate diameter "through" the current node int max_diameter = left_height + right_height + 1; // update maximum diameter (note that diameter "excluding" the current // node in the subtree rooted at the current node is already updated // since we are doing postorder traversal) diameter = max(diameter, max_diameter); // it is important to return the height of the subtree rooted at the current node return max(left_height, right_height) + 1; } int getDiameter(Node* root) { int diameter = 0; getDiameter(root, diameter); return diameter; } int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->right = new Node(4); root->right->left = new Node(5); root->right->right = new Node(6); root->right->left->left = new Node(7); root->right->left->right = new Node(8); cout << "The diameter of the tree is " << getDiameter(root); return 0; } |
Output:
The diameter of the tree is 6
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
import java.util.concurrent.atomic.AtomicInteger; // A class to store a binary tree node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Function to find the diameter of the binary tree. Note that the // function returns the height of the subtree rooted at a given node, // and the diameter is updated within the function as it is passed by // reference using the `AtomicInteger` class. public static int getDiameter(Node root, AtomicInteger diameter) { // base case: tree is empty if (root == null) { return 0; } // get heights of left and right subtrees int left_height = getDiameter(root.left, diameter); int right_height = getDiameter(root.right, diameter); // calculate diameter "through" the current node int max_diameter = left_height + right_height + 1; // update maximum diameter (note that diameter "excluding" the current // node in the subtree rooted at the current node is already updated // since we are doing postorder traversal) diameter.set(Math.max(diameter.get(), max_diameter)); // it is important to return the height of the subtree rooted at the // current node return Math.max(left_height, right_height) + 1; } public static int getDiameter(Node root) { AtomicInteger diameter = new AtomicInteger(0); getDiameter(root, diameter); return diameter.get(); } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.right = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.left = new Node(7); root.right.left.right = new Node(8); System.out.print("The diameter of the tree is " + getDiameter(root)); } } |
Output:
The diameter of the tree is 6
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
# A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Function to find the diameter of the binary tree. Note that the function # returns the height of the subtree rooted at a given node and the diameter. def getDiameter(root, diameter): # base case: tree is empty if root is None: return 0, diameter # get heights of left and right subtrees left_height, diameter = getDiameter(root.left, diameter) right_height, diameter = getDiameter(root.right, diameter) # calculate diameter "through" the current node max_diameter = left_height + right_height + 1 # update maximum diameter (note that diameter "excluding" the current # node in the subtree rooted at the current node is already updated # since we are doing postorder traversal) diameter = max(diameter, max_diameter) # it is important to return the height of the subtree rooted at the current node return max(left_height, right_height) + 1, diameter def getBTDiameter(root): diameter = 0 return getDiameter(root, diameter)[1] if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.right = Node(4) root.right.left = Node(5) root.right.right = Node(6) root.right.left.left = Node(7) root.right.left.right = Node(8) print('The diameter of the tree is', getBTDiameter(root)) |
Output:
The diameter of the tree is 6
The time complexity of the above solution is O(n), where n
is the total number of nodes in the binary tree. The program requires O(h) extra space for the call stack, where h
is the height of the tree.
Calculate the height of a binary tree with leaf nodes forming a circular doubly linked list
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)