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)