CODEWITHSUNDEEP
c++cdata-structuresbinary-tree
Vijay
Vijay

Reputation: 67221

Binary tree where value of each node holds the sum of child nodes

This question was asked of me in an interview. How can we convert a BT such that every node in it has a value which is the sum of its child nodes?

Upvotes: 2

Views: 7022

Answers (5)

Biswajit
Biswajit

Reputation: 41

Here is the code for the sum problem. It works i have tested it.

int sum_of_left_n_right_nodes_4m_root(tree* local_tree){

   int left_sum = 0;
   int right_sum = 0;
   if(NULL ==local_tree){
       return 0;
   }   
   if((NULL == local_tree->left)&&(NULL == local_tree->right)){
       return 0;
   }   
   sum_of_left_n_right_nodes(local_tree->left);
   sum_of_left_n_right_nodes(local_tree->right);
   if(NULL != local_tree->left)
       left_sum = local_tree->left->data + 
                  local_tree->left->sum;

   if(NULL != local_tree->right)
       right_sum = local_tree->right->data + \ 
                   local_tree->right->sum;

       local_tree->sum= right_sum + left_sum;


}

Upvotes: 1

Sarfaraz Nawaz
Sarfaraz Nawaz

Reputation: 361402

Here is a solution that can help you: (the link explains it with tree-diagrams)

Convert an arbitrary Binary Tree to a tree that holds Children Sum Property

/* This function changes a tree to to hold children sum
   property */
void convertTree(struct node* node)
{
  int left_data = 0,  right_data = 0, diff;

  /* If tree is empty or it's a leaf node then
     return true */
  if(node == NULL ||
     (node->left == NULL && node->right == NULL))
    return;
  else
  {
    /* convert left and right subtrees  */
    convertTree(node->left);
    convertTree(node->right);

    /* If left child is not present ten 0 is used
       as data of left child */
    if(node->left != NULL)
      left_data = node->left->data;

    /* If right child is not present ten 0 is used
      as data of right child */
    if(node->right != NULL)
      right_data = node->right->data;

    /* get the diff of node's data and children sum */
    diff = left_data + right_data - node->data;

    /* If node's data is smaller then increment node's data
       by diff */
    if(diff > 0)
       node->data = node->data + diff;

    /* THIS IS TRICKY --> If node's data is greater then increment left
      subtree  by diff */
    if(diff < 0)
      increment(node->left, -diff);
  }
}

See the link to see the complete solution and explanation!

Upvotes: 2

ig2r
ig2r

Reputation: 2394

Well as Charlie pointed out, you can simply store the sum of respective subtree sizes in each inner node, and have leaves supply constant values at construction (or always implicitly use 1, if you're only interested in the number of leaves in a tree).

This is commonly known as an Augmented Search Tree.

What's interesting is that through this kind of augmentation, i.e., storing additional per-node data, you can derive other kinds of aggregate information for items in the tree as well. Any information you can express as a monoid you can store in an augmented tree, and for this, you'll need to specify:

  1. the data type M; in your example, integers
  2. a binary operation "op" to combine elements, with M op M -> M; in your example, the common "plus" operator

So besides subtree sizes, you can also express stuff like:

  • priorities (by way of the "min" or "max" operators), for efficient queries on min/max priorities;
  • rightmost elements in a subtree (i.e., an "op" operator that simply returns its second argument), provided that the elements you store in a tree are ordered somehow. Note that this allows us to view even regular search trees (aka. dictionaries -- "store this, retrieve that key") as augmented trees with a corresponding monoid.

(This concept is rather reminiscent of heaps, or more explicitly treaps, which store random priorities with inner nodes for probabilistic balancing. It's also quite commonly described in the context of Finger Trees, although these are not the same thing.)

If you also provide a neutral element for your monoid, you can then walk down such a monoid-augmented search tree to retrieve specific elements (e.g., "find me the 5th leaf" for your size example; "give me the leaf with the highest priority").

Uhm, anyways. Might have gotten carried away a bit there.. I just happen to find that topic quite interesting. :)

Upvotes: 2

Tamer Shlash
Tamer Shlash

Reputation: 9523

With a recursive function you can do so by making the value of each node equal to the sum of the values of it's childs under condition that it has two children, or the value of it's single child if it has one child, and if it has no childs (leaf), then this is the breaking condition, the value never changes.

Upvotes: 0

Charlie Martin
Charlie Martin

Reputation: 112366

Give each node an attached value. When you construct the tree, the value of a leaf is set; construct interior nodes to have the value leaf1.value + leaf2.value.

If you can change the values of the leaf nodes, then the operation has to go "back up" the tree updating the sum values.

This will be a lot easier if you either include back links in the nodes, or implement the tree as a "threaded tree".

Upvotes: 3

Related Questions