Reordering the values in the binary tree.

Problem

Given the tree as below, write the code that fixes the order of the tree such that the value of the parent is always larger than the value of the children (left, right)

struct node {
    int value;
    node *left;
    node *right;

    node(int v):value(v),right(0),left(0){)
}

Input: root node

               2
            /    \
           5       10
          / \     /  \
         4   3   8    9 
                  / \      /  \
                12  6  1   11

The expected result will be:

           12  

         /       \ 

       5         11  

     /    \      /    \

    4     3  10        9  

              /   \       /   \

            8    6    1      2

Answer

Recursive approach

We can do the bottom-up reordering by using the DFS approach. 

The idea is that we go deep into the leaves of the tree and do the reordering first before moving up to the next level.

In the example above, we start from '4' and '3' with '5' on the left side of the tree. 

On the right side, '12' and '6' is reordered with '8' first and the swap happens between 6 and 12.

The same happens for '1' and '11' with '9', '11' will be swapped with '9'. 

After that, we have '12' and '11' as children of '10'. Therefore, '12' is swapped with '10'.

Finally, '5' on the left and '10' on the right will be compared with its parent '2'.

'2' and '10' will be swapped and '10' will be a new root. 

Are we done now? Does a new tree satisfy the invariant of parents' values being larger than those of children?

The answer is No. Something is missing. New root '10' has '2' as a right child but '2' is smaller than its children. 

There is one thing we forgot to do. When swapping happens, we should make sure that a new swapped value (old parent) is still larger than its new children.

After all, we need to perform "reordering" on the old parent node as well.

Swapping up one value from the leaf to the root takes around $O(N)$.  However, we need to perform the additional swapping for the old parent node. This swapping will take $O( \log_2 N)$ since the height of the tree is $O( \log_2 N)$. If all N nodes will require additional swap. Overall running time will be O(N \log_2 N). 

Here is the C++ solution for this problem:

Practice statistics:

20:00 to write the code.

15:00: to debug the code to handle additional swap for an old parent. 

UPDATE(2022-06-17): Resolve the problem again. Initially, I mistakenly thought I could use the MaxHeap to resort to the tree by adding all the nodes to the heap without replacing the pointer. Later I realized that this way will not work unless I reconstruct the pointers from the root all over again. The original recursive ordering is the best way to solve this problem with the least amount of code so far.

Here is the algorithm:

For the given node:

 - reorder the left side of the tree recursively to bubble up the larger number upward.

 - reorder the right side of the tree recursively to bubble up the larger number upward

 - check if the current node is larger than both left and right. If not, bubble up the larger child and recursively check if the current node is larger than the children of a replaced child. (it is bubbling the current node down the tree). 

Here is the complete code: