Range Sum of BST

[@preethiraajaratnam6399]

Hey Kevin, your videos are really helpful with interview prep! For this question, I felt an in-order traversal within the bounds L & R to be more intuitive than a BFS, just because it takes advantage of the fact that the tree is a BST.

[@asimansubera960]

Hello Kevin, Hope you are doing well! I am following your all LeetCode interview videos. Thank you for helping and educating me with your ideas and thought process solving each problem. These are very helpful.I would like to have a different video(s) from you with a holistic view of any interview question covering following aspects: 1. how you approach any problem 2. when to use Queue vs stack vs hashmap vs hashset vs arraylist, linkedlist, iterative vs recursion vs DP etc. 3. when to use one data structure vs multiple data structures 4. When to use an additional tracking data structure 5. when to use binary search when question is not about search though 6. when to use two indexes from both end of array I know it would be difficult to cover everything in a single video. You may create series of videos on this. Thanks in advance! -AB

[@gideonkibetcheruiyot7500]

your music is my favorite part of your videos, Kevin. Keep up the great work.

[@KevinNaughtonJr]

Gideon Kibet Cheruiyot thanks Gideon I really appreciate it!

[@jasonfong2582]

Any idea what the music is? Seems familiar

[@crimsoncad3230]

Why can't we use Tree traversal algorithm like in-order traversal which will travel all the nodes ???

[@ayushkashyap8299]

because there is a more efficient way of doing this. In which we don't have to traverse all nodes

[@AnshumanKumar007]

@@ayushkashyap8299 we don't need to. We can check root.left if current.left > L and don't do it if it's not. We can do the same for root.right

[@Tlacoyo59a]

I agree

[@perpendicular355]

@@Tlacoyo59a Space complexity would be O(N) in case we do recursive in order traversal.

[@gerryramosftw]

amazing bro, really appreciate this video. will be watching more and probably all! glad I found your channel

[@KevinNaughtonJr]

Anytime and thanks Gerard I appreciate the support!

[@stevenanthony4094]

Hey Kevin, just wanted to say a quick thank you, your simple explanations have helped me tremendously.

[@anushree3744]

Did not get why we didn't opt for DFS but BFS....

[@leanobajio]

The choice is arbitrary. I would have used DFS since it doesn't need a queue to implement, so it uses less space.

[@anushree3744]

@@leanobajio exactly

[@KevinNaughtonJr]

You can use either but bfs avoids using recursion which I think generally scales better (with dfs if you have a really large tree, you could run into a stack overflow)

[@KevinNaughtonJr]

Dean careful because dfs still uses extra space because of the recursive calls on the stack!

[@leanobajio]

@@KevinNaughtonJr Oh yeah! I completely forgot about that.

[@satrap299792458]

Your music playlist is dope

[@shivamsachan5109]

can you explain the initialization of queue? (TreeNode & LinkedList)

[@KevinNaughtonJr]

SHIVAM SACHAN we wanted to make sure we store tree nodes in our queue so that inside our while loop we can have references to the current node’s children (we couldn’t do that if we stored something like integers in our queue) and linked list is just how you initialize queues in java (under the hood a queue is just a linked list with certain properties/abilities)

[@lizdenhup]

Thank you for making such an awesome video!! So clear! One question --why are you not making the condition on lines 24 and 27 greater than or equal to/less than or equal to, if the range is inclusive? Thanks. :)

[@bhanuarora4504]

can we solve this problem in O(logN)?

[@aditya234567]

Nice but what's the point in tree being binary search tree. Interviewer would expect you to use that property!

[@saurabhprasad2295]

Queue queue1 = new LinkedList(); The compiler saying.... its not declared in the scope.... please help....

[@madiyar8079]

More DP please!

[@KevinNaughtonJr]

Madiyar Kaskabayev you got it! I’ll try to do more dp problems thanks for the input!

[@mdzikrullah9575]

Thank you for this video

[@AmolGautam]

Thank you so much for the videos.

[@hichemrehouma5616]

Hey Kevin! Loving your videos! I just got off an onsite with Amazon and wanted to share a problem that I thought would be a good addition to your list. The problem says you have a list of arrays with 2 elements each, with first element being the name of the commander of the second element. Return a list with the names ordered by their rank from highest ranking to lowest ranking. I actually struggled a lot haha Lemme know your thoughts!

[@ijaz2020]

this is called topological sorting. google about it.

[@naveenrawat6278]

Topological sort does the trick.

[@TonyDiCroce]

I'm curious why you didn't do an in order traversal? Then you could at least stop once Val is greater than R?

[@MrSriravi]

Hey Kevin, thanks for your videos.Could you do a video on this problem "Permutation in String" LC-567.

[@PatrickFong]

why do you check the current val of the TreeNode, before you add the left and right nodes? Shouldn't you check the left / right node that they are within the range?

[@shaanyahoo]

why not DFS ?

[@alexeydeynega7603]

Can we use the information that this is binary search tree, and not just an arbitrary tree ? Maybe, this information will allow us to minimize number of nodes to be checked if we solve it recursively (not bfs)

[@atift5465]

Nice result and explanation! This is one of those fun problems that I found

[@KevinNaughtonJr]

atif tirmizi thanks Atif as always I appreciate the support!

[@contact2ck]

Kevin kindly explain 489. Robot Room Cleaner. Leetcode problem

[@iloveallparties]

What does the average software engineering interview look like outside of companies like amazon, google, fb, etc? Do they all ask Leetcode?

[@prageeth4855]

For mobile dev positions specially 1. Ask to do a take home assignment or 2. Live coding of a component of an app.

[@AndroidJames91]

To add to the mobile dev position interviews, I just finished about 10 of them. Steps: 1. Usually a recruiter call to determine if you have the buzz words they want for the position 2. I'm seeing a lot of discussion with hiring manager or a lead engineer for the team in this step. Usually asking you to describe projects, work experience, how you work with others, difficult bugs you've solved, and to get a feel for what you're looking for tech stack/team wise and if you can speak the technical jargon. 3. 1:1 technical screen with an engineer. These were usually LeetCode easy questions OR paired coding exercise on an Android app OR take home coding test (Usually about four hours of time investment required) and a one hour discussion with an engineer to discuss decisions made. 4. On-site, which is about 3-5 hours depending on company. Technical round with design questions, technical round with algorithms questions, and cultural fit. Might also have a group round with engineers on the team to do an informal discussion/walkthrough through designing a component/feature for the app. Most companies won't ask you LeetCode hards like top companies will, but they will ask Easy to Medium level LC questions. They'll test your design skills, any knowledge that is necessary to do the job (mobile, for instance), and team fit. Source: I worked at Amazon for over three years and participated in the process of interviewing candidates. I've also done a number of technical interviews in the last four months. The process described may vary for more junior positions as I was interviewing for mid to senior level roles.

[@saurabhprasad2295]

superb man.... "You are the man"!!!!

[@KevinNaughtonJr]

thanks Saurabh!!!

[@ashishkmr]

Nice video, can you make more videos on leetcode hard/medium problems.

[@KevinNaughtonJr]

ashish kumar thanks Ashish and yes I’ll see what I can do!

[@nishadkumar7322]

+Kevin Naughton Jr. Could you please showcase problem # 1248 on LC (Count Number of Nice Subarrays) when you find time?? Thanks man.

[@rahulsinghai3033]

Please solve some DP problem. I like your explanation

[@KevinNaughtonJr]

rahul singhai thanks Rahul and you got it!

[@jsxica3751]

The videos that go over this in Python aren't as high quality as yours, any chance you will do some of these in Python?

[@pawlstothewall]

I wrote a recursive solution in python just now (where node is the root node). Any constructive criticism appreciated. def range_sum_bst(node, mini, maxi): if not node: return 0 if mini

[@sanchitjain9745]

Nice explanation... :)

[@kmdr]

Hey Kevin, why don't we check these two conditions when adding the left and right child to the queue: 1. current.val < L 2. current.val > R ?

[@JohnLee-ob3fo]

Definition of BST (Binary Search Tree) The left subtree of a node contains only nodes with keys lesser than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. The left and right subtree each must also be a binary search tree.

[@abhishekverma5928]

Hey kevin, Thanks for your channel.It is really helpful. I have 1 doubt while adding left or right node in Queue you wrote if(current.left != null && current.val > L){ queue.add(current.left) } I think it should be current.left.val if(current.left != null && current.left.val >= L){ queue.add(current.left) } Also don't we need to check the upper bound condition also if(current.left != null && current.left.val >= L && current.left.val in case if Tree root node is start with 50, then we need to look both L and R in Tree's left and right node. Please correct me if I am wrong anywhere.

[@sarveshchavan4391]

I live ur videos but just a suggestion if u can explain with diagram it will be really good!

[@KevinNaughtonJr]

sarvesh chavan thanks Sarvesh! Diagrams can be tricky but I’ll see what I can do!

[@fridaytechtalk2452]

Recursive Solution: public int rangeSumBST(TreeNode root, int L, int R) { if (root == null) return 0; if (root.val < L) return rangeSumBST(root.right, L, R); if (root.val > R) return rangeSumBST(root.left, L, R); return root.val + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R); }

[@Ajayhanand]

I guess this needs segement trees

[@Ajayhanand]

oh sorry i read it as an array range sum query

[@prakad97]

Hi Kevin, A video suggestion Leetcode #273 Number to Words..pls do if possible

[@tlj77]

public int rangeSumBST(TreeNode root, int L, int R){ int res = 0; if(root==null) return 0; if(root.valR) return rangeSumBST(root.left); res+=root.val; return rangeSumBST(root.right)+rangeSumBST(root.left)+res; }

[@prageeth4855]

Tks Kevin! 💯 Love to do a mock interview with u 😊

[@KevinNaughtonJr]

Prageeth Kumara anytime Prageeth! If you’re interested in a mock interview check out my Patreon page! The link is in the description!

[@abhaytiwari6411]

hey kevin 83 number like is done my me

[@marcgarcia3131]

Hi Kevin, I have a tech interview for Google slated for the second week of December and would _love_ to pick your brain. I saw the Patreon link, so I'm just writing to get your attention and response, thanks! :)