Check if binary tree is a sum tree

In this tutorial we shall check if the tree is a sum tree or not.

Problem Statement:

You are given the root node of a binary tree. You need to check if that tree is a sum tree or not.

Example:

Consider the binary tree given below:

check_if_tree_is_sum_tree

In the above image, it is a sum tree.

What is a sum tree?

A tree will be called as sum tree, if the parent node value is equal to the sum of it’s left sub tree and right sub tree.

For 1 and 2 parent node value is 3. That is the sum of 1 + 2
For 4 and 5 parent node value is 9, that is the sum of 4 + 5

For the root node value is 24, i.e it’s sum of left sub tree 3 + 2 + 1 = 6
and sum of right sub tree i.e 9 + 4 + 5 = 18.

By looking at the image, we can infer that, only the leaf node will not satisfy this condition.

But all the internal nodes need to satisfy this condition.

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *