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;
}

Common mistakes

Dereferencing NULL child pointers; memory leaks when deleting nodes without freeing subtrees; losing track of parent pointers.

Edge cases to handle

Empty tree (root == NULL); single-node tree; degenerate/unbalanced linked-list tree; searching for absent key.