Kth Smallest Element in a BST

----------------------------------------------------------------------------------------------------------------
Migos - Bad And Boujee (Kvzmah Lofi Remix)pt. 2 by KVZMAH

[lonelywanderer]

Hey man, wanted to say that your videos helped me a lot. I had an interview for an FB internship and I crammed by watching your videos the day before. Got the news yesterday that I got the internship! I couldn't have done it without you. Hope you keep making these videos and keep improving.

[leomonz]

2:47, I need to learn that skill and show it in the interview, I would be hired in no time

[mierta]

Great video! Only one comment and correct me if I'm wrong: I think the time complexity will always be O(n) since you're not preventing visiting right subtree even when the kth smallest element is already found. It will instead visit the whole tree and only after that the kth smallest element will be returned. We can add a if condition on the right subtree recursive call to only do it when nums[1] < k. That way right subtree will be eliminated on each following stack frames and the time complexity could be brought down to O(H + k)

[saikatpaul]

Cracked Siemens interview for software developer role ...Thank you

[tannerbarcelos]

This problem is easier than a medium however the way it is worded with "kth smallest" i found is a way to throw you off. When in reality, "smallest" is a key thing here. If we need a smallest element, we know inOrder traversal gives us least to greatest in order. Knowing that, this problem is so simple to then just get the k'th value

[venil]

Why would you use nums parameter as return value, when you can actually return it??

[ibrahimmohiuddin]

This got asked on my Cisco SDE intern on campus interview as well last month.

[kumarorlama]

Should not space complexity be the height of the tree instead of O(n) as the recursive function call keeps the stack frame of the deepest level instead of all nodes. At each return frame is pop off stack, memory will be released back.

[umapathybabu]

Nice video. Can you do some oo design questions

[nikhilbhujbal]

What does that if statement condition mean in first position because initials the nums array will be having garbage value so can you please tell tht .

[jayeshborgaonkar]

clear and easy solution, amazing video, would love to see you make some system design videos for beginners thanks

[iamabean]

is the if(++num[0] ==k) will update the value of num[0] and return it to the calling funciton.

[VaradKashmire]

Hey Kevin
Would you solve the below algorithm?

Write an algorithm to count the non zero numbers of an n by n array

[KVZMAH]

Thanks for using my music!! Feel free to use it however you like!

[as_wani]

We can also use a heap of size K right?

[_withoutwax]

Thanks for this amazing video! Great explanation!
I have one question that I didn’t understand fully from your solution:

What does this code mean?
if (++nums[0] == k) {

I am not familiar with Java so perhaps that’s the reason why I am not getting this. Would you be kind and explain that part of the code?

[willturner]

You can also use variable instead of array it will save space, am I right?

[craigslist]

Wouldn't this algo traverse the entire tree even if we find the kth smallest?
For example, find the 1st smallest element in a tree with a billion elements..
Basically this code does not have a short circuit mechanism

[hksubs]

@kevin thanks. 'Kevin's next interview' : do you care to share in some other video or via comments....regarding when you might interview next at a company that tests leetcode. or what firms.

[mohamedamer]

Hey Kevin,
Really love your videos ❤️

I have small adjustment that we can keep the values in the nums array and return if the count == k

here is Swift code for it:

func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
guard let root = root else { return 0 }
var nums = [Int]()

inOrder(root, k, &nums)

return nums[k-1]
}

func inOrder(_ root: TreeNode?, _ k: Int, _ nums: inout [Int]) {
guard let root = root else { return }
inOrder(root.left, k, &nums)
if nums.count == k {
return
}
nums.append(root.val)
inOrder(root.right, k, &nums)
}