{"id":1907,"date":"2020-06-12T07:56:04","date_gmt":"2020-06-12T07:56:04","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1907"},"modified":"2022-03-28T00:59:18","modified_gmt":"2022-03-28T00:59:18","slug":"check-sumtree","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/check-sumtree\/","title":{"rendered":"Check SumTree"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

DFS , Recursion<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

"<\/code>A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in the left subtree and right subtree."<\/code><\/p>\n

Given a binary tree and the task is to return true if given binary tree is SumTree else return false.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Starting from root node ,lets say N<\/code> , we will calculate the sum of the node values of left<\/strong> (L<\/code>) & right<\/strong> (R<\/code>) subtrees.
\nIf, N->data = L + R<\/code>, then our tree is the sumtree, else not.<\/p>\n<\/blockquote>\n

Method 1 (Brute Force):<\/h4>\n
\n

We will calculate the the sum of left<\/strong> & right<\/strong> subtree.<\/p>\n

Now, we will compare the value of root<\/strong> node to the left<\/strong> & right<\/strong> subtree.
\nIf the value of root node is equal to the value of left<\/strong> & right<\/strong> sum , then we will return true<\/strong> else false<\/strong>.<\/p>\n

We will do this recursively for our left<\/strong> & right<\/strong> subtree , by calling checkSumtree(root->left)<\/strong> && checkSumtree(root->right)<\/strong><\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Method 2 (Efficient):<\/h4>\n
\n

In the above methode, we are calculating the left<\/strong> & right<\/strong> subtrees for every node.<\/p>\n

We can skip the recalculation of this sum for each subtree, if we take care of the following points:<\/p>\n

    \n
  1. \n

    If the current node is the leaf node , then the sum of the subtrees of this node is equal to the value of the node itself.<\/p>\n<\/li>\n

  2. \n

    If the current node if not a leaf node, then the sum of the subtrees of this node is double<\/strong> the value of the node.
    \n(See C<\/strong> implementation for implementation). <\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n

    Complexity Analysis :<\/h3>\n
    \n

    In brute-force approach, we are calculating the sum for subtree of each node. We can perform sum of the tree in O(n)<\/strong>. Since we are calculating sum for each node so if there are n<\/code> node we are taking O(n2<\/sup>)<\/strong> in total.<\/p>\n<\/blockquote>\n

    Solutions:<\/h3>\n\t\t\t\t\t\t