CodeStepByStep

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.

    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:

• Your solution must be recursive and must not use any loops.
• Do not create any data structures (arrays, vectors, sets, maps, etc.).
• Do not create any BinaryTreeNode objects. You may create pointers to objects, but not allocate new objects.
• Do not leak memory. You must delete the memory for any node objects you remove from the tree.
• Your solution should be at worst O(N) time and must make only a single pass over the tree.
• You may define helper functions if you like.

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

  struct BinaryTreeNode {
      int data;
      BinaryTreeNode* left;
      BinaryTreeNode* right;
  };