Kth Smallest Element in a BST - Leetcode 230 - Python

  Рет қаралды 179,664

NeetCode

NeetCode

Күн бұрын

Пікірлер: 161
@airysm
@airysm 3 жыл бұрын
"While cur and stack" but isnt stack originally empty so that loop shouldnt execute?
@NeetCode
@NeetCode 3 жыл бұрын
yeah, sorry about that, it should actually be "or" instead or "and"
@vijay.pandey
@vijay.pandey 2 жыл бұрын
@@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
@thecuriousengineer 2 жыл бұрын
@@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
@shubhammishra1225 2 жыл бұрын
I was mulling since 15 min how could this work 😢.
@ajins777
@ajins777 2 жыл бұрын
@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
@QuadQuadQuadQuad 3 жыл бұрын
Best leetcode channel on KZbin. Quick, concise, and very useful explanations and visuals.
@flogzer0
@flogzer0 Жыл бұрын
I mean, it isn't even the correct answer so I don't know about that
@NeetCode
@NeetCode 3 жыл бұрын
Tree Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s
@swaroopacharjee2767
@swaroopacharjee2767 2 жыл бұрын
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
@avetiqasatryan1540 2 жыл бұрын
disadvantage is that you continue to traverse even if you found kth element
@YasirYSR
@YasirYSR 2 жыл бұрын
It should be "while cur or stack:" for the first while loop
@prafulparashar9849
@prafulparashar9849 2 жыл бұрын
🙏🏻🙏🏻
@summergreeny4058
@summergreeny4058 2 жыл бұрын
@@prafulparashar9849 hi could you explain why we need to use or? tysm
@pyllergyjiang5146
@pyllergyjiang5146 2 жыл бұрын
@@summergreeny4058 I guess the stack is an empty array initialy, the while loop won't be excuted by using and.
@rafeeali8307
@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
@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.
@Raman9509
@Raman9509 2 жыл бұрын
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
@dkdlife6210 2 жыл бұрын
This is exactly what I did with this solution :)
@torin755
@torin755 2 жыл бұрын
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
@hanjiang9888 Жыл бұрын
love your solution
@quirkyquester
@quirkyquester Ай бұрын
10 mins explained iterative dfs, bro, you killing it! watched this multiple times, really helpful for me to understand it step by step!
@ObtecularPk
@ObtecularPk 2 жыл бұрын
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
@UnknownName7950
@UnknownName7950 2 жыл бұрын
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
@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
@bricef0918 10 ай бұрын
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.
@DaMavrk
@DaMavrk 10 ай бұрын
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
@Peps1Lem0n
@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
@romo119 Жыл бұрын
this uses o(n) space
@Grawlix99
@Grawlix99 2 жыл бұрын
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
@bricef0918 10 ай бұрын
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
@amynguy 4 ай бұрын
@@bricef0918 no it doesnt? you can just return without going into other nodes.
@studyaccount794
@studyaccount794 2 ай бұрын
@@bricef0918 Even this solution shared in video will visit node first add them to the stack and then return the answer. At least all the left element. So, for a BST with all elements on the left we will need to add all of them. Or when we're finding the right most element we will visit all the elements. So space will be O(N) and TC will be O(N) as well in the worst case.
@yogeshk8323
@yogeshk8323 Жыл бұрын
while curr or stack: this worked for me. Use or instead of and
@varungv5402
@varungv5402 3 жыл бұрын
For DFS I find it easier to use recursion, as the logic becomes easier and cleaner.
@danparis6207
@danparis6207 3 жыл бұрын
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
@ChristopherLoverich 2 жыл бұрын
@@danparis6207 you can return the node then add an additional check before each recursion. Or you could raise an exception.
@ChristopherLoverich
@ChristopherLoverich 2 жыл бұрын
​@Kevin BurgerKing Python's iterator protocol would like a word with you.
@ChristopherLoverich
@ChristopherLoverich 2 жыл бұрын
​@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.
@danny65769
@danny65769 8 ай бұрын
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
@chinmayee95
@chinmayee95 4 ай бұрын
should be 1. while cur or stack (current while condition will not work) 2. return 0 in the end
@kedarnathgubbi
@kedarnathgubbi 8 ай бұрын
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
@minciNashu
@minciNashu 2 жыл бұрын
thats actually pretty neat. i solved this with a recursive in-order DFS, but I like this solution better
@NightHawkX
@NightHawkX Ай бұрын
Glad to have found this channel !
@AbhayNayak
@AbhayNayak 2 жыл бұрын
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)
@jair3711
@jair3711 2 жыл бұрын
we could also do an inorder traversal and return the element at (k-1)-th index
@blitzspirit
@blitzspirit Жыл бұрын
Reminder: please add space time complexity guidance.
@wrishavbhattacharyya5216
@wrishavbhattacharyya5216 2 жыл бұрын
We could do it using morris traversal as well . Using O(1) space . I saw one of your videos where you taught this
@SabinBajracharya
@SabinBajracharya 2 жыл бұрын
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.
@sniff4643
@sniff4643 3 жыл бұрын
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
@NeetCode 3 жыл бұрын
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.
@souravehossain1288
@souravehossain1288 8 ай бұрын
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] ```
@anmoljhamb9024
@anmoljhamb9024 5 ай бұрын
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.
@tonysfortune
@tonysfortune 6 ай бұрын
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?"
@daredevil0905
@daredevil0905 11 ай бұрын
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?
@yilmazbingol4838
@yilmazbingol4838 3 жыл бұрын
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
@mahamatoumar1963 2 жыл бұрын
Man I am confused too . How did that execute?
@geekydanish5990
@geekydanish5990 2 жыл бұрын
it should have that in or condition
@flogzer0
@flogzer0 Жыл бұрын
@@mahamatoumar1963 It didn't. For some weird reason the guy likes to lie about executing the code in the video.
@tesszheng4586
@tesszheng4586 4 ай бұрын
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]
@pradgarimella
@pradgarimella 3 жыл бұрын
I have been following your channel and your content is amazing
@2000daboss
@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.
@roopchandjangir6862
@roopchandjangir6862 2 жыл бұрын
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
@TanishBansal-ss2ou
@TanishBansal-ss2ou 6 ай бұрын
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
@prog5724
@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
@akshaychavan5511
@akshaychavan5511 5 ай бұрын
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?"
@Markcarleous1903
@Markcarleous1903 3 ай бұрын
same looking for that answer can we do it in less than O(N)?
@rahulchittora23
@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]
@dk20can86
@dk20can86 2 жыл бұрын
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.
@JelloparrotYT
@JelloparrotYT 3 жыл бұрын
change 'and' to 'or', then it works
@marlosison3932
@marlosison3932 Жыл бұрын
You can also count the nodes in order. Once you reach k you stop.
@rahuldey1182
@rahuldey1182 2 жыл бұрын
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
@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
@prajjwaldubey5787
@prajjwaldubey5787 Жыл бұрын
which will be better doing this recursively or iteratively ???
@danielsun716
@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
@wt7658
@wt7658 3 жыл бұрын
excellent solution! I really appreciate the simplicity!
@Xeoncross
@Xeoncross 2 жыл бұрын
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]
@darshitdesai
@darshitdesai 9 ай бұрын
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?
@akshaychavan5511
@akshaychavan5511 5 ай бұрын
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
@midhileshmomidi3120
@midhileshmomidi3120 2 жыл бұрын
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
@jrsn
@jrsn 3 жыл бұрын
This code failed in LC. I had to change line 13 to "while True:"
@jrsn
@jrsn 3 жыл бұрын
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
@fishoil5310 3 жыл бұрын
@@jrsn he mistakenly use the AND operator, this should be an OR
@NeetCode
@NeetCode 3 жыл бұрын
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
@tanayshah275 3 жыл бұрын
@@NeetCode can you write that in your pinned comment so others can quickly notice it.
@primetimetran
@primetimetran 2 жыл бұрын
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
@MrWardo2009
@MrWardo2009 11 ай бұрын
Thank you for making this video.
@EranM
@EranM 5 ай бұрын
using a stack is over kill.. just travel inorder, and set k = k - 1. When k == 0 it's the correct value
@ai-sakib
@ai-sakib 6 ай бұрын
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 };
@shuvadiproy5154
@shuvadiproy5154 7 ай бұрын
Is Iterative DFS is more efficient than recursive DFS ?? Why you are using Iterative dfs here ?? Please reply🙏🙏🙏
@ashishm8850
@ashishm8850 3 жыл бұрын
Excellent! Thanks!
@yalebass
@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)); };
@crawbug8932
@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".
@symbol767
@symbol767 2 жыл бұрын
This is great, thank you man
@mengdizheng1223
@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
@Subhash1995
@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
@studyaccount794
@studyaccount794 2 ай бұрын
It's not O(1). It uses stack.
@DiaaHaresYusf
@DiaaHaresYusf Жыл бұрын
while satck 'or' cur not 'and'
@alirezaaramoun615
@alirezaaramoun615 8 ай бұрын
`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; } ```
@trueworth638
@trueworth638 3 жыл бұрын
Could you do Combination Sum IV? I am having a tough time grasping that one.
@mattg9601
@mattg9601 2 жыл бұрын
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.
@celestial2091
@celestial2091 3 жыл бұрын
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
@juliuscecilia6005 2 жыл бұрын
same
@sanooosai
@sanooosai 2 жыл бұрын
thank you
@iamburntout
@iamburntout 9 ай бұрын
Thanks. You save me from going mad
@rvarun7777
@rvarun7777 3 жыл бұрын
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
@JasonKim1 2 жыл бұрын
Neetcode mentioned that he'll show an iterative solution instead of a recursive one.
@dthnick
@dthnick Жыл бұрын
you got a different code on your website then in the video:)
@baap6886
@baap6886 2 жыл бұрын
best for python developers
@YasirYSR
@YasirYSR 2 жыл бұрын
what is the complexity of this Algorithm???
@JasonKim1
@JasonKim1 2 жыл бұрын
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).
@sarthakjain1824
@sarthakjain1824 Жыл бұрын
I just calculated the inorder
@saadkatarkatar7568
@saadkatarkatar7568 2 жыл бұрын
it is while curr OR stack: not curr and stack
@khanaftab3852
@khanaftab3852 9 ай бұрын
use "and"instead of "or" in while loop
@limzhengyang7364
@limzhengyang7364 3 жыл бұрын
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
@ChristopherLoverich 2 жыл бұрын
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
@pushpendrapratapsingh4852 2 жыл бұрын
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
@samarthkaran2314
@samarthkaran2314 2 жыл бұрын
Can we achieve this without extra space ?
@edwardteach2
@edwardteach2 5 ай бұрын
U a God
@flocela
@flocela 5 ай бұрын
Neet code, nice name. : )
@shatakshisharma8557
@shatakshisharma8557 9 ай бұрын
while cur or stack:
@sreet2841
@sreet2841 2 жыл бұрын
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; };
@sricodes
@sricodes 10 ай бұрын
Anyone know what the runtime of this problem is? Would it be O(n)?
@ShikshaMishraMTCS
@ShikshaMishraMTCS 2 жыл бұрын
Hi can you solve this question using Heap???
@abdullahshahid9051
@abdullahshahid9051 2 жыл бұрын
Yeah sure, but then you are not utilizing the fact that it's a BST. You are treating it an unsorted array
@relaxmug2263
@relaxmug2263 5 ай бұрын
"while cur or stack" instead while cur and stack at start stack is empty!! "and" will not work.
@navaneethmkrishnan6374
@navaneethmkrishnan6374 Жыл бұрын
Why is this problem medium?
@dumbfailurekms
@dumbfailurekms Жыл бұрын
to boost confidence before we fail interview
@msugal
@msugal 2 жыл бұрын
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
@michaelvivirito 7 ай бұрын
You sound like daily dose of internet. Did you copy some of his mannerisms or is that just how you talk?
@AlbtzGaming
@AlbtzGaming Жыл бұрын
In first while loop it should be OR not AND!!!
@georgerussel
@georgerussel 3 ай бұрын
Recursive solution MUCH easier
@shareefdweikatps
@shareefdweikatps Жыл бұрын
The solution won't work for all cases. You need to replace and with or in the first while condition
@tvkrishna71
@tvkrishna71 2 жыл бұрын
Very "neet"!
@shribhamare
@shribhamare 2 жыл бұрын
This code is giving error.
@edithpuclla6188
@edithpuclla6188 2 жыл бұрын
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
@shribhamare 2 жыл бұрын
@@edithpuclla6188 Thanks! :) I figured it out.
@jacobhelwig815
@jacobhelwig815 11 ай бұрын
@8:39 How do I get Python to make the pop sound effect when popping from a list?
@adarshkv4616
@adarshkv4616 3 жыл бұрын
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
@qqqqoeewqwer 3 жыл бұрын
"while curr or stack" should be correct! I have no idea why it works in video
@abdullahalmahfuj7623
@abdullahalmahfuj7623 Жыл бұрын
May be most confusing tutorial I have even watched your videos. Sorry
Making an Algorithm Faster
30:08
NeetCodeIO
Рет қаралды 140 М.
Binary Search Tree Iterator - Leetcode 173 - Python
12:47
NeetCode
Рет қаралды 41 М.
бабл ти гель для душа // Eva mash
01:00
EVA mash
Рет қаралды 8 МЛН
HELP!!!
00:46
Natan por Aí
Рет қаралды 50 МЛН
World’s strongest WOMAN vs regular GIRLS
00:56
A4
Рет қаралды 27 МЛН
Kth Smallest Element in a BST - Leetcode 230 - Trees (Python)
7:45
Kth Smallest Element in a BST | Leetcode #230
13:07
Techdose
Рет қаралды 47 М.
Delete Node in a BST - Leetcode 450 - Python
12:59
NeetCodeIO
Рет қаралды 46 М.
Software Engineering Job Interview - Full Mock Interview
1:14:29
freeCodeCamp.org
Рет қаралды 1,5 МЛН
Implement Trie (Prefix Tree) - Leetcode 208
18:56
NeetCode
Рет қаралды 209 М.
This Algorithm is 1,606,240% FASTER
13:31
ThePrimeagen
Рет қаралды 849 М.
My Brain after 569 Leetcode Problems
7:50
NeetCode
Рет қаралды 2,7 МЛН
L45. K-th Smallest/Largest Element in BST
8:27
take U forward
Рет қаралды 188 М.
бабл ти гель для душа // Eva mash
01:00
EVA mash
Рет қаралды 8 МЛН