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
Â Â Â Â Â Â Â Â  Initialize height_left_subtree = 0
Â Â Â Â Â Â Â Â  Initialize height_right_subtree = 0
Â Â Â Â Â Â Â Â  If node’s left node ( i.e node.left ) is not null, then
Â Â Â Â Â Â Â Â Â Â Â  height_left_subtree = GetHeight ( node.left ) + 1
Â Â Â Â Â Â Â Â  If node’s right node ( i.e node.right ) is not null, then
Â Â Â Â Â Â Â Â Â Â Â  height_right_subtree = GetHeight ( node.right ) + 1
3.Â Â Â Â Â Â diameter = maximum ( diameter, ( height_left_subtree + height_right_subtree ) )
4.Â Â Â Â Â Â # Return the maximum height of the ( left subtree, right subtree )
Â Â Â Â Â Â Â Â  return 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 = 0
height_right_subtree = 0

if (root.left) :
height_left_subtree = self.GetHeight(root.left) + 1
if (root.right) :
height_right_subtree = self.GetHeight(root.right) + 1

# 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 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 = 0;
int height_right_subtree = 0;

if (root->left)
height_left_subtree = GetHeight(root->left) + 1;
if (root->right)
height_right_subtree = GetHeight(root->right) + 1;

// 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 )
return 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
``````
``````import java.util.List;
import java.util.Arrays;
import java.lang.Math;

class Node {

int data;
Node left;
Node right;

Node (int x) {
data = x;
left = null;
right = null;
}

Node (int x, Node left_node, Node right_node) {
data = x;
left = left_node;
right = right_node;
}
}

class BinTree {

int diameter = 0; // Stores the maximum diameter found so far.

int GetHeight (Node root) {

if (root == null) {
return 0;
}

int height_left_subtree = 0;
int height_right_subtree = 0;

if (root.left != null)
height_left_subtree = GetHeight(root.left) + 1;
if (root.right != null)
height_right_subtree = GetHeight(root.right) + 1;

// 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 = Math.max (diameter, (height_left_subtree + height_right_subtree));

// Return the maximum height of the ( left subtree, right subtree )
return Math.max (height_left_subtree, height_right_subtree);
}

int FindDiameter (Node root) {
GetHeight(root);
return diameter;
}

public static void main (String[] args) {

/* Constructed binary tree is
9
/   \
5     16
/  \   /  \
3   7  12   18
/ \       \
6   8      25
/  \
20  36
*/

Node node3 = new Node(3);
Node node6 = new Node(6);
Node node8 = new Node(8);
Node node12 = new Node(12);
Node node20 = new Node(20);
Node node36 = new Node(36);

Node node7 = new Node(7, node6, node8);
Node node25 = new Node(25, node20, node36);
Node node18 = new Node(18, null, node25);
Node node16 = new Node(16, node12, node18);
Node node5 = new Node(5, node3, node7);
Node root_node9 = new Node(9, node5, node16);

/* Subtree
18
\
25
/  \
20  36  */

Node _node20 = new Node(20);
Node _node36 = new Node(36);
Node _node25 = new Node(25, _node20, _node36);
Node root_node18 = new Node(18, null, node25);

/* Subtree
7
/ \
6   8
\
9 */

Node _node9 = new Node(9);
Node _node6 = new Node(6);
Node _node8 = new Node(8, null, _node9);
Node root_node7 = new Node(7, _node6, _node8);

/* Subtree
16
\
18 */

Node _node18 = new Node(18);
Node root_node16 = new Node(16, null, _node18);

/* Subtree
3 */

Node root_node3 = new Node(3);

List<Node> tree_roots = Arrays.asList ( root_node9, root_node18, root_node7, root_node16, root_node3 );

BinTree b = new BinTree();

for (Node node : tree_roots) {
b.diameter = 0;
b.FindDiameter(node);
System.out.println("Diameter of tree with root " + node.data + " is : " + b.diameter);
}
}
}
``````

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