Adding up all node values in a binary tree

Each node of a tree stores a number and has at most two children. Write a routine that returns the total of all node values.

Recursive traversal: sum(node) is $0$ for an empty node, else its value plus the sums of both subtrees. Every node is visited once, so time is $O(n)$ and the stack depth is the tree height $h$. For very deep, unbalanced trees, use an explicit stack or queue to avoid stack overflow.