A binary tree is given, the task is to check if, it is a Sum Tree or not.
A SumTree is a Binary Tree where the value of a node is equal to the sum of the nodes present in its left subtree and right subtree.
An empty tree is SumTree and the sum of an empty tree can be considered as 0.
A leaf node is also considered as SumTree.
Solutions
Method 1: Recursion
Get the sum of nodes in the left subtree and right subtree using "sum()".
Check if the sum calculated for both left and right sub-trees is equal to the root's data.
Also, recursively check if the left and right subtrees are Sum Trees.
Complexity
The time complexity of this solution is O(n2) and space complexity is O(n) due to auxiliary stack.