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 k^{th} leaf node from the tree, using an inorder 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 inorder 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 inorder 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 k^{th} 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;
};