Check if a given Binary Tree is SumTree | GeeksforGeeks
Write a function that returns true if the given Binary Tree is SumTree else false. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.
1) If the node is a leaf node then sum of subtree rooted with this node is equal to value of this node. 2) If the node is not a leaf node then sum of subtree rooted with this node is twice the value of this node (Assuming that the tree rooted with this node is SumTree).
https://www.techiedelight.com/check-given-binary-tree-sum-tree-not/
Write a function that returns true if the given Binary Tree is SumTree else false. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.
26
/ \
10 3
/ \ \
4 6 3
https://www.techiedelight.com/check-given-binary-tree-sum-tree-not/
We can easily solve this problem by using recursion. The idea is to traverse the tree in postorder fashion. Then for each non-leaf node, we check if node’s value is equal to sum of all elements present in its left subtree and right subtree. If this relation do not hold true for any node, then the given binary tree cannot be a sum tree.
int isSumTree(Node *root)
{
// base case: empty tree
if (root == nullptr)
return 0;
// special case: leaf node
if (root->left == nullptr && root->right == nullptr)
return root->key;
// if root's value is equal to sum of all elements present in its
// left and right subtree
if (root->key == isSumTree(root->left) + isSumTree(root->right))
return 2*root->key;
return INT_MIN;
}
https://gist.github.com/KodeSeeker/9716087
X. O(N^2)
http://nimishabidsar.blogspot.com/2016/10/check-if-given-binary-tree-is-sumtree.html
https://grajob.com/goldman-sachs-interviewcheck-if-a-given-binary-tree-is-sumtree/
Read full article from Check if a given Binary Tree is SumTree | GeeksforGeeks
Two approaches:
1)Check recursively for each node if the node value = sum of left and right.
O(n)
int sum(struct node *root)
{
if(root == NULL)
return 0;
return sum(root->left) + root->data + sum(root->right);
}
int isSumTree(struct node* node)
{
int ls, rs;
if(node == NULL ||
(node->left == NULL && node->right == NULL))
return 1;
ls = sum(node->left);
rs = sum(node->right);
if((node->data == ls + rs)&&
isSumTree(node->left) &&
isSumTree(node->right))
return 1;
return 0;
}
2) Use the fact that
if the tree is a sum tree then:
if (node (leaf))
return true;
for a given node:
if right child : leaf
left child : leaf
root .data = left.data+right. data
if right child: non- leaf
left-child : non- leaf
root.data= 2* right+ 2*left;
if right child: leaf
left-child : non- leaf
root.data= right+ 2*left;
if right child: non- leaf
left-child : leaf
root.data= 2* right+ left;
*/
boolean isLeaf(Node node)
{
if(n==null|| (n.getLeft()== null && n.getRight()== null))
{
return true;
}
return false;
}
public boolean isSumTree(Node root)
{
if(root == null)
return true;
if(isLeaf(root))
return true;
Node left = root.getLeft();
Node right= root.getRight();
int sum=0;
if(left!=null)
{
sum+= left.data;
if(!isLeaf(left))
sum+=left.data;
}
if(right!=null)
{
sum+= right.data;
if(!isLeaf(right))
sum+=right.data;
}
if(root.data != sum)
return false;
if(!isSumTree(root.getLeft()) || !isSumTree(root.getRight()))
return false;
return true;
}
http://shibaili.blogspot.com/2014/01/other-questions-check-if-given-binary.htmlbool isLeaf (Node* root) { if (root->left == NULL && root->right == NULL) { return true; } else return false;}bool isSumTree (Node* root) { if (root == NULL || isLeaf(root)) { return true; } if (isSumTree(root->left) && isSumTree(root->right)) { int leftSum = 0, rightSum = 0; if (isLeaf(root->left)) { leftSum = left->val; }else if (root->left == NULL) { leftSum = 0; }else { leftSum = root->left->val * 2; } if (isLeaf(root->right)) { rightSum = right->val; }else if (root->right == NULL) { rightSum = 0; }else { rightSum = root->right->val * 2; } return root->val == (rightSum + leftSum); } return false;}
The algorithm would be the same if we want to turn a tree to a valid sum tree ------------------------------------------------ Q: Implement a Stack class with O(1) min function. A: use an extra stack to contain all min values, O(n) space, use (push 2 * value - min to stack) to optimize space to O(1)
int isSumTree(struct node* node){ int ls; // for sum of nodes in left subtree int rs; // for sum of nodes in right subtree /* If node is NULL or it's a leaf node then return true */ if(node == NULL || isLeaf(node)) return 1; if( isSumTree(node->left) && isSumTree(node->right)) { // Get the sum of nodes in left subtree: extract as a method if(node->left == NULL) ls = 0; else if(isLeaf(node->left)) ls = node->left->data; else ls = 2*(node->left->data); // Get the sum of nodes in right subtree if(node->right == NULL) rs = 0; else if(isLeaf(node->right)) rs = node->right->data; else rs = 2*(node->right->data); /* If root's data is equal to sum of nodes in left and right subtrees then return 1 else return 0*/ return(node->data == ls + rs); } return 0;}X. O(N^2)
http://nimishabidsar.blogspot.com/2016/10/check-if-given-binary-tree-is-sumtree.html
Get the sum of nodes in left subtree and right subtree. Check if the sum calculated is equal to root’s data. Also, recursively check if the left and right subtrees are SumTrees.
/* A utility function to get the sum of values in tree with root as root */ int sum(Node node) { if (node == null) return 0; return sum(node.left) + node.data + sum(node.right); } /* returns 1 if sum property holds for the given node and both of its children */ int isSumTree(Node node) { int ls, rs; /* If node is NULL or it's a leaf node then return true */ if ((node == null) || (node.left == null && node.right == null)) return 1; /* Get sum of nodes in left and right subtrees */ ls = sum(node.left); rs = sum(node.right); /* if the node and both of its children satisfy the property return 1 else 0*/ if ((node.data == ls + rs) && (isSumTree(node.left) != 0) && (isSumTree(node.right)) != 0) return 1; return 0; }https://grajob.com/goldman-sachs-interviewcheck-if-a-given-binary-tree-is-sumtree/
Read full article from Check if a given Binary Tree is SumTree | GeeksforGeeks
