Kth Smallest Element in a BST

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/kth-smal...
0:00 - Drawing Explanation
7:00 - Coding Solution
leetcode 230
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#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?

[@NeetCode]

yeah, sorry about that, it should actually be "or" instead or "and"

[@vijay.pandey]

@@NeetCode do you execute a different code than what you mention in these videos , cause otherwise the code should have failed because of "or" and "and" change.

[@thecuriousengineer]

@@vijay.pandey I think he has already executed code for this particular problem and then re-wrote the code from scratch while explaining the solution :)

[@shubhammishra1225]

I was mulling since 15 min how could this work 😢.

[@ajins777]

@NeetCode Thanks for pinning this. A bunch of print statements inside different levels of the code helped me understand which loop it was not entering :)

[@QuadQuadQuadQuad]

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

[@flogzer0]

I mean, it isn't even the correct answer so I don't know about that

[@YasirYSR]

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

[@prafulparashar9849]

🙏🏻🙏🏻

[@summergreeny4058]

@@prafulparashar9849 hi could you explain why we need to use or? tysm

[@pyllergyjiang5146]

@@summergreeny4058 I guess the stack is an empty array initialy, the while loop won't be excuted by using and.

[@rafeeali8307]

@@summergreeny4058 we use or because what if the kth is on the right subtree of root and we traverse down the left subtree which does not contain a right subtree.

[@wayne4591]

Actually this mistake is worse than just for the while loop. As we set cur = cur.right in the last line of every loop, once cur.right is empty, we will jump out of the loop. This is a really bad mistake to be honest.

[@NeetCode]

Tree Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@pradgarimella]

I have been following your channel and your content is amazing

[@Raman9509]

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

[@dkdlife6210]

This is exactly what I did with this solution :)

[@torin755]

And even better: you don't need a list to store them all, and you certainly don't need to visit every node: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: # in-order traversal -> keep count of visiting in-order -> return when count==k r = root.val def dfs(root): if not root: return dfs(root.left) nonlocal r nonlocal k k-=1 if k == 0: r = root.val return dfs(root.right) dfs(root) return r

[@hanjiang9888]

love your solution

[@wt7658]

excellent solution! I really appreciate the simplicity!

[@ObtecularPk]

In-order traversal , Passing in k to the left and right children. In between the recursive call, you can decrement k. Check if k== 0 (your kth smallest integer in bst) return that or store it in a global

[@Grawlix99]

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

[@bricef0918]

The recursive solution requires visiting every node even after the solution is found and thus is O(n) in the best and worst case. Since the iterative solution returns as soon as k is found, it would only be O(n) in the worst case. If the BST is balanced, then the space complexity is O(logN) as mentioned. However, a BST does not have to be balanced and the worst-case space complexity can be considered O(h), where h is the height of the tree (Consider a BST containing only left nodes).

[@amynguy]

@@bricef0918 no it doesnt? you can just return without going into other nodes.

[@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

[@yogeshk8323]

while curr or stack: this worked for me. Use or instead of and

[@sniff4643]

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.

[@NeetCode]

The people passionate about leetcode, like competitive programmers are able to solve Hards consistently. But i think for the average person studying for interviews, they should only focus on the most popular leetcode hards. Occassionaly, there are problems where you have to simply memorize the "trick" in hard problems.

[@danny65769]

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

[@minciNashu]

thats actually pretty neat. i solved this with a recursive in-order DFS, but I like this solution better

[@swaroopacharjee2767]

It is a great answer. I would like to add my own answer to this thread. We know that inorder traversal of a BST gives an array in ascending order. We can traverse the BST inorder, and store the result in a array. After this we can return (k - 1) index of the of the array. class Solution: def __init__(self): self.node_lst = [] def inorder(self, root:Optional[TreeNode]): if not root: return self.inorder(root.left) self.node_lst.append(root.val) self.inorder(root.right) def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.inorder(root) return self.node_lst[k - 1]

[@avetiqasatryan1540]

disadvantage is that you continue to traverse even if you found kth element

[@ashishm8850]

Excellent! Thanks!

[@UnknownName7950]

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?'

[@ary_21]

What if you use an avl tree or basically convert a bst to avl tree Avl will always ensure the tree is height balanced in nature

[@bricef0918]

My answer would be to ensure that the BST is balanced. The logic is equivalent to that of searching an unsorted array (unbalanced tree) vs searching a sorted array (balanced tree). Finding an element in an unbalanced BST is O(h), where h is the height of the tree. Consider a tree with only left elements and having to find the element at the bottom. If this same tree was balanced, the complexity is now O(logN), where n is the total number of nodes.

[@symbol767]

This is great, thank you man

[@wrishavbhattacharyya5216]

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

[@varungv5402]

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

[@danparis6207]

The only problem with DFS is that you still have to explore the upper nodes even after you've found the kth smallest element. The recursive calls that got you to the bottom of the tree still need to finish. Using the while loop you get right to the bottom of the tree and then only go up as far as you need to.

[@ChristopherLoverich]

@@danparis6207 you can return the node then add an additional check before each recursion. Or you could raise an exception.

[@ChristopherLoverich]

​@Kevin BurgerKing Python's iterator protocol would like a word with you.

[@ChristopherLoverich]

​@Kevin BurgerKing they went great! Now I get to spread the love by dinging interviewees if they don't come up with exception based alternatives to their otherwise great solutions.

[@MrWardo2009]

Thank you for making this video.

[@jair3711]

we could also do an inorder traversal and return the element at (k-1)-th index

[@Peps1Lem0n]

I actually managed to make this simpler and faster using recursive in order traversal: it looks like depth first traversal but if you do the action in between the nodes, it results in a in order traversal. const arr = []; function inOrder(node: TreeNode | null) { if(!node) return; inOrder(node.left); arr.push(node.val); inOrder(node.right); } inOrder(root) return arr[k-1]; (this still is the best channel on youtube for leetcode problems)

[@romo119]

this uses o(n) space

[@blitzspirit]

Reminder: please add space time complexity guidance.

[@trueworth638]

Could you do Combination Sum IV? I am having a tough time grasping that one.

[@kedarnathgubbi]

class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: # need to do iterative INORDER DFS to find the kth smallest element cur = root stack = [root] count = 0 while(stack): # find the leftmost node while cur: stack.append(cur) cur = cur.left # now cur is pointing to null # we process thelast node that we added cur = stack.pop() count += 1 if count==k: return cur.val # check right node cur = cur.right return -1 I felt this is much easier to understand

[@anmoljhamb9024]

For this question, I've personally used the fact that in order traversal of a binary tree, gives us the sorted array. So, we can just get the kth element.

[@akshaychavan5511]

It would have been great if you could answer this 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?"

[@2000daboss]

Small correction: at 9:45 the while loop does execute, but only once, thus adding the current node to the stack but not anything else.

[@yilmazbingol4838]

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?

[@mahamatoumar1963]

Man I am confused too . How did that execute?

[@geekydanish5990]

it should have that in or condition

[@flogzer0]

@@mahamatoumar1963 It didn't. For some weird reason the guy likes to lie about executing the code in the video.

[@sanooosai]

thank you

[@prajjwaldubey5787]

which will be better doing this recursively or iteratively ???

[@AbhayNayak]

for someone wondering whats recursive DFS approach, pls feel free to improve it class Solution: def __init__(self): self.count = 0 self.smallest = 0 def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.count = k self.dfs(root) return self.smallest def dfs(self, root): if root.left: self.dfs(root.left) self.count -= 1 if self.count == 0: self.smallest = root.val if root.right: self.dfs(root.right)

[@SabinBajracharya]

My 3 line solution for this problem class Solution { fun kthSmallest(root: TreeNode?, k: Int): Int { if (root!!.left == null) return (root!!.`val` - 1) + k return kthSmallest(root!!.left, k) } } This works because the testcases in Leetcode doesn't have have gap in between numbers. So you can predict the kth number just by knowing the initial smallest number.

[@daredevil0905]

For 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?", can we keep the count of nodes in the left and right subtrees of a particular node within the node itself? In this case we will traverse the BST looking where the value of k fits in based on this count. So even if we insert/delete nodes, just update this count along the path upwards towards the root and we can just reuse the same process again. In doing so we would not have to traverse the entire tree just to find the kth smallest element right? Can this be the correct approach?

[@JelloparrotYT]

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

[@mattg9601]

Idk how it was submitted on leetcode and it could be due to my low knowlegde of python however the code you put on screen would cause an error when the left most node doesn't have a right node. As it was set it to right and then check the loopguard which would see curr as null.

[@prog5724]

same idea with better readability def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: n = 0 stack = [] cur = root while cur: stack.append(cur) cur = cur.left while k!= 0: node = stack.pop() k -= 1 if k == 0: return node.val right = node.right while right: stack.append(right) right= right.left return -1

[@roopchandjangir6862]

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: curr=root n=0 stack=[] while True: while curr: stack.append(curr) curr=curr.left m=stack.pop() #print(m.val,end="->") n+=1 if n==k: return m.val curr=m.right return -1

[@jrsn]

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

[@jrsn]

or change it to "while cur or stack:". How did your test passed? With logical-and, it won't even go in to the while-loop given that the stack is initially empty.

[@fishoil5310]

@@jrsn he mistakenly use the AND operator, this should be an OR

[@NeetCode]

Yeah, it should be logic OR, sorry about that. But good question, i have no idea how it passed in the video, it might have used previously cached code that i wrote before recording.

[@tanayshah275]

@@NeetCode can you write that in your pinned comment so others can quickly notice it.

[@primetimetran]

My guess is LeetCode realized their example didn't account for an edge case which runs and updated to add a new "hidden" test case. Just a guess though

[@tonyzhang1612]

Could you also provide any insights into the follow-up question to this one? Thanks! "Follow up: 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?"

[@TanishBansal-ss2ou]

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: s = [] while s or root: if root: s.append(root) root = root.left else: root = s.pop() k -= 1 if k == 0: return root.val root = root.right

[@chinmayee95]

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

[@souravehossain1288]

Not sure if this is good or bad but if It's a BST then inorder traversal will always give us values in ascending order. if we store the values in a list and then just return K-1th index (as in the problem it says 1-indexed), we should get the Kth smallest value. Here's the code: ``` def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: values = [] def dfs(root: TreeNode) -> None: if not root: return dfs(root.left) values.append(root.val) dfs(root.right) dfs(root) return values[k-1] ```

[@dk20can86]

It's a good exercise to go through, but this iterative solution is also O(logn) space complexity so theres no real advantage to the more complex iterative code.

[@marlosison3932]

You can also count the nodes in order. Once you reach k you stop.

[@celestial2091]

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??

[@juliuscecilia6005]

same

[@tesszheng4586]

another solution: we can traverse the tree using InOrder, then the result will be a sorted array, then we can return the [k-1] element of the array class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: # Traverse tree using InOrder, result will be a sorted array # idx: k-1 element of the array is the result res = [] def dfs(root): if not root: return dfs(root.left) res.append(root.val) dfs(root.right) dfs(root) return res[k-1]

[@mengdizheng1223]

shouldn't that while cur and stack be while cur "or" stack ? stack initialised as [] won't enter that while like this . thanks so much this explains in order traversal on BST well

[@edwardteach2]

U a God

[@iamburntout]

Thanks. You save me from going mad

[@Xeoncross]

The first part of this video (until 3:00) didn't make sense because this is a BST so the first element should be the root (3) just like shown on the "Input:". That is, each left child is array[index * 2]

[@midhileshmomidi3120]

what is the time complexity of this code class Solution: res,count = -1,0 def inorder(self,root,k): if not root: return self.inorder(root.left,k) self.count += 1 if self.count == k: self.res = root.val return None self.inorder(root.right,k) def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.inorder(root,k) return self.res

[@flocela]

Neet code, nice name. : )

[@darshitdesai]

How to solve this? Follow up: 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?

[@dthnick]

you got a different code on your website then in the video:)

[@baap6886]

best for python developers

[@shuvadiproy5154]

Is Iterative DFS is more efficient than recursive DFS ?? Why you are using Iterative dfs here ?? Please reply🙏🙏🙏

[@rahulchittora23]

# Easiest one. keep traversing left. add val and then go right class Solution: def kthSmallest(self, root, k: int) -> int: res = [] def inorderTraversal(root): if root is None : return None inorderTraversal(root.left) res.append(root.val) inorderTraversal(root.right) inorderTraversal(root) return res[k-1]

[@danielsun716]

res = root.val def dfs(node): if not node: return None dfs(node.left) nonlocal k, res k -= 1 if k == 0: res = node.val return res dfs(node.right) dfs(root) return res

[@sricodes]

Anyone know what the runtime of this problem is? Would it be O(n)?

[@alirezaaramoun615]

`while` condition states that stack should not be empty but at the first iteration stack is empty. So, it will never enter the loop. Moreover, I don't know why you are using `and` instead of `or`. This is the implementation in c++, I had to push the first element twice. how can I avoid it? ``` int kthSmallest(TreeNode* root, int k) { stack v; int n =0; auto curr = root; v.push(curr); while (curr || !v.empty()) { while (curr) { v.push(curr); curr = curr->left; } curr = v.top(); v.pop(); n+=1; if(n==k) return curr->val; if(curr) curr = curr->right; } return 0; } ```

[@akshaychavan5511]

My recursive and iterative solutions - # iterative inorder traversal - Beats 50% def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: stack = [root] current = root cnt = 0 while len(stack)>0: if current and current.left: stack.append(current.left) current = current.left else: popped = stack.pop() cnt+=1 if cnt == k: return popped.val if popped.right: stack.append(popped.right) current = popped.right return -1 # recursive inorder traversal - Beats 99% def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.cnt = 0 self.res = None def inorder(root): if not root: return inorder(root.left) self.cnt+=1 if self.cnt == k: self.res = root.val inorder(root.right) inorder(root) return self.res

[@limzhengyang7364]

pls correct me if i am wrong, but we essentially do not even have to check while current or stack we just have to check while stack; because as long as stack is not empty, we want the while loop to keep going

[@ChristopherLoverich]

You need both checks because you need the first loop case to have curr already set so it descends fully down the left branch. Iterative binary treee traversal is trickier than recursive.

[@pushpendrapratapsingh4852]

yes we only have to check while stack. however in this code implementation stack is initially empty so to start the while loop cur or stack is required

[@sarthakjain1824]

I just calculated the inorder

[@EranM]

using a stack is over kill.. just travel inorder, and set k = k - 1. When k == 0 it's the correct value

[@samarthkaran2314]

Can we achieve this without extra space ?

[@YasirYSR]

what is the complexity of this Algorithm???

[@JasonKim1]

Average case: you traverse to the bottom left of the tree of height log(n) where n is the number of the nodes. So O(log(n) + k) ~= O(log(n)) where k is the input param. Best case: k = 1. Still O(log(n)), as you have to go to bottom left of the tree. Worst case: If the tree is a long left biased tree, it'll be O(n).

[@jacobhelwig815]

@8:39 How do I get Python to make the pop sound effect when popping from a list?

[@crawbug8932]

Since there's guaranteed to be at least k elements, the "while cur or stack" part is unnecessary. You can make the solution a little simpler by replacing it with "while True".

[@yalebass]

here is a recursive solution in javascript: var kthSmallest = function(root, k) { // place in order, return(k - 1)th index return inOrder(root)[k - 1]; }; var inOrder = (root) => { if (root === null) { return []; } if (root.left === null && root.right === null) { return [root.val]; } return inOrder(root.left).concat(root.val).concat(inOrder(root.right)); };

[@ai-sakib]

DFS solution (JavaScript): var kthSmallest = function(root, k) { let smallestElement const dfs = (node) => { if (!node) { return } dfs(node.left) k-- if (k === 0) { smallestElement = node.val } dfs(node.right) } dfs(root) return smallestElement };

[@Subhash1995]

Recursive approach with O(1) space class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: counter = 0 ans = 0 def dfs(root): nonlocal counter nonlocal ans if not root: return dfs(root.left) counter+=1 if counter == k: ans = root.val dfs(root.right) dfs(root) return ans

[@rvarun7777]

Easier! def inorder(root): if root is None: return [] in_left = inorder(root.left) in_right = inorder(root.right) root_val = [root.val] return in_left + root_val + in_right return inorder(root)[k-1]

[@JasonKim1]

Neetcode mentioned that he'll show an iterative solution instead of a recursive one.

[@mohamedhassan-ub4kj]

while satck 'or' cur not 'and'

[@saadkatarkatar7568]

it is while curr OR stack: not curr and stack

[@rahuldey1182]

After seeing this question the quick solution that came to my mind was lets do it BFS - level order traversal to get the value of each node in a list. Then we will sort the list and get the kth smallest element. But the downside was the time complexity becomes O(NlogN). Neetcode's solution does it in O(N), so it can be considered for the explanation in the interviews. Posting my solution here: class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: # BFS - Level Order Traversal - O(NlogN), O(N) nodes = [] q = collections.deque([root]) while q: node = q.popleft() if node: nodes.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return sorted(nodes)[k-1]

[@yohanma8341]

I was thinking also storing each node in a list, but instead of sorting the list, I build a minHeap from that list and get the k smallest element. Where time complexity is still O(n), and space complexity is also O(n), not sure if space complexity can be improved anymore than that

[@khanaftab3852]

use "and"instead of "or" in while loop

[@ShikshaMishraMTCS]

Hi can you solve this question using Heap???

[@abdullahshahid9051]

Yeah sure, but then you are not utilizing the fact that it's a BST. You are treating it an unsorted array

[@sreet2841]

This solution beats 77%, much better one var kthSmallest = function(root, k) { console.log(root); const stack = []; let counter = 0, kthSmallest = 0; function bfs(root){ if(!root){ return; } bfs(root.left); if(++counter === k){ kthSmallest = root.val; return; } stack.push(root.val); bfs(root.right); } bfs(root); return kthSmallest; };

[@shatakshisharma8557]

while cur or stack:

[@navaneethmkrishnan6374]

Why is this problem medium?

[@dumbfailurekms]

to boost confidence before we fail interview

[@tvkrishna71]

Very "neet"!

[@relaxmug2263]

"while cur or stack" instead while cur and stack at start stack is empty!! "and" will not work.

[@AlbtzGaming]

In first while loop it should be OR not AND!!!

[@shareefdweikatps]

The solution won't work for all cases. You need to replace and with or in the first while condition

[@adarshkv4616]

At starting stack is empty right But we are writing while curr and stack: How it's going inside while loop Can anyone clarify this

[@qqqqoeewqwer]

"while curr or stack" should be correct! I have no idea why it works in video

[@shribhamare]

This code is giving error.

[@edithpuclla6188]

With an "and" in the while it will never enter into the loop, so we should change it for an "or" -> while curr or stack:

[@shribhamare]

@@edithpuclla6188 Thanks! :) I figured it out.

[@msugal]

I think this problem should be market easy. Also, no need for extra space. You can have a variable and count each node. If count == k: return root.val.

[@michaelvivirito]

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

[@abdullahalmahfuj7623]

May be most confusing tutorial I have even watched your videos. Sorry