# CodeStepByStep ## removeEveryKthLeaf

Language/Type: C++ binary trees pointers recursion

Write a function named `removeEveryKthLeaf` that accepts a reference to a pointer to a `BinaryTreeNode` representing the root of a binary tree and an integer k, and modifies the tree by removing every kth leaf node from the tree, using an in-order traversal. Recall that a leaf is a node that has no children. For example, if k is 3, your function should remove every third leaf that would be seen during an in-order traversal.

If the value of k is 0 or negative, you should throw an `int` exception. If k is 1, remove all leaves in the tree. If the tree is null or there are fewer than k leaves in the given tree, no change should be made to the tree.

The following diagrams show several calls to your function on a given initial tree with various values of k. Note that the original tree's six leaf nodes, as visited by an in-order traversal, are: 3, 1, 18, -6, 35, 4. Each call is independent, not sequential; all of these calls show results if the given call were made on the original tree.

original tree

`removeEveryKthLeaf(tree, 1);`
or, `removeEveryKthLeaf(tree, 2);` or, `removeEveryKthLeaf(tree, 3);`
`(7 (2 (3) (1)) (41 (5 (18) (9 (-6))) (7 / (-2 (35) (13 (4))))))`
`(7 (2) (41 (5 / (9)) (7 / (-2 / (13)))))`
`(7 (2 (3)) (41 (5 (18) (9)) (7 / (-2 (35) (13)))))`
`(7 (2 (3) (1)) (41 (5 / (9 (-6))) (7 / (-2 (35) (13)))))`

Note that your function might cause some nodes that were previously branches to become leaves. For example, the call above with k = 2 causes the former branch node 13 to become a leaf. These new leaves should not be counted by your algorithm for the purposes of removing every kth leaf; only nodes that were nodes at the time of the call should be considered for removal.

Constraints: You must implement your function recursively and without using loops. Do not construct any new `BinaryTreeNode` objects in solving this problem (though you may create as many `BinaryTreeNode*` pointer variables as you like). Do not leak memory; you must delete the memory for any node objects you remove from the tree. Do not leave any node pointers in the tree that point to invalid or deleted memory; null out any such pointers. Your solution should be at worst O(N) time and must make only a single pass over the tree. Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).

Assume that you are using the `BinaryTreeNode` structure as defined below:

```struct BinaryTreeNode {
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
};
```
Function: Write a C++ function as described, not a complete program.