Convert BST to Greater Tree - Leetcode 538 - Python

0:00 - Read the problem
1:05 - Drawing Explanation
5:34 - Coding Explanation

leetcode 538

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[dustinscroggins]

Hey man I just want to say thanks for all you do for the community. I landed my dream job at Microsoft and your channel was a big part of me building up my DSA foundations. Everybody out there keep practicing these problems I swear it'll pay off in the long run

[numberonep]

It took me waaay too long to find the solution but for what it is worth, you don't need a tmp variable if you do an assignment:

def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
prev = 0
def dfs(node):
nonlocal prev
if node:
dfs(node.right, )

node.val += prev
prev= node.val

dfs(node.left)
dfs(root)
return root

[wmsbgjq]

Bro I wouldn’t pass all of the assessments to the biggest Tech Company in Russia without your help. Thank you so much, you’re a freakin beast! thank you so much!

[abheykalia]

You could just use : curSum+=node.val
node.val=curSum

[madhumithakolkar_]

Great explanation as always. You don't really need to mention curSum as nonlocal or have a tmp variable actually:
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
curSum = [0]

def dfs(root):
if not root : return

dfs(root.right)
root.val += curSum[0]
curSum[0] = root.val
dfs(root.left)
dfs(root)
return root

[danielsun]

If you want, we could use a list to store the curSum, and modify it in the nested function, Cause it is a shallow copy. And no need to store the tmp.
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
curSum = [0]
def dfs(node):
if not node:
return None
dfs(node.right)
'''
tmp = node.val
node.val += curSum[0]
curSum[0] += tmp
'''
node.val += curSum[0]
curSum[0] = node.val
dfs(node.left)
dfs(root)
return root

[SoupHikes]

We can also Pass the curSum as a member variable in the Constructor initialize part. Then inside DFS we don't need to mention curSum as global variable.

[curimeowcat]

Thanks! Very awesome videos! If you have google code jam tutorial, not just for leetcode, I would definitely join the member channel!

[jarvispotter]

Hi Neetcode, thanks for your amazing explanations. cannot think of solving DSA with out your videos. thanks for making it possible for me. i have a request. is it possible for u to create playlists based on companies ?

[numberonep]

Nice explanation as always! Do you mind doing "307. Range Sum Query - Mutable" or "37. Sudoku Solver" or something about A* someday? It will force me to do them :S i mean you already managed to make me do KMP and the daily leetcode challenges, what is a few more good deeds?

[johnniewalkerjohnniewalker]

you can also solve this problem doing first inorder traversal and using after the technique of prefix sum .Here is my solution in c++
class Solution {
public:
void dfs_inorder(TreeNode* root, vector<int> &v, vector<TreeNode*> &ans){
if (root != NULL){
dfs_inorder(root->left, v, ans);
ans.push_back(root);
v.push_back(root->val);
dfs_inorder(root->right, v, ans);
}

}
TreeNode* convertBST(TreeNode* root) {
if (root == NULL)
return NULL;
vector<TreeNode*> ans;
vector<int> v;
dfs_inorder(root, v, ans);
for (int i=1;i<v.size();i++)
v[i] += v[i-1];
int n = v.size();
if (n==1)
return root;
ans[0]->val = v[n-1];
for (int i=1;i<n;i++){
ans[i]->val = (v[n-1]-v[i-1]);
}
return root;

}
};

[ilirhajrullahu]

Hello Neetcode, thank you for these great videos and your explanation. Could you please share with us what drawing tablet do you use and what software do you use for video editing? Thank you and I am eagerly waiting for your new videos!

[dossymzhankudaibergenov]

Great expleniation, and which app do you use to drawing?

[Od]

God damn so easy but just tricky enough. Thanks for the vid.

[avichai]

hey there NeetCode, love your channel its really bright and understandable!
can you make a video on:
1202. Smallest String With Swaps?
there are coupe of videos on youtube but i didnt quite understand their explanations.

[pushkarchaubey]

Can we make inorder traversal in original tree and stored in an array
After that with prifix logic sum we make another array in sorted manner
And with logic of makin bst with arr we can return new root

[Mukesh-nxtf]

what app do you use to record screen and for white board?

[selfishmango]

Yo which language do you recommend for competitive programming because everyone says pythons not good for that

[kaustubhwaghavkar]

Hey Neetcode, you could also eliminate temp by doing something like this(just carry the updated root.val as currSum for further iterations): Just a suggestion :). BTW, great work!
dfs(root.right)
root.val += currSum
currSum = root.val

[brajagopalmukherjee]

Sir need an explanation of Word break problem on lc