Amazon Question: Convert a binary tree to a tree that holds children sum tree

Problem: Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node (Structure can not be changed and decrement operation is not allowed).

Algorithm: Traverse given tree in post order to convert it, i.e., first change left and right children to hold the children sum property then change the parent node.

Let difference between node’s data and children sum be diff.

     diff = node’s children sum - node’s data  

If diff is 0 then nothing needs to be done.

If diff > 0 then increment the node’s data by diff.

If diff < 0 then increment one child’s data. We can choose to increment either left or right child if they both are not NULL. Let us always first increment the left child. Incrementing a child changes the subtree’s children sum property so we need to change left subtree also. So we recursively increment the left child. If left child is empty then we recursively call increment() for right child.

Implementation:

void increment(struct node* node, int diff)
{
  if(node->left != NULL)
  {
    node->left->data = node->left->data + diff;
    increment(node->left, diff);
  }
  else if (node->right != NULL)
  {
    node->right->data = node->right->data + diff;
    increment(node->right, diff);
  }
}

void convertTree(struct node* node)
{
  int left_data = 0,  right_data = 0, diff;
  if (node == NULL ||(node->left == NULL && node->right == NULL))
    return;
  else
  {
    convertTree(node->left);
    convertTree(node->right);

    if (node->left != NULL)
      left_data = node->left->data;

    if (node->right != NULL)
      right_data = node->right->data;

    diff = left_data + right_data - node->data;

    if (diff > 0)
       node->data = node->data + diff;

    if (diff < 0)
      increment(node, -diff);
  }
}