Problem:
Calculate height of a binary tree:
Logic:
In binary tree left subtree and right subtree are also binary trees. We will calculate height of each subtree and will select maximum of both. 1 is added to maximum height of tree to add distance of root from a subtree. Recursive method call was made for each node till node is null to get height of a tree.
|
1 2 3 4 5 6 |
int HeightOfTree(Node root) { if (root == null) return -1; return 1 + Math.Max(HeightOfTree(root.Left),HeightOfTree(root.right)); } |
If root is null (for left and right child of leaf node) we are returning value -1 because in a final result we are adding 1 . If we return 0 instead of -1 then for leaf node we will get height as 1 (o+1) instead of 0 which is wrong. So to balance 1 we are returning -1 in if condition.
If you want to understand recursive call and how we will get correct output as result, you can refer this and try to trace above function in same way.
Also if you are new to recursion, you can check my article on recursion.
To calculate height all nodes of tree are visited, so complexity of function will be O( n)