# Height of a Binary Tree: Recursion Unrolled & Explained

tags: >-
development, C++, tree, height, programming, recursion, internals, complete
flow
categories: development

Height of a Binary Tree is the longest path in the tree.

##### Code
``````int getHeight(node *root)
{
if (root == NULL) {
return -1;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);

return (max(leftHeight, rightHeight) + 1);
}
``````

Suppose the tree is as follows:

``````         [10]
|
[8]  [12]
|
[4] [5]
``````

The recursion flow is as following:

``````1. getHeight(10)
2. getHeight(left of 10) ==> getHeight(8)
3. getHeight(left of 8) ==> getHeight(NULL)
4. getHeight(NULL) returns -1
5. leftHeight = -1 and flow goes back to line # 3
6. Now, it calls right of 8, getHeight(right of 8)
7. getHeight(NULL) returns -1 to rHeight
8. Both subtree of 8 are traversed and leftHeight = -1, rightHeight = -1
9. It compares both values and return the max + 1
10. max( -1, -1) + 1 = 0
11. The node 8 is left subtree of 10, and returns to line # 2.
12. At node 10, leftHeight = 0
13. Now, rightHeight is calculated by moving to right of 10.
14. getHeight(right of 10) ==> getHeight(12)
15. Similar to above, height at node 12 is calculated as 1.
16. At the end, node 12 returns its height at line #14.
17. Again we compare max (0, 1) + 1