Problem:
Calculate sum of all the leaf nodes in binary tree.
Logic:
In this implementation we are passing 0 as initial result. When node is a leaf node(left child and right child is null) we are assigning node value to result. At the end of calls we are calculating addition of leaf nodes (that is result returned by each left and right sub-tree’s function call).
|
1 2 3 4 5 6 7 8 9 10 11 |
int SumOfLeafNodes(Node rt, int result) { if (rt == null) return 0; if (rt.left == null && rt.right == null) { result = rt.value; } return result + SumOfLeafNodes(rt.left, result) + SumOfLeafNodes(rt.right, result); } |
If you want to understand recursive call and how we will get correct output as result, you can refer this and try to trace this function in same way.
To calculate sum of leaf nodes , all nodes of tree are visited, so complexity of function will be O( n)