WAP to Calculate Maximum Height & Depth of Tree With & Without Recursion

Height/Depth of Tree Without Recursion


Data Structure Used:Queue

Algorithm
1.Insert Root Node in Queue & NUll After root Node.Inserting NULL will help us in measuring height of tree.
2.do remove front element from the queue until its is empty
if(front==NULL)
increment height=height+1;
check queue is empty or not if not insert NULL every time at this step.
else
insert root->left & root->right node into queue.

repeat above step 2 until queue is empty



#include
#include
#include

typedef struct TreeNode {
struct TreeNode *left, *right;
int data;

}TreeNode;


typedef TreeNode * Tree;

/*
*Function which returns height of a binary tree without recursion

We are using level order traversal
*/

int Height(Tree t) {

int height = 0;//-1;

if(t != NULL) {

std::list q; //Queue to store tree nodes

q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end of the level

while(!q.empty()) {

TreeNode *node = q.front();
q.pop_front();

if(node == NULL) {//delimeter encountered, increase height and push NULL if q not empty

height++;

if(!q.empty())
q.push_back(NULL);

}
else {

if(node->left)
q.push_back(node->left);

if(node->right)
q.push_back(node->right);
}

}

}

return height;
}


TreeNode * newNode(int data)
{
TreeNode *node = (TreeNode *)
malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int main()
{
Tree root = newNode(1);

root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Height of tree is %d", Height(root));

getchar();
return 0;
}



Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/gfgru


Maximum Height/Depth of Tree Using Recursion

Algorithm

1. If tree is empty then return 0
2. Else
(a) Get the max depth of left subtree recursively i.e.,
call maxDepth( tree->left-subtree)
(a) Get the max depth of right subtree recursively i.e.,
call maxDepth( tree->right-subtree)
(c) Get the max of max depths of left and right
subtrees and add 1 to it for the current node.
max_depth = max(max dept of left subtree,
max depth of right subtree)
+ 1
(d) Return max_depth



#include
#include
#include

struct node
{
int data;
struct node* left;
struct node* right;
};
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{ int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int main()
{
struct node *root = newNode(1);

root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Hight of tree is %d", maxDepth(root));

getchar();
return 0;
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/SoqlA