Tree

Problem 
Implement an algorithm to find the height of a Binary Tree.

Solution 
Height of the tree is defined as the number of nodes along the path from root node to the deepest leaf node.
The height of the tree shown below is 4. The paths with maximum number of nodes are { 29 , 24 , 16 , 31 } and
{ 19 , 24 , 16 , 31 }
.

height of a tree

We use a recursive approach to find the maximum of left subtree height and right subtree height and add 1 for the parent node. This process continues till we reach the deepest leaf node. 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);
}

// 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<<"\nHeight of the tree is "<<getHeight(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 )
About    Contact    Sitemap    Terms    Privacy