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:

	#include<iostream>
	#include<queue>
	using namespace std;
	struct node {
	int value;
	node *left;
	node *right;
	node(int v):value(v),right(0),left(0){}
	};
	void reorder_tree(node * current) {
	if(current == 0) {
	return;
	}
	reorder_tree(current->left);
	reorder_tree(current->right);
	// now reorder the current node.
	node *larger = current;
	if (current->left && current->left->value > larger->value) {
	larger = current->left;
	}
	if (current->right && current->right->value > larger->value) {
	larger = current->right;
	}
	//swap value if necessary
	if (larger != current) {
	int tmp = larger->value;
	larger->value = current->value;
	current->value = tmp;
	//reorder for the swaped node since we don't know
	// it is bigger than children.
	reorder_tree(larger);
	}
	}
	void print_tree(node * root) {
	queue<node *> que;
	que.push(root);
	int current_child_count = 1;
	int next_child_count = 0;
	while(que.size() > 0) {
	node * current = que.front();
	que.pop();
	current_child_count--;
	cout<<current->value<< " ";
	if(current->left) {
	que.push(current->left);
	next_child_count++;
	}
	if (current->right) {
	que.push(current->right);
	next_child_count++;
	}
	if (current_child_count == 0) {
	cout<<" "<<endl;
	current_child_count = next_child_count;
	next_child_count = 0;
	}
	}
	}
	int main() {
	node *n1 = new node(1);
	node *n2 = new node(2);
	node *n3 = new node(3);
	node *n4 = new node(4);
	node *n5 = new node(5);
	node *n6 = new node(6);
	node *n7 = new node(7);
	node *n8 = new node(8);
	node *n9 = new node(9);
	node *n10 = new node(10);
	node *n11 = new node(11);
	node *n12 = new node(12);
	node *n13 = new node(13);
	n2->left = n5;
	n2->right = n6;
	n5->left = n4;
	n5->right = n3;
	n6->left = n8;
	n6->right = n9;
	n8->left = n13;
	n8->right = n12;
	n9->left = n1;
	n9->right = n11;
	cout<<"before reordering" << endl;
	print_tree(n2);
	reorder_tree(n2);
	cout<<"before reordering" << endl;
	print_tree(n2);
	}

view raw yext_reorder_tree_recursively.cpp hosted with ❤ by GitHub

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:

	class Node:
	def __init__(self, value, parent=None):
	self.value = value
	self.parent = parent
	self.left = None
	self.right = None
	def reorder_tree(node):
	if node == None:
	return
	# reorder the left and right recursively
	reorder_tree(node.left)
	reorder_tree(node.right)
	# reorder the current node and the largest between left and right.
	to_swap = node.right if node.left is None else node.left
	to_swap = node.left if node.right is None or node.left.value > node.right.value else node.right
	if to_swap != None and to_swap.value > node.value:
	tmp = node.value
	node.value = to_swap.value
	to_swap.value = tmp
	reorder_tree(to_swap)
	def print_tree(root):
	queue = []
	cur = 1
	next = 0
	queue.append(root)
	while len(queue) > 0:
	node = queue.pop(0)
	cur -=1
	print("{} ".format(node.value), end='')
	if node.left != None:
	next += 1
	queue.append(node.left)
	if node.right != None:
	next += 1
	queue.append(node.right)
	if cur == 0:
	print("\n", end='\n')
	cur = next
	next = 0
	# test
	c2 = Node(2, None)
	c5 = Node(5, c2)
	c10 = Node(10, c2)
	c2.left = c5
	c2.right = c10
	c4 = Node(4, c5)
	c3 = Node(3, c5)
	c5.left = c4
	c5.right = c3
	c8 = Node(8, c10)
	c9 = Node(9, c10)
	c10.left = c8
	c10.right = c9
	c12 = Node(12, c8)
	c6 = Node(6, c8)
	c8.left = c12
	c8.right = c6
	c1 = Node(1, c9)
	c11 = Node(11, c9)
	c9.left = c1
	c9.right = c11
	root = c2
	print_tree(root)
	reorder_tree(root)
	# print tree
	print_tree(root)

view raw reorder_tree_decending.py hosted with ❤ by GitHub