Write a recursive function named stretch that replaces each single binary tree node with multiple nodes with smaller values.
Your function accepts two parameters: a reference to a TreeNode pointer representing the root of a binary tree , and an integer "stretching factor" K.
Your function should replace each node N with K nodes, each of which stores a data value that is 1/K of N's original value, using integer division.
The new clones of node N should extend from their parent in the same direction that N extends from its parent.
For example, if N is its parent's left child, the stretched clones of N should also be their parent's left child, and vice versa if N was a right child.
The root node is a special case because it has no parent; we will handle this by saying that its stretched clones should extend to the left.
For example, suppose a variable named root refers to the root of the tree below at left.
If we then make the function call of stretch(root, 2); , notice that the root node of value 12 has become two nodes of value 6.
Its left child 81 has stretched into two leftward branch nodes storing 40 (which is 81 / 2 rounded down).
Its right child 34 has stretched into two rightward branch nodes storing 17.
And so on.
We also demonstrate the result of calling your function on the same original tree with a stretch factor of 3, in which each node stretches itself into three smaller valued nodes.
The root of 12 stretches into 3 nodes of 4; the children of 81 and 34 stretch into 3 nodes of 27 and 11 respectively; and so on.
| tree |
after stretch(root, 2); |
after stretch(root, 3); |
(12 (81 / (56))) (34 (19) (6)))
|
(12 (81 / (56))) (34 (19) (6)))
|
(12 (81 / (56))) (34 (19) (6)))
|
If the stretch factor K passed is 0 or negative, throw an integer exception.
Constraints:
Do not create any unnecessary BinaryTreeNode objects.
If your stretch factor is K, you should create K-1 new nodes for each existing node in the tree, but no more.
In particular, do not throw away the existing nodes that were present in the tree; modify and reuse them as much as possible.
Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).
Your solution should be at worst O(N * K) time, where N is the number of elements in the tree.
You must also solve the problem using a single pass over the tree, not multiple passes.
Your solution must be recursive; loops are allowed, but your overall traversal of the tree should use recursion.
Assume that you are using the BinaryTreeNode structure as defined below:
struct BinaryTreeNode {
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
};
