# Finding the diameter of a binary tree

To find the diameter of a binary tree, we do the below

• Find the height of the left subtree and right subtree of every node recursively.
• If we add the two heights ( height of left subtree + height of right subtree ) of a node, we get the diameter passing through that node.
( As the diameter of a tree need not always pass through the root of a tree )
• From every node, we also return the maximum of ( left subtree height, right subtree height ) so that the parent node has the maximum length of diameter passing through it.

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
``````

Copyright (c) 2019-2023, Algotree.org.