To find the diameter of a binary tree, we do the below
Algorithm
Initialize diameter = 0
Get_Height ( Node node )
1. If node is null, then
return 0
2. Else
height_left_subtree = GetHeight ( node.left )
height_right_subtree = GetHeight ( node.right )
3. diameter = maximum ( diameter, ( height_left_subtree + height_right_subtree ) )
4. # Return the maximum height of the ( left subtree, right subtree )
return 1 + max ( height_left_subtree, height_right_subtree )
Find_Diameter ( Node root )
1. Get_Height ( root )
2. return diameter
class Node :
def __init__ (self, data=0, left=None, right=None) :
self.data = data
self.left = left
self.right = right
class BinTree :
def __init__ (self) :
self.diameter = 0
def GetHeight (self, root : Node) -> int :
if (root == None) :
return 0
height_left_subtree = self.GetHeight(root.left)
height_right_subtree = self.GetHeight(root.right)
# Find the diameter of every node by adding the height of
# the left-subtree and the right-subtree below it.
# Store the maximum diameter by comparing the diameter found at every node.
self.diameter = max (self.diameter, (height_left_subtree + height_right_subtree))
# Return the maximum height of the ( left subtree, right subtree )
return 1 + max (height_left_subtree, height_right_subtree)
def FindDiameter (self, root : Node) -> int :
self.GetHeight(root)
return self.diameter
def main () :
# Constructed binary tree is
# 9
# / \
# 5 16
# / \ / \
# 3 7 12 18
# / \ \
# 6 8 25
# / \
# 20 36
#
node3 = Node(3)
node6 = Node(6)
node8 = Node(8)
node12 = Node(12)
node20 = Node(20)
node36 = Node(36)
node7 = Node(7, node6, node8)
node25 = Node(25, node20, node36)
node18 = Node(18, None, node25)
node16 = Node(16, node12, node18)
node5 = Node(5, node3, node7)
root_node9 = Node(9, node5, node16)
# Subtree
# 18
# \
# 25
# / \
# 20 36
_node20 = Node(20)
_node36 = Node(36)
_node25 = Node(25, _node20, _node36)
root_node18 = Node(18, None, node25)
# Subtree
# 7
# / \
# 6 8
# \
# 9
_node9 = Node(9)
_node6 = Node(6)
_node8 = Node(8, None, _node9)
root_node7 = Node(7, _node6, _node8)
# Subtree
# 16
# \
# 18
_node18 = Node(18)
root_node16 = Node(16, None, _node18)
# Subtree
# 3
root_node3 = Node(3)
tree_roots = [ root_node9, root_node18, root_node7, root_node16, root_node3 ]
b = BinTree()
for node in (tree_roots) :
b.diameter = 0
b.FindDiameter(node)
print("Diameter of tree with root " + str(node.data) + " is : " + str(b.diameter))
if __name__ == "__main__" :
main()
Output
Diameter of tree with root 9 is : 7
Diameter of tree with root 18 is : 2
Diameter of tree with root 7 is : 3
Diameter of tree with root 16 is : 1
Diameter of tree with root 3 is : 0
#include<iostream>
#include<vector>
using namespace std;
class Node {
public:
int data;
Node * left;
Node * right;
Node (int x, Node * left_node = nullptr, Node * right_node = nullptr) :
data(x), left(left_node), right(right_node) {
}
};
class BinTree {
public:
int diameter = 0;
int GetHeight (Node * root) {
if (root == nullptr) {
return 0;
}
int height_left_subtree = GetHeight(root->left);;
int height_right_subtree = GetHeight(root->right);
// Find the diameter of every node by adding the height of
// the left-subtree and the right-subtree below it.
// Store the maximum diameter by comparing the diameter found at every node.
diameter = max(diameter, (height_left_subtree + height_right_subtree));
// Return the maximum height of the (left subtree, right subtree) + 1
return 1 + max (height_left_subtree, height_right_subtree);
}
int FindDiameter (Node* root) {
GetHeight(root);
return diameter;
}
};
int main() {
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
/ \ \
6 8 25
/ \
20 36
*/
Node node3(3), node6(6), node8(8), node12(12), node20(20), node36(36);
Node node7(7, &node6, &node8);
Node node25(25, &node20, &node36);
Node node18(18, nullptr, &node25);
Node node16(16, &node12, &node18);
Node node5(5, &node3, &node7);
Node root_node9(9, &node5, &node16);
/* Subtree
18
\
25
/ \
20 36 */
Node _node20(20), _node36(36);
Node _node25(25, &_node20, &_node36);
Node root_node18(18, nullptr, &node25);
/* Subtree
7
/ \
6 8
\
9 */
Node _node9(9), _node6(6);
Node _node8(8, nullptr, &_node9);
Node root_node7(7, &_node6, &_node8);
/* Subtree
16
\
18 */
Node _node18(18);
Node root_node16(16, nullptr, &_node18);
/* Subtree
3 */
Node root_node3(3);
vector<Node> tree_roots = { root_node9, root_node18, root_node7, root_node16, root_node3 };
BinTree b;
for (Node node : tree_roots) {
b.diameter = 0;
b.FindDiameter(&node);
cout << "Diameter of tree with root " << node.data << " is : " << b.diameter << endl;
}
return 0;
}
Output
Diameter of tree with root 9 is : 7
Diameter of tree with root 18 is : 2
Diameter of tree with root 7 is : 3
Diameter of tree with root 16 is : 1
Diameter of tree with root 3 is : 0
© 2019-2026 Algotree.org | All rights reserved.
This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org
"First, solve the problem. Then, write the code. - John Johnson"