Diameter Of A Binary Tree In C++

Filed Under: C++
Diameter Of A Binary Tree In C

Today, we’ll learn to find the diameter of a binary tree in C++. Trees are one of the most important data structures we have in computer science. There are countless applications for trees in the real world. Ranging from your file managers to the most complex databases, trees are everywhere. Today we’ll solve another interesting problem based on trees.

Problem Statement of Diameter Of A Binary Tree in C++

You are given a binary tree, find the diameter of this binary tree. The input will be of the form given below.

Input: Root Node -> Left Subtree -> Right Subtree

-1 will be used to represent NULL(No child).

For example,

Tree:
8 10 1 -1 -1 6 9 -1 -1 7 -1 -1 3 14 13 -1 -1 -1 -1
Output: 6

Approach to Solve Diameter Of A Binary Tree in C++

Let’s first understand, what the diameter of a binary tree means. The diameter of a binary tree is the maximum possible distance between any two nodes of a binary tree. It doesn’t matter if both these nodes belong to the same subtree or not. All that matters is that the distance between this pair of nodes must be greater than or equal to the maximum possible distance between all other pairs.

In the case of binary trees, there can only be three possibilities.

  1. The diameter passes through the root node.
  2. It lies entirely in the left subtree.
  3. Otherwise, the diameter lies entirely in the right subtree.

Below is the formula to calculate the diameter and height of a binary tree.

diameter = max(height_left + height_right, diameter_left, diameter_right);
height = max(height_left, height_right);

Pseudocode

  • Start iterating from the leaf nodes, and move towards the top.
  • During each iteration, we’ll find the height and diameter of a subtree.
  • But, instead of finding the height of each subtree, again and again, we’ll store these heights and pass them to other function calls recursively. This’ll help cut down redundant calculations.
  • It’ll be similar to a post-order traversal.
  • During each function call, we’ll return the following.
    • Height of that particular node.
    • Diameter of that subtree/root node.

Queue Using Two Stacks Problem In C++ Program

#include <iostream>
#include <queue>

using namespace std;

class Node
{
 public:
    int data;
    Node*left;
    Node*right;
    
    Node(int d)
    {
        data=d;
        right=NULL;
        left=NULL;
    }
};

class Pair
{
public :
    int height;
    int diameter;
};

Node*build()
{
    int d;
    cin>>d;
    if(d==-1)
    {
        return NULL;
    }
    
    Node*root=new Node(d);
    root->left=build();
    root->right=build();
    
    return root;
}

void printBFS(Node*root)
{   
    queue <Node*> q;
    
    q.push(root);
    q.push(NULL);
    
    while(!q.empty())
    {
        Node*f=q.front();
        if(f==NULL)
        {
            cout<<endl;
            q.pop();
            if(!q.empty())
            {
                q.push(NULL);
            }
        }
        
        else 
        {
            cout<<f->data<<" ";
            q.pop();
            
            if(f->left)
            {
                q.push(f->left);
            }
            if(f->right)
            {
                q.push(f->right);   
            }
        }
    }
    
    return ;
}

// function to calculate the diameter of the tree
// the function returns a Pair object
// it will contain both the diamter and the height
// of the tree
Pair fast_diameter(Node* root)
{
	Pair p;

	// base case
	if(root == NULL)
	{
		p.height = 0;
		p.diameter = 0;

		return p;
	}

	// otherwise
	// 1. left_subtree
	Pair left = fast_diameter(root->left);

	// 2. right_subtree
	Pair right = fast_diameter(root->right);

    // time to calculate the diameter and height of this particular node
	p.diameter = max(max(left.diameter, right.diameter), left.height + right.height);
	p.height = max(left.height, right.height) + 1;

	return p;
}

int main()
{
	cout << "Enter the elements of the tree(root->left->right)" << endl;
    Node*root=build();
    cout<<"The tree is : "<<endl;
    printBFS(root);
    cout<<endl << "The diameter of this tree is: " << fast_diameter(root).diameter << endl;

    return 0;
}
Program Code 1
Program Code

Output

Diameter Binary Tree Output
Diameter Binary Tree Output

Conclusion

In this article, we learned to find the diameter of a binary tree in C++. First, we went through the problem statement. Next, we looked at the concept behind the solution. In the end, we coded the solution and tested its working in the terminal. Please note that the time complexity of this algorithm is O(N). The main trick behind this optimized approach is the bottom-up concept that we used. Finding the diameter of all the subtrees starting right from the leaf nodes helped to eliminate a huge number of redundant cases.

Further Readings

To learn more about trees, do check out the following articles.

https://www.journaldev.com/56918/0-1-knapsack-using-cpp

https://www.journaldev.com/61662/intersection-point-of-two-linked-lists-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors