Friday, February 13, 2015

Check for children sum property in a binary tree

Problem: Given a binary tree, write a function that returns true if the tree satisfies below property:
For every node, data value must be equal to sum of data values in left and right children. Consider data value as 0 for NULL children.

Algorithm: Traverse the given binary tree. For each node check (recursively) if the node and both its children satisfy the Children Sum Property, if so then return true else return false.

Implementation:

bool isSumProperty(Node* node)
{
  int left_data = 0,  right_data = 0;
  if(node == NULL || (node->left == NULL && node->right == NULL))
    return true;
  else
  {
    if(node->left != NULL)
      left_data = node->left->data;
    if(node->right != NULL)
      right_data = node->right->data;
    if((node->data == left_data + right_data)&&
        isSumProperty(node->left) &&
        isSumProperty(node->right))
      return true;
    else
      return false;
  }
}

No comments:

Post a Comment