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