What whys and hows are there for this code? Its a stack, and its in-order. Its use is printing out a Binary Search Tree in ascending order (as far as I can tell). Thats about it.
Spot on... I was wondering the same :) people who need to be given one step after other will learn well from this like @Xeno Bob and @Shresth Mishra...
Thank you very much, this algorithm has helped me to solve the problem: " write function that receives a binary search tree and returns a list sorted in ascending order containing all the item int the tree(integer , the list and the tree).thank: public static Node TreeToTHEnode(BinNode t) { Stack s = new Stack(); Node L = new Node(-1); Node lastNode = L; while (true) { if (t != null) { s.Push(t); t = t.GetLeft(); } else { if (s.IsEmpty()) { break; } t = s.Pop(); lastNode.SetNext(new Node(t.GetValue())); lastNode = lastNode.GetNext(); t = t.GetRight(); } } L = L.GetNext(); return L; }
Yes, that's true. You can do in order traversal for BST (not binary tree) to get the elements in sorted (ascending order). The converse is also true, you can do in-order traversal and check if the elements are sorted (ascending order) in order to determine if the given binary tree is a BST.
Did you know, you can do iterative in / pre / post order traversals using same code?? Checkout how I did it in just 20 lines, in my new video ruclips.net/video/6wxNc8gCj8E/видео.html
Conversion binary tree to doubly linked list is similar to the traversal (inorder is good when we have binary search tree and want sorted doubly linked list ) but instead of printing key value of nodes we append it into doubly linked list Can we convert binary tree to doubly linked list without recursion and without creating new nodes in time O(n) ?
Yes def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]': if not root: return None
stack = [] temp = root head = Node(0, None, None) last = head final = root while True: if temp: stack.append(temp) temp = temp.left else: if not stack: break temp = stack.pop() final = temp last.right = temp temp.left = last last = temp temp = temp.right
first = head.right final.right = first first.left = final
I think you make some thing wrong in the Binary search tree. The left children of root 10 should less than it and right children should greater than their root
It works fine in case of right-skewed tree. Suppose, root = 15 root->right = 25 root->right->right = 35 root=15 root!=NULL, we will push 15 to stack. root=root->left = NULL So, now as root==NULL, we go to else condition and print 15 Now, root = root->right = 25 And then, you continue following the same process.
Tushar your videos are lovely. Can you please start making videos on codechef challenges if possible.... It would be really beneficial for us in understanding complex questions. ThankYou! :)
This channel is gold. The videos are simple yet amazing.
Thank you so much for making the concepts so easy to grasp!
Really enjoy your visualizations of algorithms which facilitate learning. Thanks.
most clear explanation on RUclips.. thanks for such an amazing content
Finally understood the concept! Thank you so much Sir!
Why most people "explain" the algorithm by going step by step on some example, instead of actually explaining it by explaining the whys and the hows?
I'm making myself the same question. This way we don't understand the algorithm, but the example.
What whys and hows are there for this code? Its a stack, and its in-order. Its use is printing out a Binary Search Tree in ascending order (as far as I can tell). Thats about it.
Criticising others for self incapability is the first step towards self destruction.
Spot on... I was wondering the same :) people who need to be given one step after other will learn well from this like @Xeno Bob and @Shresth Mishra...
The only thing you need to understand is how an inorder traversal works. You're just doing it with a stack instead of a call stack and recursion.
Thank you very much, this algorithm has helped me to solve the problem: " write function that receives a binary search tree and returns a list sorted in ascending order containing all the item int the tree(integer , the list and the tree).thank:
public static Node TreeToTHEnode(BinNode t)
{
Stack s = new Stack();
Node L = new Node(-1);
Node lastNode = L;
while (true)
{
if (t != null)
{
s.Push(t);
t = t.GetLeft();
}
else
{
if (s.IsEmpty())
{ break; }
t = s.Pop();
lastNode.SetNext(new Node(t.GetValue()));
lastNode = lastNode.GetNext();
t = t.GetRight();
}
}
L = L.GetNext();
return L;
}
Yes, that's true. You can do in order traversal for BST (not binary tree) to get the elements in sorted (ascending order). The converse is also true, you can do in-order traversal and check if the elements are sorted (ascending order) in order to determine if the given binary tree is a BST.
Can you answer this in interview without knowing the answer beforehand?
Kinda... its just a stack. And you implicitly use a stack in the recursive version. For 90% of questions though, no.
You actually don't need to , just inform them of your approach ,if they feel like you can get to the solution , they'll guide you if you get stuck
I finally understand thanks to this video!! Thank you!
It is wrong code in case of right skewed tree it will not work
this video doesnt explain the intuition behind the algo but only explains the steps of the algorithm
thanks for the explanation of traversing tree unsing sthack
Simple and clear explanation. Thank you
This is easy to understand, NICE VIDEO!!!
Thanks. Your video made it so easy to understand. Much Appreciated :) :D
how to check one node is visited or not? Using hashset? but that may only work for no duplicates case, right?
What is you tube link to see similar questions? he shared it in end of video but i am not able to understand it
Did you know, you can do iterative in / pre / post order traversals using same code??
Checkout how I did it in just 20 lines, in my new video
ruclips.net/video/6wxNc8gCj8E/видео.html
Thank you so much for sharing this. It's so clear and helps me a lot!
Generally speaking, while(true) is a bad practice (in case you accidentally leave no exit routes) and I can imagine the interview calling that out.
Very well explained. Thank you
Hi tushar...is there no other way to do an inorder traversal iteratively without using a stack and morris algorithm?
It's pretty clear! Thanks a lot
this guy is a machine
Very clear explanation, thanks!
very well explained...
"my name is -char"
lol u wrong for that
my brain start glitching after seeing this video..
Conversion binary tree to doubly linked list is similar to the traversal (inorder is good when we have binary search tree and want sorted doubly linked list )
but instead of printing key value of nodes we append it into doubly linked list
Can we convert binary tree to doubly linked list without recursion and without creating new nodes in time O(n) ?
Yes
def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None
stack = []
temp = root
head = Node(0, None, None)
last = head
final = root
while True:
if temp:
stack.append(temp)
temp = temp.left
else:
if not stack:
break
temp = stack.pop()
final = temp
last.right = temp
temp.left = last
last = temp
temp = temp.right
first = head.right
final.right = first
first.left = final
return head.right
Very very helpful! Thank you so much
Thank you so much, this video is really helpful.
Excellent explanation. Just a small doubt. Is -1 suppose to be the left child of 2? I'm not sure about 11 as well.
It's for General Binary Tree..not for specific Binary Search Tree..
how is -1 bigger than 11?
this is not a binary search tree, it's not sorted data, it's just a random binary tree
I am getting an error when I do this :stacks=new stacksp;
Always try to avoid dynamic allocation of STL
love your videos , im from brazil thx
please make a video on Inorder Tree Traversal without recursion and without stack! Morris Traversal!
recursive so easy and iterative so tough
I think you make some thing wrong in the Binary search tree. The left children of root 10 should less than it and right children should greater than their root
+Buer Jiang
This was a traversal of a binary tree not a BST.
How did you figure this out?
umm you just jump into algorithm explaining how it works... but no explanation of how to arrive at it?
This code will not work in case of right-skewed tree
It works fine in case of right-skewed tree.
Suppose,
root = 15
root->right = 25
root->right->right = 35
root=15
root!=NULL, we will push 15 to stack.
root=root->left = NULL
So, now as root==NULL, we go to else condition and print 15
Now, root = root->right = 25
And then, you continue following the same process.
@@kritisingh3194 yes ty for explanation
awesome video
bruh what you smoked send me some
why? i dont get the joke
Nice explanation :)
Isn't the time complexity Big O of n and and not 'h'?
I know this is from two years ago, but h can equal n in it's worst case
I don't think it is a valid BST because it is not sorted. I hope idea is to only explain Inorder using stack.
no where it is written that its a "binary search tree"....
just a binary tree..
Tushar your videos are lovely. Can you please start making videos on codechef challenges if possible.... It would be really beneficial for us in understanding complex questions. ThankYou! :)
thank you
Thank you!
Thanks a lot.
great!
Toosharp!!
nice
In python please 🙂
REVISION NO 3 😶
whats "sthack" lol
i need subtitles
Iterative sika na bp😡
have you smoked weed?
why u r trying an American akcent
Why ask? He's really easy to understand, is he not for you?
Boarky Chup be lvde
He has been living in US from last 9 years. So you tend to start speaking certain words how American speaks so they can understand.
why don't you start off by learning spellings lvde
Aditya Darekar
Why shouldn’t he ?
why do you teach as if we are here to mugg up everything.
thank you
thank you