×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

Diameter of Binary Tree

In this article, we are going to see how to find diameter of a tree? This is a very popular problem to be asked and has already been featured in Amazon, MakeMyTrip, Microsoft, Oracle, VMWare, Oyo rooms etc. Submitted by Radib Kar, on February 11, 2019

Problem statement

Given a Binary Tree, find diameter of it. The diameter of a tree is the number of nodes on the longest path between two leaves in the tree.

Example

Diameter of Binary Tree
    For the above tree:

    Diameter is 7

    Longest paths:
    11->6->7->2->5->.9->4
    5->6->7->2->5->9->4
    
    Both have 7 nodes

Solution Approach

Diameter of a tree

Diameter of a tree is number of nodes on the longest path between two leaves of tree.

Now the fact is the longest path always passes through the root.

In fact no of nodes=height of left subtree (there is the source/destination leaf node) + height of right subtree(there is the destination/source leaf node) + 1(for root)

So actually the solution depends on finding the height of each subtree.

Finding height of each subtree can be done using recursion or level order traversal. However, I prefer level order traversal (BFS rocks!)

Algorithm

Diameter=height of left subtree + height of right subtree+1

Pre-requisite:

A Queue q for level-order traversal, input binary tree, function to calculate height of subtrees

FUNCTION height (root)
1.  Set h=1;
    EnQueue (q, root);
    EnQueue (q, NULL);
    While(q is not empty)
        temp=DeQueue(q) 	
        IF(temp is NULL)
            IF(q is not empty)
                EnQueue (q, NULL);
                h++; //increment height as this is the end of the processed level
            End IF
        ELSE
            IF(temp->left)
                EnQueue (temp->left);
            IF(temp->right)
                EnQueue (temp->right);
            End IF-ELSE
    End While

2.  Return h; //height of the tree
End FUNCTION
FUNCTION diameter (root)
	Return height (root->left) +height(root->right) +1;
End FUNCTION

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class TreeNode{    
	public:
	int data;
	TreeNode *left;
	TreeNode *right;
};

// creating new node for tree
TreeNode* newnode(int data)  
{ 
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 

	return(node); 
} 

int height(TreeNode* node){
	int h=1;	
	queue<TreeNode*> q;
	Node* temp;
	
	q.push(node);
	q.push(NULL);
	while(!q.empty()){
		temp=q.front();
		q.pop();
		if(!temp){
			if(!q.empty()){
				q.push(NULL);
				h++;
			}
		}
		else{
			if(temp->left)
				q.push(temp->left);
			if(temp->right)
				q.push(temp->right);
		}
	}
	return h;
}

int diameter(TreeNode* node)
{
	if(node==NULL)
		return 0;
	return height(node->left)+height(node->right)+1;
}

int main() { 
	//**same tree is builted as shown in example**
	int k;
	cout<<"same tree is built as shown in example\n";
	
	TreeNode *root=newnode(2); 
	
	root->left= newnode(7); 
	root->right= newnode(5); 
	root->right->right=newnode(9);
	root->right->right->left=newnode(4);
	root->left->left=newnode(2); 
	root->left->right=newnode(6);
	root->left->right->left=newnode(5);
	root->left->right->right=newnode(11);

	cout<<"Diameter of the tree is:\n"<<diameter(root);

	return 0; 
} 

Output

same tree is built as shown in example
Diameter of the tree is:
7 

Explanation with example

For our example tree
Calculating height of left-subtree

Root=2;
Root->left=7
Root->right=5
------------------------------------------

height(7)
h=1
root=7
Push 7
Push NULL
Queue status:
7, NULL

1st iteration
Queue not empty
Queue front is 7
Pop 7
Push: 7->left(2) & 7->right(6)
Queue status: NULL, 2, 6
------------------------------------------

2nd iteration
Queue not empty
Queue front is NULL
Pop NULL
Increment h; h=2
Push: NULL
Queue status: 2, 6, NULL
------------------------------------------

3rd iteration
Queue not empty
Queue front is 2
Pop 2
Push: Nothing ( 2->left (NULL) and 7->right (NULL) 
Queue status:  6, NULL
------------------------------------------

4th iteration
Queue not empty
Queue front is 6
Pop 6
Push: 6->left (5) 6->right (11) 
Queue status: NULL, 5,11
------------------------------------------

5th iteration
Queue not empty
Queue front is NULL
Pop NULL
Increment h//h=3

Push: NULL
Queue status: 5, 11, NULL
------------------------------------------

6th iteration
Queue not empty
Queue front is 5
Pop 5
Push: Nothing (5->left is NULL, 5->right is NULL)
Queue status: 11, NULL
------------------------------------------

7th iteration
Queue not empty
Queue front is 11
Pop 11
Push: Nothing (11->left is NULL, 11->right is NULL)
Queue status: NULL
------------------------------------------

8th iteration
Queue not empty
Queue front is NULL
Pop NULL
Queue is empty
So no more pushing NULL
------------------------------------------

Queue is empty, hence end
Thus height of left subtree is 3

Same way we can proceed to calculate right subtree height which is also 3
Thus diameter of the tree is 3+3+1=7


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.