Problem:
Binary Tree is Sum tree or Not. [Problem Link]
Explanation:
Write a function which returns True if the given binary tree is a Sum Tree, else False. A sum tree a is a binary tree where the value of a node is the summation of the subtree at both its left and right. An empty tree is also a sum tree and value of its sum can be considered as 0. A leaf node is also considered as sum tree. For example, following is a sum tree,
26
/
10 3
/ /
6 4 3
Solution:
Well, I decided some definitions here. Like, first of all, I used Complete Binary Tree in my solution.
The way my solution represents a tree in memory has been written by me. I studied the Linked List Representation of Trees and from there I derived this way of representation. It will need only ((n-1)*3) number of memory spaces to store a tree of n items for Worst Cases. But actually I designed this for Binary Search Trees and the statistics works there, here I have just used it to ignore the hazard for storing binary tree in memory. So in this case the above given statistics won’t work.
My solution only works for distinct elements. If user inputs an element more than once, it can cause a wrong result, even it can also hang the solution.
My solution consists a text box where user will input an item and will press the corresponding button ‘Insert Item’ to insert the item. Now, supposing that the user is going to insert the above given tree. Then he will have to insert 26 first. Then he will have to insert all the items of depth 2. The Item of depth 2 are 10, 13. After inserting those he will have to insert all the items of depth 3. The items of depth 3 are 6, 4, 3. So the rule is, insert Items of a depth at once in order.
My solution will create a table initially. There is button called ‘Clear all entered data’ pressing which user can remove any entered tree (remember, it will delete the whole tree, not a single item).
To have the final result user will have to press the ‘Find if it is a sum or not?’ button. The result will be viewed in the text box beneath the ‘Find if it is a sum or not?’ button.
The solution will initially load the following tree,
50
/
10 20
/ /
6 4 5 5
Result to this table will be as follows,
I hope you all have understand. Now you can download the solution from this link and after test, please leave a comment here.
[Click Here To Download the Solution for Check If Sum Tree problem]