check if a given binary Tree is a SumTree or not

Показать описание

Given a binary tree , check if it is a sumTree or not.

Рекомендации по теме

Комментарии

This is an unoptimized way. You can make it optimized with this hint: Subtree sum = 2X(currentNode.value) where currentNode is the root of subtree. eg. left subtree sum for tree rooted at 13 is 2*5 = 10 (5+3+2) This is only true for sumtree so this will be the condition.

shobhanksharma

SIR PLZ GIVE A LECTURE ON ALL THE PROPERTIES OF BINARY TREE AND ALL TYPES OF BINARY TREES IN DETAIL

ghanshamsingh

Code in python..

def is_sum_tree(self, root):
if root is None:
return False
if root.rchild is None and root.lchild is None:
return root.data
if root.data == self.is_sum_tree(root.lchild) + self.is_sum_tree(root.rchild) :
return True
return False

pymondo

If it's a leaf node, then I think it should not return 1, it should return (root->val). Tell me if I am wrong

adarshanand

Here is one more solution(xD): Do the post order traversal of the binary tree and store the data of the node in an array. Then, find the sum of the elements of array till n-2(where n is the size of array). Check if sum is equal to the (n-1)th element of the array, if its is equal then it is a sum tree else not.

manakupadhyay

Sir,
Please do videos on DATA STRUCTURES and ALGORITHMS on every topic.
Please please....

santhosh........

sir could you give the a video on find the largest binary search tree in a binary tree program

veerrajuyeleti

This algo won't work in case of just single node in a tree.

yunususmani

this solution has o(n^2) time complexity and in interviews we are supposed to give solution in linear time complexity ...so i think this solution is not worthy...please guide me if i am wrong it will be appreciated :)

gauravshukla