Binary Search Tree to Greater Sum Tree | Brute | Better | Optimal | Leetcode 1038 | codestorywithMIK
306Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 4th Video of our Playlist "Binary Search Tree : Popular Interview Problems".
We will be solving Leetcode - 1038 -
Binary Search Tree to Greater Sum Tree | Brute Force | Better | Optimal | Leetcode 1038 | codestorywithMIK
Problem Name : Binary Search Tree to Greater Sum Tree | Brute Force | Better | Optimal | Leetcode 1038 | codestorywithMIK
Company Tags : AMAZON
My solutions on Github : https://github.com/MAZHARMIK/Intervie...
Leetcode Link :
https://leetcode.com/problems/binary-...
Approach Summary :
The approach involves converting a Binary Search Tree (BST) into a Greater Sum Tree (GST) where each node's value is updated to the sum of all values greater than or equal to it. This is achieved through a reverse in-order traversal (right-root-left) of the tree. Here's a step-by-step explanation:
Traversal Method (solve):
Base Case: If the current node is null, simply return.
Right Subtree Processing: Recursively process the right subtree to ensure all nodes with greater values are updated first.
Update Current Node: Add the current node's value to the cumulative sum and update the current node's value to this sum.
Left Subtree Processing: Recursively process the left subtree to update nodes with lesser values.
Main Function (bstToGst):
Initialize the cumulative sum to 0.
Call the solve method starting with the root node to transform the BST into a GST.
Return the modified tree's root.
This approach ensures that by the time a node is processed, all nodes with greater values have already been updated, thus maintaining the properties required for the Greater Sum Tree.
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Timelines : ⏰
00:00 - Problem Explanation
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear