Give the pseudocode of a recursive method int calculateHeigh

Give the pseudocode of a recursive method “int calculateHeight(Node p)” that, given the root node of a binary tree, computes the height of the binary tree. For example, in the tree above where the root is the node containing key 44, calculateHeight(root) would return the value 5.

Hint: use some of the tree traversals.

Assume as usual that class Node has accessor methods parent(), leftChild() and rightChild() each one returning a Node with obvious meaning.

Solution

static int max(int a, int b)
{
if (a >= b) {
return a;
}
return b;
}

unsigned int binarytree_height_recursive(const btnode *node)
{
unsigned int height = 0;
if (node->left || node->right) {
height = max(node->left ? binarytree_height_recursive(node->left) : 0,
node->right ? binarytree_height_recursive(node->right) : 0) + 1;
}
return height;
}

unsigned int binarytree_height(const binarytree *tree)
{
unsigned int height = 0;
if (tree->root) {
height = binarytree_height_recursive(tree->root);
}
return height;
}

2 way

if (node == null) {
return;
}
if ((node.right == null) && (node.left == null)) {
if (tempHeight < count) {
tempHeight = count;

}

}

findHeight(node.left, ++count);
count--; //reduce the height while traversing to a different branch
findHeight(node.right, ++count);

}

3 way

public static int getHeight (Node root){
int lheight = 0, rheight = 0;
if(root==null) {
return 0;
}
else {
if(root.left != null) {
lheight = 1 + getHeight(root.left);
System.out.println(\"lheight\" + \" \" + lheight);
}
if (root.right != null) {
rheight = 1+ getHeight(root.right);
System.out.println(\"rheight\" + \" \" + rheight);
}
if(root != null && root.left == null && root.right == null) {
lheight += 1;
rheight += 1;
}

}
return Math.max(lheight, rheight);
}

node* newNode(int data)
{
node *temp = new node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}

// Driver program to test above functions
int main()
{
// Let us create binary tree shown in above diagram
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

cout << \"Height of tree is \" << treeHeight(root);
return 0;
}