Height of a binary tree

Challenge

Measure the height of a binary tree.

Task

Given the node type typedef struct tnode { int v; struct tnode *l, *r; } tnode_t;, implement int tree_height(tnode_t *root) that returns the tree's height: the number of nodes on the longest path from the root down to a leaf.

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

int: the height. An empty tree (NULL) has height 0; a single node has height 1.

Example

NULL                       ->   0
single node                ->   1
root with depth-3 branch   ->   3

Edge cases

• An empty tree returns 0.
• A single leaf returns 1.

Input format

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

Output format

int: number of nodes on the longest root-to-leaf path (0 if empty).

Starter code

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

int tree_height(tnode_t *root) {
    /* TODO */
    return 0;
}