Diameter of binary tree in C++

28 Aug 2024 | 6 min read

In this article, you will learn about the diameter of binary trees in C++ with examples.

The number of edges that connect the longest paths between any two nodes in a binary tree allows us to calculate the diameter of a binary tree. The diameter of the binary tree is a measure commonly used to describe its breadth. The path taken is dependent upon the binary tree's diameter and may or may not traverse the binary tree's root. There are two leaf nodes in the path, each of whose diameter can be calculated. There are two possibilities for determining the longest path among two nodes expressing the binary tree's diameter:

By using Root Node: It will traverse the binary tree's root node and count the root node.
Not by using Root Node: In this example, the chosen path will not travel through the binary tree's base node and will not include it in the path.

Approach 1:

The measurement of the diameter of a tree T is the greatest of the following:

The left sub-tree length
The right sub-tree length
The longest path connecting leaves that runs through T's root (calculated using the heights of T's subtrees)

Filename: DiameterOfbtree.cpp

Output:

The diameter  is 4

Approach 2:

Efficient Approach:

You can use the below approach to solve the problem:

The above implementation can be improved by computing the height within the same iteration rather than calling heightoftree() function independently.

Output:

The diameter of the given binary tree is 4

Approach 3: Using the Morris Traversal Algorithm

The Morris Traversal Algorithm modifies the binary tree's structure by linking the left subtree's rightmost node to its parent. It allows you to navigate the tree without taking up extra space for the stack or recursive function.

To put the above idea into implementation, follow the steps below:

Use a current_node initialized as the binary tree's root to navigate the binary tree.
Perform the previous step if current_node is not NULL.
If the selected node's left child is NULL, proceed to the right child.
If the currently selected node's left child is not NULL, find the right-most node in the current node's left subtree.
Set the right child of the rightmost elements to the presently selected node and go on to the leftmost element of the current node when it is NULL.
If the right child is present in the rightmost node and is not NULL, visit the current node and proceed to the right child.
Using the maximum function, determine the left and right subtree heights for every visited node, and then update the diameter to be the maximum value of the heights of the subtrees combined with the existing diameter.
return diameter

Filename: Morris_Traversal.cpp

Output:

The diameter is 4

Complexities:

Time complexity: O(N), where N denotes the total number of nodes in a binary tree.

Space Complexity: O(h), Morris Traversal has an auxiliary space complexity of O(1) because it doesn't use additional information structures like stacks or queues. On the other hand, the recursive stack of a program increases the space complexity, resulting in O(h), where h is the binary tree's height.

Next TopicFoldable binary tree in C++

← prev next →