Given a binary tree, write an efficient algorithm to compute the diameter of it. The diameter of a binary tree is equal to number of nodes on the longest path between any two leaves in it.
For example, below figure shows two binary trees having diameter 6 and 5 respectively (nodes highlighted in blue color). The diameter of binary tree shown on left side passes through root node while the diameter of binary tree shown on right side do not passes through the root node.
Simple solution would be to calculate height of left subtree and right subtree for each node in the tree. The maximum node path that passes through a node will have value equal to sum of height of its left and right subtree plus 1. 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 height of its left subtree and right subtree that takes O(N) time.
We can solve this problem in linear time by doing post-order traversal of the tree. Instead of calculating height of left subtree and right subtree for every node in the tree, we can get the height in constant time. The idea is to start from the bottom of the tree and return height of subtree rooted at given node to its parent node. The height of subtree rooted at any node is equal to 1 plus maximum height of the left subtree or right subtree. We pass diameter by reference to the function (instead of returning it) and update its value within the function itself using left and right subtree height.
C++ implementation –
|
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 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to find diameter of the binary tree. Note that the function // returns the height of the subtree rooted at given node and 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 subtree rooted at current node is already updated as we're // doing post-order traversal) diameter = max(diameter, max_diameter); // important - return height of subtree rooted at current node return max(left_height, right_height) + 1; } // Function to find diameter of the binary tree int getDiameter(Node* root) { int diameter = 0; getDiameter(root, diameter); return diameter; } |
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply