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


Diameter_Of_A_Binary_Tree


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-2022, Algotree.org.
All rights reserved.