Representing Trees

There are a few ways to represent a tree T with n nodes.

One particularly flexible way is in terms of three arrays. For $0 \le i \le n-1$:

• T_v[i]: The key for node i.
• T_p[i]: The index of the parent of node i (-1 for root).
• T_l[i]: The index of the left child of node i (-1 if there is none).
• T_r[i]: The index of the right child of node i (-1 if there is none).

How can we test if node i is a leaf?