LeetCode Day 20 - Binary Search Tree from Preorder Traversal
Binary Search Tree is an important data structure and you should be able to construct it from an array. I'm showing O(N^2) and then O(N) solution starting at 8:49
Leetcode holds a 30-day Challenge in April with a new coding interview problem appearing each day, here's contest link: leetcode.com/explore/featured...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...
#Coding #Programming
Пікірлер: 112
We want Tutorial on Trees Errichto!
A tutorial on Trees would be great!
Fantastic video, I tried to wrap my head around the more advanced solution (2nd one) with various explanations, and your video finally did it!
Wow Errichto! You explained it beautifully. One thing i like the most is the way you explain how to approach a problem. Keep making such videos!
Really appreciate you starting with the simpler solution first. Helps build intuition for the more complex solutions
Thank you very much, didn't understand the code of O(n) solution, but drawing at the end of the video helped me to get the idea, now I can try to code it myself
This is the best walkthrough I've seen on tree problems. Thanks!
The way this guy explains is plain superb !! Thanks
hell yes we need more of these tutorials btw great explanation
This was amazing explanation of binary search trees!! I love you
It is fun watching you write these. I hope they give you some harder ones though, it is more fun when you don't know the answer right away.
Another outstanding video Errichto!! Additional tutorials on BST, BFS and DFS would be great.
Please keep the explanation (step by step + drawing) like in this video's end part. It's really helpful. Even if the problem is simple.
I really enjoyed it like a show! Go for these trees tutorial including recursion. Thanks
Thanks for showing O(n) solution. It was very interesting lesson.
yaa we want BST tutorial , it will be a great entertainment to learn from you bruh , take love ✨
you are great
I love your videos . Thanks so much for making them !
You are great. Very beautiful explanation :)
for my solution i used a stack to save the visited nodes, first i start by adding the root to the stack and for each element from the sequence if it's less than the top i do top->left = current. otherwise, i pop from the while the element values are small than the current value, eventually, there will be at least an element in the stack (at the end i add current to the right of the last element that had a value smaller than current)
You are a very good teachrt Errichto
Awesome explanation.... hoping to see tutorials from on Tree Data Structures :)
Enjoyed it 😊, please do videos on BST construction from other traversals...
The problem here is you return a reference of a local variable to outer scope but the local variable will be deleted if it goes out of inner scope. P/s: great content :)
@sahilchoudhary1473
4 жыл бұрын
can you explain what are you saying
@bacuongcao2170
4 жыл бұрын
@@sahilchoudhary1473 In the video, Errichto got a runtime error while he is trying to return the address of the root node (a local variable) to the outer scope. The reason is that the root node which is a local variable went out of scope (the function is returned) and it's automatically released (destroyed) so you no longer access the returned value from the caller function.
@climbnexplore1187
4 жыл бұрын
@@bacuongcao2170 Thx for mentioning this. Do smart pointers help (?)
@bacuongcao2170
4 жыл бұрын
@@climbnexplore1187 Of course, you can use a shared_ptr. But a normal pointer perfectly works in this case like what Errichto did in his video
@kunalsinghgusain2070
4 жыл бұрын
@@bacuongcao2170 no I don't think this is the case because no matter if its local or global variable objects go to the heap, its stack that gets destroyed after method exit but variables stored in heap remain in the heap. so the method is just returning the reference to the object in the heap, which still exists. correct if I am wrong I am telling this from java point of view.
A tutorial on various trees, like AVL tree, red-black tree, segment tree would be extremely helpful. There are very rare good tutorials on them
A series on Trees and Graphs would be great :)
The linear solution is very elegant. For some reason, my brain worked better with a stack than a recursion. I put on stack the first root (the result) and then if the next value is less than the stack top I put it on the stack, if not I pop from the stack to the moment it's either empty or the top is not less than the value and put again the new node on the stack.
Please Take Leetcode 30 days challenge every month!! you are a gem!
would love to refer to tutorials on trees and graphs aftere 30-day challange, enjoyed the video!
Hi Errichto . On Behalf of the coding community I would like to request if you could continue the LeetCode Challenge so that we can learn from it. It will be helpful for all of us as we had our previous Leetcode Monthly Challenge. Thanks
I solved using 3 methods. 1)Using stack 2)recursion 3)sorting preorder to get inorder then constructing from them.
@kaustavpaul6625
4 жыл бұрын
The third method defeats the purpose of the question. However, it's a nice trick. How did you solve using stack?
As we were only asked to return BST root which will be formed from preorder traversal we can just write a insert() function and it works in O(n) in worst case.
I solved it in O(nlogn) using binary search inside recursion.
Very cooll explanation 👍😎
Yes we want data structures tutorial 😁
We want Tree tutorial Errichto. Mercy, Mercy !!🙏
really helpful tutorial , thx :D
Awesome explanation and thinking process _/\_
My first idea was similar to your second one... but faced issues in implementation. ***Tutorial on Trees*** would be great
best explanation
The final solution you have is N time and N space but seems like Morris Tree Traversal algorithm makes space constant.
Can you make tutorial on the first problem of codejam round 1B(expogo)? Please...
"new" keyword makes the value stored in heap memory. So even if the variable holding it gets out of scope it won't get destroyed until manually deleted or the whole program is terminated.
above in O(n) solution you put preorder[id] > limit for boundary check , would this be just id > limit ? @Errichto
Why not use binary search on the preorder vector and get a complexity of nlogn?
@Errictho maybe you can teach us some of your favorite topics from Computational Geometry after this series.
Which keyboard layout are you using? American?
Could we just use a Queue instead of using limit ? That's what it seems to be doing if we are just incrementing id++.
More videos on tree and graphs please
Vision/Jarvis is such a good programmer
Will u not upload codejam round 1B solutions?
hello sir could u sggest what to learn in maths for prograamming
can such a method also be used for recreating BST from postorder, inorder traversal? what extra thing is needed for recreating tree from level-order traversal?
@Danzlh
4 жыл бұрын
I am thinking the same thing. For some input, it should not be possible to produce a BST with the same preorder tranversal.
Yeah and a semgnet tree tutorial would be cool as well
I did the same thing! So handy in C++ you can use int reference, had to wrap in an array in Java. Also isnt the space O(height)?
@barongrmel3797
4 жыл бұрын
Yeah I think but then its also O(N) :)
Please make toturial on tree and recursion, *How you encounter recursion problem*
Write c program to implement binary search tree by inserting in following 6,2,8,10,4,3,7 write c routin for find operation min.max.delete please solve the. Problem
same apporach as valid bst or not
What Is the name of the program you use to draw?
I solved it by regular insertion logic of BST. a simple recursion function
@taritgoswami3957
4 жыл бұрын
That's good, but, you are not using the fact that we have "the preorder traversal" in hand, not any random array.
@piotrgorski9786
4 жыл бұрын
But this solution is pessimistically quadratic.
14:49 "Global variable stuff like that BAD" lmao
erichto rocks
I want tutorial on segment trees
There's a mistake at 8:41 : The time complexity of inefficient algorithm in N*Log(N) not N**2.
Plus blue yeti sucks, get a pro audio gear, you deserve it. You are such a talent.
Code Jam vids?
What is difference between low+high/2. And low +(high-low)/2 in binary search? Please tell
@jinxblaze
4 жыл бұрын
The latter does not cause integer overflow
@ajays861
4 жыл бұрын
kzread.info/dash/bejne/eYlrptKgeKy0h7Q.html Watch this video! the second formula will not cause an integer overflow.
@rajdave9862
4 жыл бұрын
@@ajays861 thank you so much, buddy ❣️, god bless you, thanks again.
@rajdave9862
4 жыл бұрын
@@jinxblaze thank you so much
@ajays861
4 жыл бұрын
@@rajdave9862 no mention 😇
YES
Tutorial on Trees is needed too much
Tutorial on Graphs and trees please
The problem can be simply solved in O(n) by performing BST insertion for every element from left to right of preorder array..
@PiyushKumar-qj8ue
4 жыл бұрын
Think carefully, it won't be O(n). In worst case it will be O(n^2).
@srikanthnarapureddy4580
4 жыл бұрын
Yeah thanks for correcting me
How can you simply know that bounds will work like that, he didn't even try to break his approach. it simply worked like magic.
more trees and graph tuts plz'
yes, we want tutorials on trees and graphs..............
I implemented it using iterative dfs, with upper and lower limit for each node. But it’s slower then your approach haha Ps just realised lower limit is not useful here
@rajarshibose5122
4 жыл бұрын
That's the key observation .I have done the same thing ,later realised that.
As a Competitive programmer, you may be not familiar with ‘new’ operator.
Why Don't You make tutorials on programming??
ayy i'm early.
How can I be like you ,what course should I do ,plz sir help me plz suggest me something ! That can I follow in daily basis to improve coding 🙏🙏🙏🙏🙏♥️♥️♥️♥️
logical but implementation is brain teasing
I wish someone could help me with a python implementation of this algorithm, its very elegant
@bismeetsingh352
3 жыл бұрын
class Solution: def bstFromPreorder(self, preorder: List[int]) -> TreeNode: def helper(limit): nonlocal idx if idx==len(preorder) or preorder[idx]>limit: return None root_value=preorder[idx] root=TreeNode(root_value) idx+=1 root.left=helper(root_value) root.right=helper(limit) return root idx=0 return helper(float("inf"))
make same video for only binary tree not bst
tutorials on trees
I can't stop laughing when I see TreeNode root = TreeNode(root_value)
Can I be Your Friend Please.....
You're an amazing competitive programmer, but probably you should learn the c++ language a bit. For example, it was surprising to me that you didn't know about local variable's lilfetime and that it is an issue to return reference to it as it is already destroyed.
first cmnt.
Blah Blah Blah
Python please !!!
@shivaraj-bh
4 жыл бұрын
I have written a python3 implementation...O(N), it basically remembers the minimum possible value and maximum possible value at a given node and decides whether the current node fits in the position. check it out here: pastebin.com/MrNg1EiF