{"id":1777,"date":"2020-06-11T15:51:37","date_gmt":"2020-06-11T15:51:37","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1777"},"modified":"2022-03-28T01:16:18","modified_gmt":"2022-03-28T01:16:18","slug":"convert-sumtree","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/convert-sumtree\/","title":{"rendered":"Convert SumTree"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

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

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

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

Given a binary tree and the task is to convert that tree into SumTree.<\/p>\n<\/blockquote>\n

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

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

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. In SumTree the leaf node values are always 0<\/code>.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Approach :<\/strong><\/p>\n

\n

We can store the sum of left<\/strong> & right<\/strong> subtree values in the root itselft, but this will result in the loss of the value which is currently stored in the root and we will be needing this value to update the parent node value.
\nSuppose, inorder traversal of our tree is : 1 ,2 ,3<\/code>, now we will store the left<\/strong> & right<\/strong> subtree values (2+3) = 5 in the root node , now the root node value is 5<\/code> which is wrong, the correct answer would be: 2+3+1= 6<\/code>
\nWe need to store the old value (1<\/code>) somewhere before replacing the this value with the new value (5<\/code>), in order to return the answer i.e sum of new and old values. (5+1<\/code>)<\/p>\n<\/blockquote>\n

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

Since we are traversing each node atmost once, the time complexity<\/strong> of this approach is O(n)<\/code>.
\nConsidering the space complexity, the only space it takes is the recursion stack.<\/p>\n<\/blockquote>\n

SOLUTIONS:<\/h3>\n

\t\t\t\t\t\t