Kth Smallest Element in a BST - Leetcode 230 - Python

0:00 - Drawing Explanation
7:00 - Coding Solution

leetcode 230

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

[airysm]

"While cur and stack" but isnt stack originally empty so that loop shouldnt execute?

[YasirYSR]

It should be "while cur or stack:" for the first while loop

[QuadQuadQuadQuad]

Best leetcode channel on YouTube. Quick, concise, and very useful explanations and visuals.

[yogeshk]

while curr or stack:
this worked for me.

Use or instead of and

[chinmayee]

should be
1. while cur or stack (current while condition will not work)
2. return 0 in the end

[UnknownName]

What would be the answer to the follow up question? 'If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?'

[yilmazbingol]

initially stack=[ ], its bool value is "False". So how come "while cur and stack" is True. cur=root so cur is True, stack is False, True and False returns False. We should never enter into the while loop?

[jrsn]

This code failed in LC. I had to change line 13 to "while True:"

[sniff]

hey. do you think it’s possible to be able to consistently do leetcode hards with practice? i can do easy and a good amount mediums, but hard seems completely way too difficult for me now. are hards generally do-able with practice. or are they “nutcracker” problem? i.e. extremely difficult to solve without guidance.

[Raman]

If you recursively build the inOrder array, you just need to print the k-1th element :)

def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
inOrder = []
def doInOrderDFS(node):
if not node:
return
doInOrderDFS(node.left)
inOrder.append(node.val)
doInOrderDFS(node.right)

doInOrderDFS(root)
return inOrder[k-1]

Amazing channel btw! Really helping me approach these problems systematically

[JelloparrotYT]

change 'and' to 'or', then it works

[Grawlix]

DFS recursive solution is same complexity (time and space). It just needs logN in-memory recursion stack space rather than a logN array to track values.

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
self.res = None
self.k = k
def dfs(node):
if not node or self.res:
return

dfs(node.left)
self.k -= 1
if self.k == 0:
self.res = node.val
dfs(node.right)

dfs(root)
return self.res

[michaelvivirito]

You sound like daily dose of internet. Did you copy some of his mannerisms or is that just how you talk?

[blitzspirit]

Reminder: please add space time complexity guidance.

[DaMavrk]

this was the first Leetcode problem I was able to solve on my own! Going to take a screenshot and save it, lol. Surprisingly I found this to be easy? Thanks neetcode

[celestial]

in the first while loop i chenged the && to || (or) and got the correct answer .
how did && work correctly for you and not for me can anyone explain please??

[varungv]

For DFS I find it easier to use recursion, as the logic becomes easier and cleaner.

[pradgarimella]

I have been following your channel and your content is amazing

[danny]

My recursive solution:

class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:

count = 0
res = -1
def dfs(node):
nonlocal count
nonlocal res

if not node or res != -1:
return None

dfs(node.left)
count += 1
if count == k:
res = node.val
return
dfs(node.right)

dfs(root)

return res

[wrishavbhattacharyya]

We could do it using morris traversal as well . Using O(1) space . I saw one of your videos where you taught this