Binary Search Tree to Greater Sum Tree | Brute | Better | Optimal | Leetcode 1038 | codestorywithMIK
Вставка
- Опубліковано 27 сер 2024
- Whatsapp Community Link : www.whatsapp.c...
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 : github.com/MAZ...
Leetcode Link :
leetcode.com/p...
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 | Recursi...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
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
Just submitted this problem and your solution popped up!!
I was come up with better brute force sol (O(n) time morris traversal & O(n) space using prefix hashmap), after that by seeing optimal sol explanation, I coded it myself
class Solution:
def bstToGst(self, root: TreeNode) -> TreeNode:
inorder = []
cur = root
while cur:
if not cur.left:
inorder.append(cur.val)
cur = cur.right
else:
prev = cur.left
while prev.right and prev.right != cur:
prev = prev.right
if prev.right == cur:
prev.right = None
inorder.append(cur.val)
cur = cur.right
else:
prev.right = cur
cur = cur.left
mmap = {} # prefix map
mmap[inorder[-1]] = inorder[-1]
for i in range(len(inorder) - 2, -1, -1):
mmap[inorder[i]] = inorder[i] + mmap[inorder[i + 1]]
cur = root
while cur:
if not cur.left:
cur.val = mmap[cur.val]
cur = cur.right
else:
prev = cur.left
while prev.right and prev.right != cur:
prev = prev.right
if not prev.right:
prev.right = cur
cur = cur.left
else:
prev.right = None
cur.val = mmap[cur.val]
cur = cur.right
return root
Love the simplicity in your explanation.
Good explanation 👏 👍
Amazing problem and great explanation
Mera to bruteforce hi accept hogia wo bhi beat 100% se😂
Thanks
Better version of the 2nd solution which got accepted:
Instead of iterating on the inorder array to find the nodes which are greater than the current node, I used prefix sum to store the sum nodes which are smaller than the current node in a unordered map.
Later making the function modular, I found the total sum of all the nodes.
Hence currNode -> val = totalSum - mp[currentNode] where mp[currentNode] is the sum of node values which are smaller than current node. C++ code:
class Solution {
private:
void solve(vector&inorder, int &totalSum, int &finalTotalSum, bool &changingValues, unordered_map&mp, TreeNode* &root){
if(root == NULL) return;
solve(inorder, totalSum, finalTotalSum, changingValues, mp, root -> left);
if(!changingValues){
inorder.push_back(root -> val);
totalSum += root -> val;
}
else{
root -> val = finalTotalSum - mp[root -> val];
}
solve(inorder, totalSum, finalTotalSum, changingValues, mp, root -> right);
}
public:
TreeNode* bstToGst(TreeNode* root) {
vectorinorder;
int totalSum = 0;
int finalTotalSum = 0;
bool changingValues = false;
unordered_mapmp;
solve(inorder, totalSum, finalTotalSum, changingValues, mp, root);
int smallerSum = 0;
mp[inorder[0]] = 0;
for(int i = 1; i < inorder.size(); i++){
smallerSum = smallerSum + inorder[i-1];
mp[inorder[i]] = smallerSum;
}
changingValues = true;
finalTotalSum = totalSum;
solve(inorder, totalSum, finalTotalSum, changingValues, mp, root);
return root;
}
};
yes ,i was also thinking for the same
Bro when I submitted the Brute Force solution in LC it showed 0ms Runtime & beats 100%. SO STRANGE.
MIk boss please bring dp optimization videos
Sir please make video on leetcode 164 maximum gap
please aage se bhaiya saare approcah ka solution github me upload kr djiyega taki hum check kr sake kanhi mistake ho to .
bhaiya aap please 1937. Maximum Number of Points with Cost ye wala question karwa dijiye ...aur logo ne jo smjhaya hai usme itne acche se intution clear nhi ho paa rhi hai ...aap kaafi acche se samjhate ho ...btw thanks bhaiya aapki wajaah se meri leetcode pr 1840 rating ho gyi hai (in just 15 contest) and it just a begining
can you please point to your morris video and iterative solution?
Mark for revision
Morris traversal-O(n)
space-o(1)
class Solution {
public TreeNode bstToGst(TreeNode root) {
int sum = 0;
TreeNode curr = root;
while (curr != null) {
if (curr.right == null) {
sum += curr.val;
curr.val = sum;
curr = curr.left;
} else {
TreeNode succ = curr.right;
while (succ.left != null && succ.left != curr) {
succ = succ.left;
}
if (succ.left == null) {
succ.left = curr;
curr = curr.right;
} else {
succ.left = null;
sum += curr.val;
curr.val = sum;
curr = curr.left;
}
}
}
return root;
}
}
I am not able to understand why are we counting root's value for left nodes. The problem description says, original key plus the sum of all keys greater than the original key in BST.
Example : 6 is a BST with 7,8 (right node) and 5 (left node), so it make sence to add 7+8+6 in replace the sum to 6's value. But 5 is a BST with no left and no right, so the sum should be 5 only. Why are we counting the value of parent in case of 5, 1, 0 (all left node).
Can you please explain.
because in the question it is clearly written to replace the given key by the key and sum of all the greater keys than that key. I think you misunderstood the question
Bhaiya please dp concept shuru krdijiye na
Bhai already channel pe hai
Resume krne ko kaha rha
agar isme apn node 3 ko node 5 se swap kr dete h toh ...it will still be a BST. But leetcode says that this is invalid BST whereas GPT and my knowledge say that this is valid BST. And for this BST your solution won't work. I'm confused ....Help!
Brute Force:O(n^2)
void inOrder(TreeNode* root,vector& inorder)
{
if(root==NULL)
{
return;
}
inOrder(root->left,inorder);
inorder.push_back(root->val);
inOrder(root->right,inorder);
}
void solve(TreeNode* root,vector& inorder)
{
if(!root)
{
return;
}
int sum=0;
for(int idx=inorder.size()-1;idx>=0;idx--)
{
if(inorder[idx]>=root->val)
{
sum+=inorder[idx];
}
else
{
break;
}
}
root->val=sum;
solve(root->left,inorder);
solve(root->right,inorder);
}
TreeNode* convertBST(TreeNode* root) {
vectorinorder;
inOrder(root,inorder);
solve(root,inorder);
return root;
}
Thank you MIK for these amazing videos😊
BETTER mai postfix calculate karke more optimal ho skta hai sir
Niceee
Bhaiya apna bola tha *longest valid parantheses* karwayenge ye important q h bhaiya or ye nhi h yr par ache se... Please bata dijiye
Couldn’t get time due to travel plans. Will soon try in my free times.
If possible, can you share what solution have you tried ?
I will try to improve or suggest over that
Bhaiya multiply two strings pe banao Mai aase Instagram pe bhi message Kiya tha apne reply nhi kiya
Waiting to your code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void solve(TreeNode* root,map&mp,vector&v){
if(!root) return;
solve(root->left,mp,v);
mp[root->val]=root;
v.push_back(root->val);
solve(root->right,mp,v);
}
TreeNode* bstToGst(TreeNode* root) {
mapmp;
vectorv;
solve(root,mp,v);
for(int i=v.size()-2;i>=0;i--){
v[i]+=v[i+1];
}
int i=0;
for(auto it:mp){
it.second->val=v[i];
i++;
}
return root;
}
};
upload slide
Gg ❤
8+7+6=Aekais😂😂
😆❤️
Itne ad😑😑😑😑bhkk😑😑😑😑😑😑😑😑😑
But Video ❤❤
class Solution {
public int subarraySum(int[] nums, int k) {
// Call the helper function with an initial sum of 0
return helper(nums, k, 0);
}
private int helper(int[] nums, int k, int idx) {
if(idx>=nums.length)
{
if(k==0)
{
return 1;
}
return 0;
}
int take=0;
if(nums[idx]
index must always be checked first no matter what
if the other condition is making it out of bound it will be terminated because of the case written below the index base case
@@yashkalia2311 no bro I have seen some problems where the index out of bound is checked after some other base condition depending on the question please check and if you find the answer let me know
@codestorywithMIK bro please help
Kaise kr lete ho yaar mai sochta rah gya but nhi hua mere se😢😢😢