The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Tree

Problem :-
Check if the given tree is a sum tree i.e value at each node is equal to the value of all elements in its left subtree and right subtree. The Binary tree shown below is an example of a sumtree.

sum tree

Solution :-
Suppose we start at root node ( X ). We can compute the sum of the node values of left subtree ( sum1 ) and right subtree ( sum2 ). If X -> data = sum1 + sum2 and the same condition is true for each node in the left and right subtrees, then the given tree is a sum tree. See the implementation below.

#include<iostream>
using namespace std;

// tree node structure 
typedef struct tree_node {
   int value;
   struct tree_node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
   node *new_node = new node;
   new_node->value = value;
   new_node->left = NULL;
   new_node->right = NULL;
   return new_node;
}

// create the tree
node *createTree() {
   node *root = getNewNode(30);
   root->left = getNewNode(12);
   root->right = getNewNode(3);
   root->left->left = getNewNode(5);
   root->left->right = getNewNode(7);
   root->right->left = getNewNode(1);
   root->right->right = getNewNode(2);
   return root;
}

// get the sum of all elements in the subtree starting at a given node
int getSubtreeSum(node *ptr) {
   if (ptr == NULL) {
      return 0;
   }
   else {
      return getSubtreeSum(ptr->left) + ptr->value + getSubtreeSum(ptr->right);
   }
}

// check if the given tree is a sum tree i.e value at each node is equal to
// the value of all elements in left subtree and right subtree
bool isSumTree(node *ptr) {
   if (ptr == NULL || (ptr->left==NULL && ptr->right==NULL))
      return true;
   int left_subtree_sum = getSubtreeSum(ptr->left);
   int right_subtree_sum = getSubtreeSum(ptr->right);
   if (ptr->value == (left_subtree_sum + right_subtree_sum)
           && isSumTree(ptr->left) && isSumTree(ptr->right)) {
      return true;
   }
   else {
      return false;
   }
}

// main
int main() {
   node *root = createTree();
   if (isSumTree(root))
        cout<<"The given tree is a SumTree ";
   else
        cout<<"The given tree is not a SumTree ";
   cout<<endl;
   return 0;
}

Back | Next

All problems on Trees
* Implement the inorder , preorder and postorder traversal mechanisms of a tree
* Implement an algorithm to insert a node in a Binary Search Tree ( BST )
* Implement an algorithm to find the height of a Binary Tree
* Implement an algorithm to get the level of a node in a Binary Tree assuming root node to be at level 1
* Get the root to leaf path in a Binary Tree such that the sum of the node values in that path is minimum among all possible root to leaf paths
* Print all the ancestors of a given node in a Binary Tree
* Replace all the node values with the sum of the node values of ancestral nodes in a Binary Tree
* Check if the given tree is a sum tree i.e value at each node is equal to the value of all elements in its left subtree and right subtree
* Given a Binary Tree, create another tree which is a mirror image of the given tree
* Construct a tree, given its inorder and preorder traversals
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Search Tree
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Tree
* Compute the Diameter of a given Binary Tree
* Check if a given tree is a Binary Search Tree ( BST )