The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Tree

Problem :-
Compute the Diameter of a given Binary Tree.
Diameter of a tree is the largest path between any two leaf nodes in the tree.
For e.g, in the tree shown below diameter is 5 because the longest path ( { 29 , 24 , 16 , 31 , 52 } or
{ 19 , 24 , 16 , 31 , 52 } ) consists of 5 nodes.

Diameter of a tree

Solution :-
Assume that root node is a part of the longest path between two leaf nodes. We need to compute the height of left subtree ( lh ) and the right subtree ( rh ) of root. Then, the diameter is lh + rh + 1. We will recursively consider other nodes of the tree as part of longest path and compute the diameters. Finally, we will return the maximum diameter. See the implementation below.

#include<iostream>
using namespace std;

// get the max of two no.s
int max(int a, int b) {
   return ((a > b) ? a : b);
}

typedef struct node {
   int value;
   struct node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
   node *new_node = new node;
   new_node->value = value;
   new_node->left = NULL;
   new_node->right = NULL;
   return new_node;
}

// compute height of the tree
int getHeight(node *root) {
   if (root == NULL)
      return 0;

      // find the height of each subtree
      int lh = getHeight(root->left);
      int rh = getHeight(root->right);

      return 1 + max(lh,rh);
}

// compute tree diameter recursively 
int getDiameter(node *root) {
   if (root == NULL)
      return 0;

   // get height of each subtree
   int lh = getHeight(root->left);
   int rh = getHeight(root->right);

   // compute diameters of each subtree
   int ld = getDiameter(root->left);
   int rd = getDiameter(root->right);

   return max(lh+rh+1,max(ld,rd));
}

// create the tree
node *createTree() {
   node *root = getNewNode(31);
   root->left = getNewNode(16);
   root->right = getNewNode(52);
   root->left->left = getNewNode(7);
   root->left->right = getNewNode(24);
   root->left->right->left = getNewNode(19);
   root->left->right->right = getNewNode(29);
   return root;
}

// main
int main() {
   node *root = createTree();
   cout<<"\nDiameter of the tree is "<<getDiameter(root);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Trees
* Implement the inorder , preorder and postorder traversal mechanisms of a tree
* Implement an algorithm to insert a node in a Binary Search Tree ( BST )
* Implement an algorithm to find the height of a Binary Tree
* Implement an algorithm to get the level of a node in a Binary Tree assuming root node to be at level 1
* Get the root to leaf path in a Binary Tree such that the sum of the node values in that path is minimum among all possible root to leaf paths
* Print all the ancestors of a given node in a Binary Tree
* Replace all the node values with the sum of the node values of ancestral nodes in a Binary Tree
* Check if the given tree is a sum tree i.e value at each node is equal to the value of all elements in its left subtree and right subtree
* Given a Binary Tree, create another tree which is a mirror image of the given tree
* Construct a tree, given its inorder and preorder traversals
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Search Tree
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Tree
* Compute the Diameter of a given Binary Tree
* Check if a given tree is a Binary Search Tree ( BST )