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;
};
