Take the height-balanced tree code, and replace the key field by a field int leaves That field should contain the number of leaves below the node, so n->leaves - 1 if n is a leaf, and n->leaves -n->left->leaves + n->right->leaves else. The leaves field must be updated after an insertion or deletion for all nodes on the path from the root to the changed leaf, and after a rotation for the changed nodes. Then you (1) replace the find function by object.t *find.by_number (tree node-t *tree, int k); which returns the object stored in the k-th leaf from left (start counting with the leftmost leaf as 1); (2) replace the insert function by void insert.by-number (tree.node.t *tree, int k, object.t *new-obj); which inserts new.obj in a new k-th leaf, moving all leaves above it one step to the right (without renumbering), and (3) replace the delete function by object.t * delete.by number (tree node.t *tree, int k); which deletes (and returns) the object stored in the k-th leaf, moving all leaves above it one step to the left (without renumbering). Take the height-balanced tree code, and replace the key field by a field int leaves That field should contain the number of leaves below the node, so n->leaves - 1 if n is a leaf, and n->leaves -n->left->leaves + n->right->leaves else. The leaves field must be updated after an insertion or deletion for all nodes on the path from the root to the changed leaf, and after a rotation for the changed nodes. Then you (1) replace the find function by object.t *find.by_number (tree node-t *tree, int k); which returns the object stored in the k-th leaf from left (start counting with the leftmost leaf as 1); (2) replace the insert function by void insert.by-number (tree.node.t *tree, int k, object.t *new-obj); which inserts new.obj in a new k-th leaf, moving all leaves above it one step to the right (without renumbering), and (3) replace the delete function by object.t * delete.by number (tree node.t *tree, int k); which deletes (and returns) the object stored in the k-th leaf, moving all leaves above it one step to the left (without renumbering)