—
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
18. The answer is 2
Summary
Usually, all recursion steps are not visualized and just assumed to be working. This post tries to exhaust a recursion flow and help understand it better.
Advertisements
Published by