Sum of a binary tree

Challenge

Add up every value stored in a binary tree.

Task

Given the node type typedef struct tnode { int v; struct tnode *l, *r; } tnode_t;, implement long tree_sum(tnode_t *root) that returns the sum of the v field of every node in the tree.

Input

root: a pointer to the root node (the type tnode_t is given, with an int v and left/right child pointers l and r). May be NULL.

Output

long: the sum of all node values; 0 for an empty tree.

Example

NULL                          ->   0
tree with values 1, 2, 3      ->   6

Edge cases

• An empty tree (NULL) returns 0.
• Accumulate in a long so a large tree does not overflow.

Input format

root: pointer to a tnode_t (given: int v; tnode_t *l, *r;); may be NULL.

Output format

long: sum of every node's v value (0 if empty).

Constraints

Accumulate in long to avoid overflow.

Starter code

typedef struct tnode { int v; struct tnode *l, *r; } tnode_t;

long tree_sum(tnode_t *root) {
    /* TODO */
    return 0;
}