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(n**and space complexity is^{2})**O(n)**due to auxiliary stack.