Write a function named zip
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 merging parent nodes with their children up to the specified level k.
Specifically, your code will traverse the tree looking for nodes with a single child and will merge the node with its child, producing a single node whose data
value is the sum of the parent's and the child's.
You will do this for up to k nodes at a time.
For example, if k is 2, you will merge two nodes at a time: one parent and one child.
If k is 3, you will merge a parent with its child and grandchild.
And so on.
When a parent merges with its child, it inherits any children of that child.
Note that you will only merge a parent node with its child if that parent has a single child, not if it has two children.
(The child itself could have any number of children.)
The merging process goes until you reach a node that doesn't have a single child or until you have merged k nodes.
The merging logic continues down the whole tree.
If the value of k is 0 or negative, you should throw an int
exception.
If the value of k is 1, do not modify the tree.
The following diagrams show several calls to your function on a given initial tree with various values of k.
Each call is independent, not sequential; all of these calls show results if the given call were made on the original tree.
 In the
zip(tree, 2)
call, notice how every 2 nodes are merged, where the parent has a single child: 5 merges with 4 to become 9; 7 merges with 15 to make 22; and so on.
This recurs later in the tree: 8 and 4 merge to become 12; 1 and 6 become 7; 6 and 2 become 8; and 7 and 3 become 10.
 The
zip(tree, 3)
call merges the first three nodes (5, 4, and 7) into 16; it then merges 15 and 2 into 17.
Node 2 has two children, so no third node merges with this pair.
Later in the tree, 8, 4, and 1 merge to become 13; 6 and 4 merge to become 10; and 6, 2, and 7 merge to become 15.
 The
zip(tree, 8)
call has such a high k value that it will merge long chains of nodes together.
It merges all of 5, 4, 7, 15, and 2 into 33; all of 8, 4, 1, 6, and 4 into 23; and all of 6, 2, 7, and 3 into 18.
Any k value of 5 or greater would have produced this same result for the given tree.
tree 
after zip(root, 2); 
after zip(root, 3); 
after zip(root, 8); 
5
/
4
\
7
\
15
/
__2__
/ \
8 1
\ / \
4 6 13
/ \
1 2
\ /
6 7
/ /
4 3

9
\
22
/
__2__
/ \
12 1
/ / \
7 8 13
/ /
4 10

16
\
__17__
/ \
13 1
\ / \
10 15 13
/
3

33
/ \
23 1
/ \
18 13

Constraints: