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


© 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"