Problem:
Calculate sum of all nodes in a binary tree.
1 2 3 4 5 6 |
int SumOfNodes(Node rt) { if (rt == null) return 0; return rt.value + SumOfNodes(rt.left) + SumOfNodes(rt.right); } |
You refer following image to understand function calls in above recursive method.
We need to visit all nodes, so time complexity will be O( n)