Background reading

Read sections 6.1 and 6.2 in the text.

The problem

Do programming exercise 2 from the end of chapter 6.

Building the tree

Use the following class for the nodes of the tree

class node {
  public:
    int value;
    char source;
    node *left, *right, *parent;
    
    node(int v) : value(v), source('n'),
      left(nullptr), right(nullptr), parent(nullptr) {}
};

To construct the initial tree from an array of N ints, start by determining 2^k, the smallest power of two that is greater than or equal to N+1. Make 2^k nodes and store pointers to these nodes in an array. Fill the first N of the nodes with values from the original array, and put the E value in the remaining nodes. This first set of nodes will be the leaves for your tree.

Next, start combining the leaves two at a time to form the parent nodes for the leaves. As you form each parent, place the smaller of the two child values in the parent node and set the source value to indicate which of the two children was responsible for the parent's value. If the left child node has the smaller value set source to 'l'. If the right child node has the smaller value set source to 'r'. As you make the parent nodes, store their pointers in the array, overwriting the pointers in that array from left to right as you go.

Repeat the parent building process with the parents you constructed in the first round, forming grandparent nodes from the parents. This process repeats until you have constructed a full tree from the initial leaf nodes. Using the source values you should be able to walk down the tree from the root to the leaf that was responsible for the root having its value.

Running the algorithm

The algorithm proceeds in a series of N rounds. In each round we will take the value in the root and copy it back to the original array of ints, filling up the original array with ints in ascending order as we go.

On each round, start at the root and use the source values to work your way down to the leaf that contributed that value. Replace that leaf's value with E, and then work your way back up to the root using the parent pointers. As you come to each internal node along that path from the leaf to the root, update its value and its source setting so that at all times those internal nodes store the value of the smaller of their two children, and the source member variable tells us which of the two children has the smaller value.