Tree Data Structures and Algorithms | Abhishek Kumar | Skillshare

Playback Speed

  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x

Tree Data Structures and Algorithms

teacher avatar Abhishek Kumar, Computer Scientist at Adobe

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Lessons in This Class

36 Lessons (9h 28m)
    • 1. Introduction

    • 2. Trees - Introduction

    • 3. Binary Tree Representation

    • 4. Binary Tree in C++

    • 5. Simple Binary Tree in C++

    • 6. Types of Binary Tree

    • 7. Binary Tree Insertion - Level Order

    • 8. Binary Tree Deletion

    • 9. Tree Traversals - Inorder, preorder, postorder

    • 10. Inorder Traversal without Recursion - using Stack

    • 11. Diameter of Binary Tree - LeetCode

    • 12. Symmetric Tree - LeetCode

    • 13. Construct Binary Search Tree from Preorder traversal

    • 14. Binary Tree Maximum Path Sum

    • 15. Valid Sequence from Root to Leaves Path in Binary Tree

    • 16. Cousins in Binary Tree

    • 17. kth Smallest Element in a BST

    • 18. Invert Binary Tree

    • 19. Search in BST

    • 20. Count Complete Tree Nodes

    • 21. Count Unique Binary Search Trees - Catalan Number

    • 22. Sum of Root to Leaf Numbers - Recursion

    • 23. Reverse-order Level Order Traversal of Binary Tree

    • 24. Maximum Width of Binary Tree

    • 25. Check if 2 Binary Trees are Same - Iterative + Recursive

    • 26. Zigzag Traversal of Binary Tree

    • 27. Construct Binary Tree from Inorder and Postorder traversal

    • 28. Vertical Order traversal of Binary Tree

    • 29. Closest Binary Search Tree Value

    • 30. Path Sum III

    • 31. Sum of Left Leaves

    • 32. Delete Node in BST

    • 33. Sort All elements of 2 BSTs

    • 34. Maximum Depth of Binary Tree

    • 35. Tilt of Binary Tree

    • 36. Convert Sorted list to Balanced Binary Search Tree

  • --
  • Beginner level
  • Intermediate level
  • Advanced level
  • All levels
  • Beg/Int level
  • Int/Adv level

Community Generated

The level is determined by a majority opinion of students who have reviewed this class. The teacher's recommendation is shown until at least 5 student responses are collected.





About This Class

Tree data structures are one of the most popular data structures and are used in all the fields. Many complex things cannot be represented using simple Linear Data structures like Arrays and Linked Lists. In such cases Trees are used. There are different Types of trees. But the main power of Trees can be seen in Search Trees where there is defined ordering of nodes. So, if Trees are almost balanced, then Search, Insertion and Deletion Operations can be performed in time which is proportional to the height of Tree. That's why Trees are also one of the main topics for Programming Interview Questions.

In this course we will explore different types of Trees and Search Trees and also different types of problems that can be solved using these. Each theory will be followed by C++ implementation.

So, welcome to the course.

Meet Your Teacher

Teacher Profile Image

Abhishek Kumar

Computer Scientist at Adobe


Computer Scientist @Adobe

See full profile

Class Ratings

Expectations Met?
  • Exceeded!
  • Yes
  • Somewhat
  • Not really
Reviews Archive

In October 2018, we updated our review system to improve the way we collect feedback. Below are the reviews written before that update.

Why Join Skillshare?

Take award-winning Skillshare Original Classes

Each class has short lessons, hands-on projects

Your membership supports Skillshare teachers

Learn From Anywhere

Take classes on the go with the Skillshare app. Stream or download to watch on the plane, the subway, or wherever you learn best.


2. Trees - Introduction: in this video, I will give you an introduction off tree data structure treated destructor is a very powerful data. Stricter. And later we will see different types of trees and are weakened or store different types of information in different forms of treats. So this will be just of any low three north boundary treat North third Street, that is Nordlinger. So what is your treated Destructor. So if you remember link list or a resource tax or cues, do your linear data structure. We store information in linear fashion. Where is Ah, hierarchical information cannot be represented in those or their destructive and trees. Good in representing hierarchical data structure, for example, or we have a trailer sittin. It can have Children. So you see her are here. This is a level one or level Jiro. This is a level one, level two. So there are different levels of hierarchy and this kind of information cannot be represented with linear data structures like link list or airy's. You know, let's of family arise ourselves with the tree workability. So we have a concept off group in every tree. So if you look at this tree, you see there to Rudy's on the mortem and leaves her on the top. But in our case, we will have a root and the top. So this is room and route will be just one node. It cannot be multiple, then via multiple trees. Then we call that forest so that most north, we call this one element as no so element or nor can be used interchangeable, generally across the tree or cavalry. So this is a group no every nor can have Children so noticed, better directly blew. It are called Children. So here is the Children off. Don't beat 30 and 15 are the Children off. And but these are not 50 51 52 dear, nor Children, often because they're not directly connected. They're what we call descendants, often because they all are connected to 10 but not directly. So let's say through Paris Tin. Then we will define everything officer below any north in terms of room. So Children off dinner so pence Children are couldn't be 40 earned, 15 burn, so same as a child. The north, which is directly below in order and connected to it, is called Children. Similarly, an order which isn't a clear of it and connected to it is called Parent. For example, Parent off 20 is Tim. Similarly, Parent, Off 30 is all certain. I don't know when you don't do is keep doing. We have to look the north reading direct clear of it and connected parent of when you Go to is not her. P 30 is what we call and sister off when you're too, so it's connected to one your toe. It lies in this part, but not you. And your Clearbrook leaves our notes with no Children. For example, all the north's hair colored in green our lives. So leave, said 100 When you know one when youthful, so whatever isn't green you go. You see, there is no telling off 100. Similarly, for 101 So these other nodes and the mortem no and sisters so any north thirties connected to it, but nor directly, for example, off twenties and sister of 100. Similarly to needles and sister 100. Because if we go one level a parent off 100 religious, 50 parent off deliveries 20 so 20 Asian and Sister we again move up and go to parent off 20 be reached 10. So any Jolson and sister of 100 what 15 is Norton and Sister of 100? Because we cannot reach to 15 by going up in one drinks similarly and sisters off when your three year 2 30 110 and similarly descendants. So all the north better below it. So it's we consider any north as the Roop. If we chop some subset off this tree, then bigot, it's surgery so busy part of the original tree. So consider any north as root and then job everything else so distribute, reformed if their digital. So all the North other than party in this, our descendants off 30. Now there's a concept of siblings. Siblings are reader brothers or sisters. So there it is, an old switch whose parents are unique. For example, if you see when you go to and 103 dear parents are different, so they're not siblings because they're not brothers or sisters. But if you look at when you know full and when you know for you, we see that dear parent are when you go to so they're siblings. So in this case, we can write when you're awful. When you're afraid. Similarly, what can be other siblings? So you if you look at 2030 and 15 these three older siblings 2030 15 are also siblings, so parents would be seem. It's a really less commonly used but sometimes are called uncles were, If so, the parents off to Lourdes, also on brothers and sisters or parent, that is siblings off Parenteau Article uncles, for example, of 51 is not apparent. Off 100 fifties apparent of 100 and 100 and one on a trip. You on Aegis Sibling or 50 Norte Nordeste sibling. In this case or so, let's look at another example. Let's look at when your twin when you're three, your parents are different. These two are not siblings, but if you look at this doing, then 52 51 are siblings. So for one year or two, if they look at north of one year or two, then 52 isn't uncle off. When you have to go to its parent is this and its sibling is 52? No, Or let's look at why doing need trees if we have other data structures, so one is we can store our killing formation, which is not possible. It you near the district. Er, let's say you want to store ah side system to present the fire system on your computer. So how you can represent there you see hierarchy. The top most of cold air is route. Then within that we have multiple folders for example user than you have home and some other forgers. Then video home. You can have this stop documents, downloads and other folders and within the stop it. So you have a file one and you can have another holder for older one or 42 within their to have another file. So you if you want to represent, let's see or this file one so you can see the route been home, then the stop. Then finally one similarly for other norms. If you want to represent this document, then you will write the rules home Document. So are this until this form say tree here. So treasure. Very good in representing her killing formation. Now we have looked at what we call a non order trees. So there was no knows enough are drinking on the Children off Any note what ah trees become much more useful when we have a concept off ordering or we call them ordered trees. One simple example are so street were ah Northwich Children, which come first are generally lists, then these. And in case on buying research trees, which is a special case of surgery, all the left Children or any nor in the left sub tree of Disney World will be less than Disney World. And any north in the rights of tree will be more than this. More so. This mix the search or access very fast because if you want to surge, let's say let's make an order treat. So we have been my injuries, her street, and here we have sleep here we have 20. Then we can have 15 and 25 and here we have 22. So let's say we want to service for 22 so we will come here and we see that 22 more than 10 . So we will not look at any node in this sub tree because any Norden this obtainable with less than 10 and 22 is more than 10. So we go in, right? Told here we compared with 20 again, 22 is more than 20. So forget about the lefts of tree. Just over. Rights of trick now very is 25. We see that 22 is less than 25 so it has to lie in the left sub tree. So we go left and we find 22. And if we reach the lift node and we don't find the value, we return that it's not really so here. We don't need to access all the nodes because we have a concept off ordering here. So even if this is a balanced, then at each level we will be chopping out. The remaining are foster norms. So in case of balanced Sastri, we will have log arrhythmic time. But this man would be balanced. But on every it's better than Lini asserts, like in our air link list, where we have to look for every node if the structure is not sorted. Similarly, insertion is faster, so it's better than areas because if we insert anything in in area, so we have an area. 12345 Let's say, want to insert six in the beginning or anywhere in the at it and then we have to sift everything to the right and inserted. So here pain will be lenient. But here again is the the trees somewhat balanced. It will be faster than linear insertion and also it. So we have a non ordered list. Ben, then in their kiss in certainly list will be faster because the list Injun on ordered. Then simply we will insert and the and so in certain really faster than Aires, but slower than on order list. No. Another at one place is that there is no upper limit on the number of nodes. When we use areas, we have to define the size. Yes, specify the size off very if we want to add more elements than we have to create in January and copy everything your January with larger sage and copy everything to new Eri and insert new elements where to the north are connected, using pointers left and right in case of boundary. And it can be more in Kissel's non mine retreats. So there is no upper limit on the number of North, same as link list where there is more limit 3. Binary Tree Representation: in our previous Really, we had seen what is a treated structure and why it is so important. No, we will start modifying our tree and we will call it mind retreat and or it's clear from the name by angry means to So what is the importance off to hear industry? So all the tree vocabulary that we learn in our previous listen remains applicable in the case of boundary three years. Well, so rule Children parent leaves all replicable. No, let's see, what is the boundary tree? So here we have a tree whose nodes can app at most two Children, so at most does not mean exactly toe. Every note cannot have two Children because some we're down the line, you will have leaf nodes which by definition, help Jiro Children so any nor can have Oh, jeez, Children. One child like this All told, but not more than two Food jewel 22 Children 012 And since here we have at max two Children , we named them as lift child earned very chilled. This is not possible in the case of General Tree, where we can have ah, tens or hundreds off child. So there, we can maintain it in some linear destructive or there may be some different way off doing better, and we will look at that in some different forms of tree which are not boundary for you. Number two for three, where it can have 23 or four Children. So every node we love you will lose and then it cannot. At Max Tree Children so desires Nordmann retreats to four tree. They will see that later. No, let's do some quick exercise Build on. This is small constraint and we have to identify which of desire by and retreat in which is not so. There we see that one has two Children 213 So this is correct. Similarly, to have zero we see also correct, it can have any very general one or two. Similarly, Tree also has two for 050 so lost the North's qualify and visiting mind retreat. Similarly here one has one too old for everyone, so it may look like a linear structure, but it's valid mind retreat because every note has from 0 to 2 trees of the Sergio Children . This is 111 to it. Oh, does not wear little condition. So does he. Also banditry here once or dissuaded three satisfies it. But do you see to us three Children? So it's a very literate at two, and this is not a band retreat. Now this again is a mind retreat by the same logic that we saw here. It's not as one Children except this last leaf eaters you, so it's also valid here. It's just one north Justin, and this itself is a boundary tree because it does not violate any of the properties. Now let's see how we can represent boundary or trees. So it really is represented by you pointed to rural route. So you may Seelert. I have to represent it by all the notes. But that is not required because once you have going to to root, you know that it cannot Onley two Children so left and right. So if you have route, if you want to access, let's say four than what will you do We want to access for and were given this route. So we were right. The group, right. So this will come here so rude, right represents three The left represents to so rude rate we reach here at three and four is the left off three So again lift. So you see we can reach to any normal just starting from the group. Any Nord is accessible from route, so we just represent her group as it three. Similar Similarly in the link list, we just, uh, have appointed to the head, nor Bob Heard of the Linguist. And from there we can traverse to any Norden the link list. We don't need to store all the list This notice pointing to next note. This is pointing to next. So once we are access to this had no we can reach anywhere in the list. Similarly, here in the tree, Once we have access to root, we can reach any part of the treat. So it's represented as pointed to group on what the fruit is. No. So it's even rotational and the trees empty tree has judo lords good. If tree had any normal, then the top most noted that would by definition, so its original that then that means it has general lords and it re Nordea's represented at a data, and this data can be very complex later nor distant easier or character, then pointed to the left sale winter to the right. Erred in real applications. You can have more pointers like Winter Toe Parent, which can make some of the task very easy and some more point, just like Finder two siblings. But in plain mind retreat, we will just use these three values. And if we're rating according any language, let's NC placeless. Then we can define a Structure Gordon Award, and within that we can have any type of glitter nordeste two basic types like int care. But any other custom tape lake Plus a. Then you can have it off tape that close also, and going to two left child and what is left sailed. This it'll exist nor, similarly dis left really also Arnold all the North Star off same type. So the left say, didn't also pointed to the same instructors norm and similarly, nor disturb right. And we will use this nor the structure when we're solving their different problems off by Adrian when resource trees later in the course 4. Binary Tree in C++: in this video, we will believe very simple by in retreat using sleeplessness. So we will try toe construct this mind retrain sleeplessness and it has four nodes. And this nor is the root. This is the left child off route. This is the Rachel Off Group and we had seen that we represent in north, as in data. In this case, we're storing integral values. And then you lift and right off the same structure, going to to left and right. So let's ah, start writing court for this. First, we need to include those tender literary or printing some stuff and in the main function and no will start defining our Nord and within this, nor we will ever in NATO. Do you love a left pointed to left field decision, off tape, nor the same tape and then we appointed to the right child. Her personally will include constructor and we will know in its allies the different values in the insulated list in the say lies visited of it whatever. Valuables and and and left and right with null pointers. So we define anything custom if you have in the destructor. No, let's create our tree which is this one route is one then left is to rightist three. So first, let's create till this point. So Lord Group and we will pass ST Teachers because this constructor we have defined on route is one. Then defend others notes and to whose values too. And three who's were loose tree and fourth, whose values for now who is the left off one? So we were right root got left equal toe left it in your pointer and decision Lord object So we give an dress and similarly root lord right equal to address off entry. And finally So the this part is Burt. Now we have to set for as the left off three So we were right. Uh, and three north left equal do address so sends hole So this will build over tree Let's say we want to print Ah, this three earned four Then what? We will do trees So three years routine Dordt right from the suit for entry If we do root nort right north left the suit different for who wrote a note left and then we will print Good Lord left not right because it will take just one left Social Bertel of Children too and root right not left will print for so to enforce. And we are so in this certain gave to this would give food Let's earn it so if you got some users. Okay, so here Ah, fruit is not object So we use dark material dot right is pointer. So Villaluz point and ah also otherwise it will bring the north Point turn. It is an address. So we have to call this indicator to access the values toward this. No, we get to win four as expected. So you So you are Ah, If n off object oriented programming and on one huge instructs we got here were along to access the member variables using north operators which is not acceptable in As for the object oriented principles, then you can be fined a class institute and protect the variables. So I will compete. His tears changed too close and these were a defaulter private school. If we don't define any school, then constructor and distracters army public and then we need setters and getters. Or you can also write this deter This This point there is implicit when you destroy and deter And no, we will similarly defined centers. So we don't need settle for their tropical. We have already. Delta is already initialized during construction. - So we have defined over sitters and getters. No. Oh, this scored Will remains him here. This note salutes Comme entitled McCord for a structure and we will resign the Korb four plus so route Lord Sert left and we will pass this address into then Drew nort set. All right us and three on day three, not certain lift. We will pass address and forth and to print these values. Ah, root note. Good lift, Langert. And good luck to just function. Good details has worked and art get right So we have one errors nor group So some type wears set right and again we get to see more. So you see this Ah object oriented thing makes our life before so for the further will usually stick to this simple constructivist functions instead of class. Because the goal off this course is not to understand the object oriented programming, but rather on the data structures tree in mind, re tree mind resource, treating these data structures and different problems associated with them. So this will keep our courts simpler 5. Simple Binary Tree in C++: Let's look at some of the properties reserves satisfied by all the bind retreats. So the first properties that maximum number off notes that level will author boundary trees to raise to the bar l minus one. So we're required to find the maximum number of Nords north minimum. So make some morphine towards that level, will be there when or the night level is completely filled. So when in mind, retreat is completely full, then we fill all the possible positions. So your little starts from number one. So rude is at level one and he tests one more. Who to restore power? Jiro There, This one minus one in the next Ah, the maximum number of north region double off previous level. Because if supporters some level were four notes This is not This is some living, then maximum or of notes. And the next level will be then each, nor does to Children. So when Ritchie can have Jiro one or two Children so maximum driven. Snore has two Children, so each in order has two Children. So if we have four north third some level l then at the next level maximum, they can have two times for notice it notes because it's nor does, oh, Children. So here we will use this property. So first level has one note Second level we lab two times previous notice one, that is to Lourdes. Next again, double alert. So four next it. So this is to restore for one. This is two rested for two. This is tourist of poetry every time we multiply by two. So the power off to increases way who won and at level 10 at level two, it's one level two, Level three It's too so one less than level number. So they're actually you re stood for l minus one? No. Next properties that maximum off Nords in a bind re tree off height, it is to restore over its minus one. So again, maximum number of notes. What is the maximum number of norms in a mandatory when every level is completely filled? So here you, me, a tree like this. So this also has hired off three. I want to win three, but we can add more number of north without increasing the ICT. Notice this and this. So make some number of North's occurs when every more has two Children now is the increased any north? Then the height off tree will increase. No, it is given there the height off trees. It's notice. Always. Levels are completely filled. So if it is one, we're one Nord. If I it is too were one plus Donald. If I These three were one plus two plus four Nords. If we have four height, then we have one plus two plus two a square plus to give nerds similarly to restore board. It's minus one. So this is a simple geometric progression with its values and ah, the the issue is to here. So who is to about it? Minus one diverted way. Issue minus one that is two minus one. It could do to restore bore. It's minus one directory to minus one is one so anything? Director? Very oneness. The new router itself. No, let's look at third property, which is, in a mind re tree that in Nords minimum possible height or a minimal number off levels. Both are same thing is log based to and plus one know how we'll get this. We had seen in property to dirt in the Mex. There in Max do not Maximum number of norms with height it is to its minus one. So here in the max, which is in is equal to toe, it's minus one. So this is from property to net resource. Just know no, a move. Want to decide? So we get n plus one equals two to restore Poritz nor pick done locally the most base two on board states. So this anything in exponent or power comes, you know, So it becomes its names Log, toe, toe So this look toe to its one. So this ah, it becomes log to in this one And hence the proof minimum possible hiatus log two n plus one No, the lost property for this video in mind Retrieve it. Leafs has at least log toe l less one levels. No. Oh, maximum off leaves or minimum off levels, of course, when all levels are completely fooled. So at least this much levels that is minimal. Number of levels for a given number off leaves believe in all levels are completely filled . That is, all leaves lie at the same level or lives. Oh, uh, live in ill. So this is possible when lives are at the same level because if they believe their different level So here these tour leaves and this one is leave. So here, make some itis. Three. What number off leaves his three. What is the heard? More lives. We get four lives with the same height. Same number of levels maximum What off leaves and minimum number off levels will even all the leaves are same level. So let all the leaves are at level Will then from property one. We know that maximum number of nodes at level l is to restore power l minus one. So make some number off leaves will be who is to devour l minus one or so? It's in Leonard's maximum off leaves. Then this will be equal to the rest of our L minus one. No, let's take the log on both sides. No more. One toe the sage. So l becomes one plus log ill hence liberals. So I hope you understood all of these truths. If not, then try watching the video again. 6. Types of Binary Tree: in this listen. We will look at different types or Bindra trees. The 1st 1 is full buy in retreat and all of these have similar names. So that's where they're confusing full When retreat means it does not mean that it will be fooled on all the levels will be full. We have some. Another name for that. So full 100 remains every nor Dad, Jiro or two Children, not one Children. For example, if you see the first tree here, we have three levels and all the levels are completely filled. So all of these north also who are geo Children all the leaves will have no Children. All the internals here will Apple Children. Similarly here it does not look very full, but still it's full when retreat because all the North's help two or zero Children. So one has to three year Jiro. None off the North's have one Children so dizzy. Also correct. Busy also correct. But let's say remove this. No, this is not a fool when retreat because this one has just wondered. So in order to make it full, you have to add one more note. No, next is complete when retreat so it's similar in some sense, but also different in some things. To full render Tree to all levels are completely filled except possibly the last level. So if you see it earlier examples disqualifies that complete Wender dream because all levels are completely filled and even last level is completely fooled. But this is not a complete when Richie, because here we have 1234 levels on this Level one and two work complete. But level three is not complete and it's also not the last level Onley Last level is not alert so we complete it can be complete or may not be complete. So these tour valid examples One practical example it'll bind re keep were also the same property holds and all the little Sir Phil except the last level on the last level is as left as possible. So you see another example that I'm going injured, which is very similar toe. The second example decides same number of norms and even same number north at all the levels. But still this is not a complete render tree because only at the last level it can be non filled, which is the case here, but it should be as left as possible and this is not as left as possible. But this is all the three are to the left. Here we have a gap in between. So this is the definition of complete brand retreat. Next is perfect Vendor tree. So this is the in jail Since complete at all the levels, all the internal nodes have two Children. All the leaves are the same level. So here's the first properties holding. If you compare this tree which is full vendor tree, all internal north step two Children. But all the leaves are not at same levels. These two word level four. This is a level three. This is a little too so uh or fragmentary tree. All leaves were the same level. This is a traditional country. So in this case you will get a complete kind off A structures like this. So here we have just two levels, or levels are full. All the leaves are at level two noted last level similarly here. So here I it is to a writer's three. And if height off the street, it's the number of North will be to restore power. It's minus one. You know, just fired is one then more of north is one if itis too. Then the Wilton double the previous level. So to more. And if we have one more levels than again doubled up previously. This is four. So if you keep adding these one plus two plus two square talk you and if you have it in, then it's minus one. Then this. Some off the geometric progression becomes do is to put it minus one. Directed by common difference, which is to minus one. This becomes one. So to raise, to power its minus one. And this is the best case in. Are you for in mind retreat? If it's perfect, when Richie, then the or so's time can be comme perfectly located. Make if these are ordered on next year's balance when retreat. So they're definitional balance by under trees that the height should be order off. Logan. Not exactly Logan. What? Order off Logan. And there are many examples off balance Banri trees, for example. A real treat. Read Malek tree. We also 40 but those are not my injury. So each off them have some property. Some constraint with gifts. The tree oh, balanced in some level. For example, in a real tree, the max difference between lift and rate. This is the number of Nords in left sub tree and rates up tree is one. So if you have a tree like this, it's any military because left sub Tree, Aguirre notes, writes up traditional. If you have this, this is still a military and a balance when retreat because left sub tree of one has one and right sub tree had euros or differences one. And this would be dis property suitable for every note more just to root more. And what if you wear this at level three? This is perfect because for three boat our deal. So here it's okay for a whole search. Find left has one greater Jiro for differences one which is acceptable. So year old search fine. But this node one you see left hers to third trees to Nords Man right rights of tria journals or differences to search violated here. Similarly, if you were the north here, then it becomes a real tree. And let's see if you have a north here then this property horse here, here here's what do to violate, said the left has to, uh, notes, But rights of three had urinals. So this is how it makes your done, the trees not skewed in any one direction, and it gives it balanced and it's society's off. Daughter off. Lauren. We will see more of this later on. We study able to Ariel trees. Similar lizard electorate has another property that Ah, we have rid or black nodes. So either Redmoon what Black knob. I cannot draw black here because the background is black and there are certain more constrained that all the leaves should have same black deft that is, in the past from room so that leaps would have same number off black nodes. Similarly, there should not be too. Read notes. Consecutive tour. Not smart. There can be two consecutive black notes, so these are the different properties which keep them balanced. No, let's look at another tree. Vicious degenerate tree. So every internal lord has just one sale. So we look like a linear structure, very similar to link list. So at every note, one of the very least missing only left or right is present and performance where it looks very similar. to link list. So for North four levels here also for not for levels, number of levels is number off north, so first time will be off, daughter off and 7. Binary Tree Insertion - Level Order: in this. Listen, we will see our to insert in new move into the Bindra tree in a level order, fasten and by level order, I mean that. Or let's say you are given a mine retreat and a bind retreat can and a maximum off to Children. So, of yep to let's say, in Cirque 60. So they're resurgence there. There are many ways we can insert. We cannot insert as a sell off 10 because 10 already has two Children. Similarly 20 Beginning, sir. Here also. This is fine here, All too even left off this even 30. So the constraint is their level order That is the first level where it can be accommodated . So at the minimum level and also oh towards the left. So it cannot be obviously inserted. A level one similarly level to level two is already full to notes at level three. Rezidor, 20 has two Children. So we cannot 3 60 editorial of 20 Tortilla just wanted, which is right chilled. So what's left for us? And he simply so there we will insert 60. So this is the requirement of this problem. So how we will solve it. So for this, we will create a que for level order or presence. We generally deal with you. So in Q, we will initially insert a little more and then we can do same It. We do a Brit for searching a graph we can write while Q not empty. So look, you is not empty. Executed this loop and initially via inserted and into it. So curious, not empty. Certainly emperor here. So what we will do? Move in the two. You can only ah off from the beginning and insert in the end, killed or front and then you'll off there from Parliament. So no in contains the values this 10. So Andy north the north containing 10. This no what we will do. Yes, it's small, so it's left is none. Then do mix in new Nord salute severe to insert 60. So the new normal All right it as in and equal told 60 appointed Lord. So we will make in and lift off this. But this is not true in this case. And once we have inserted, we don't need to execute further and return. But if o An already has left, we will not make it left because it already has a left. So we will take four. Similarly really take for right. It's right, is none other than make and then as the right off this Nord and return if left and right both her present than what we will do, we will do Cue Dordt, who's lift and also plus right. So Noah here it did not work through for 10 and we have already port and from the cuse who accuse them here. But before this loop completes being served on P and 13 to it. Because none of these conditions are satisfied. So no Que has twin peaks and 32 elements. So again, it's not empty, so it will prop 20. It will take for left. It's their right, it's there. So no, no, these will exit you So it will. Who's the left and right off the current node toe the q 20 sport and what is inserted for B and 50. So you see, there you elements are inserted in the level Order for Stan is inserted. That is an order level one then, both of which say Lord, next level, that has little to do with our inserted in the queue. So in the cued elements, the order in which they're inserted, they're processed or pop in the same order. So this is level one. This is level two. And when we processed this really insert the cherry lof, this mold, which will were one a little more than the current mold. So for people Pierrette level three. So before 40 50 will get processed, 30 was already there, so 30 will get popped. We will take your fruits left Regional. Yes. So we will make it's left us in an Indian arsonist immune orb consisting of 60. So no left off thirties. Listen in and once we in 30 to return. So this program will not execute further on this will be the new state off treat. So let's write it Never called. Um Oh, this is the tree that we have seen in the example when this is the basic Nora structure. So let's first builder tree similarly cleared or the Lords for 36 One more Don't be 40 40 50 and 70. I'm just naming these variables for convenience. You can give any other name just to denote that. And horse the Milutin Monk lift off and then is stunning. P in 20 and right is and 30 similarly left and right off turn beer for being 50 respectively. No, the right off 30. It's in 70. So just in orderto bring the tree we can, or do any of their Trevor since reorder Quest Order are in order. So let's right there in order for its root is empty. Then we don't need to do anything. Just return. There are no norms in the tree. Otherwise, first Brenda left and then bring the Lord and then print the right sub tree so they, in order will be then before printing till in all elements off lifts of tresses reprinted similarly for every note. So now it will call in order on 20. So before printing 20 old elements in the lefts of tree, which is 40 so 40 than 20 then 50 and 10 30 70. So let's bring the tree before we insert the new Nord, and then again we will bring the trick in order and it takes a little pointers. In 10 is the root. I heard a new line they concede prince the tree in the same order there is expected for beaten and 29 50 10 30 70. So this is the got into street off. Three. No women in 3rd 16 to it. Let's define a function insert level order, and we need the pointer off the tree that is the roop and then the value that we want to insert. So let's create in new law with this value well on. We need to include the curator in order to use the queue, and you need to specify the type we will in certain or pointers into it and cue Dort. Push a little more and front element and then the queue. So if it's not in left, then other ways, both these conditions are not satisfied. That is the north North, as boot left, as well as writing been riven, who was the lift as well as dough, right Children, toa que And then we will begin, walk different element and take four Oh, the Chris Morning Lords. So ultimately, what will happen if there is a complete mind retreat? Then it will answer to the as a left tail off. Oh, the left most nor in the last level, no one's no we need to insert it. We will call in certain level order and we want to insert 16 3 So sixties would come here the left tail of 30 and again we would be in vain. Order travels a lot Destry after insertion. Okay, so we have not related the pointer off route move. So no, the in order to reverse alert scenes, let's see if it matters over expectation. So 60 comes here. So for B 2050 then pin for B to d 50 10 that's expected. Then it will come to this left sub tree and this has left left. At 60 it will print 60 than 30 then 70 which is as expected. So the CEO you can insert in new Norden were by and retreat in the level order fasten 8. Binary Tree Deletion: In this video, we will see OKC ability and old from a tree mine retreat. First we will see you method which involves Trevor sells off the tree. Then we will make slight modification to our Corp so that it can be done in a single troubles. Let's see how we can believe. You know, let's say this is the mind retreat. So here one is the room and let's say I want to delete No. Three, which is this normal? So what we will do and in order to maintain the tree in a good state because the surge of Fitri Although although this is not a search tree at the moment, but our trees are useful when it has less hate because although prisons depending on the height of the tree. So when we delete in north, we have to fill this space because this node itself maybe may have some child on this intern mayhem some for the sub treat. So we cannot simply remove it because what will happen to the remaining north below it. So we have to some element here and then get rid of three. So here we will pick element from the bottom. That is the last note at the last level. So in this case, Mrs at level one, level two, level three Little food so forth is the highest level. So the last element at fourth level it's six. If six would have been here, we would have picked that. So in this case, these Big six and what will be the Regent result will be the remaining norms will do in seem three is going No for three will not were so what should come here? We will take whatever is done Last note six will come here on remaining structure will remain the same and six is no morir with auditors moved to three So in order to ah, make this D Listen, we need two things What is the point? You're off the north that we want to delete And what is the point? Truth The last Nordion The last level We are just given a value 80 military I'm not in North Pointer so dusky may or may not exist in the tree. So if the skis form then find the last north put it there and get rid us that no So the result of this is this. So how we will achieve that again. Similar to level order. Troublesome. We will maintain a Q and we will Mr Wood morninto this and Wales Que is not empty. We will do the processing And let's say we keep two pointers whose is in order stuff for pointed and last note or the personal. This is all excited, this loop. So what we will do, we will pick one element. Let's a current mood on current more will always video element dirty both from the you killed or front and we'll take if this value matches with ah this key. So every North has you know in our case it will read then left earned right pointers. So we will compare this tough current note with the key. If it matches, then we will update this kindled Swiss current Lord Data is equal to okay then keen orb equal to current more and also Ah, we will keep updating this. You can use this last norther the current No. And when this loop parents, that means the Q is empty and every North has been processed. So whatever was the last value of this last mood that will de Nord the last north and it's the key was formed somewhere. Then this key Nord will be off deterred which was in its original. So no are said this. Look, we can take this keynote was form. That is he is presenting the tree and what we have to do We have to make the did it off, you know? So he Norcen data was three. We'll make this their take will to last north Sandretto, so six will come here. So what will the structure of tree at this point, everything else will remain same on leader. Well, it'll become six. So two new works of lower the value of six. Once we have our updated this we approve get rid off this last North as well. So how can we get rid off last night? We have a pointer to this large Donald Not that we have in this last nordeste pointing to this, but this is just another point to is pointing to this note on the left pointer of This is also pointing to this note so we cannot simply make last Nordic will terminal And this left winter who become that is not the case. So it's set last nautical Tonal. This will simply point to Mom. We're just left off. This mold is still for ending to this. So in order to delete this, we need to somehow ever going to tow this Nord. So in our first approves, what will do once we have I said to this that is three becomes six. The realtor was the tree again on again we will look for Oh, it's the left off or write off Any Nord is equal to this last note. Then we will sit the chorus warning left or right to mull. So again we will start from Rupe. Take your foot's left is equal to last. No, no, very difficult to last. No, no. So we will move further. So when we reach for we'll see that the write off for it. The last note is equal to this point. So what we will do? We will sit this See, you're not vertical to know and also delete this more so that will in world to travel cells . In first reversal, we find the keynote on the last note and in the second reversal we get rid off this last note. Let's implement this. So this is the treatment exact same tree, that resource just know. And this is the more destructive and we have defined and in order to reversal from them so that we can see the state off tree before and after the listen. So let's quickly defined their nodes. We have six months here. You know the North 30. Fine, No, let's sit set of the structure. So once left and writer to 13 So this level is done. Been to lefties four and three Left his five. So this is this is these forages air? Don't know. Forthright to six? No, we're fruit industry knowledge. Do the in order, Walter. It hurts certain the route and when he's little flirts around it. So it does in order to reversal of this tree, which is 462153 No, well defined, a function total eternal. Delete more. We will pass the route and also a key in this case three. So we will take for others in a residual force. Let's try to delete three what we saw in the example, and after deleting, they will again. Indian order reversal and this delete no will return the updated route. So this is a function that we need to define. So most cases off this leaf root is no, That is we're not. We're deleting a key from a tree which is empty. Then we will simply return because nothing needs to read. Um, no, there is another case that very just single node in the tree resistible. So it's that key matches with the route, we will eat it. Otherwise we will return the original group. So is not the routers left and not Ruto's rate that is single load and roots in detail is equal to he Then only we need to delete then delete who it's if that is not find fund again , we will simply return the original route because the key was more thorn. But is the three years more number of nodes? Then we will create a que que off north pointers It's and no we will create the two pointers he Nord It's and current more so current mobile going to the north which is part from the Q and the last more when this look turn its will in order last night so this current mobile ultimately whole world of values lost mood when this Leuchter minutes. So if the current Nords no ties a call to key, then what we'll do we'll update this. You know, that is reformed and nor condemning this key. So g Nordic all to current North. But we will not return from here because yours have to find last more. So what we will do this, if left, is their position to the Q similar leaves. That's right. Nobody's there was right nor into the Q and ultimately every normally processed on this loop will end and the last updated value of current mood. Will Denard, the last note rich in other cases, this six on this keen orb will be objected when we travels this tree so keen or this tree and current noticed six or the last month. So there may be case that keynote is not form. So we need to check your skin ord is a myth regarding the salute Wimal. If it's not there that Minsky was not formed. We don't need to do anything and we will simply return group. What is key is fun. What will you first? We need to off the the values the data member off this knob, Little Last North's nuclear. And once no, we need to is removed the last note. So we will write songs in front and we will pass the root and the North will be deleted. And we saw here where we cannot just delete distant last night this last note we just additional point services pointing to this note. So this or two pointers are pointing to this note the right pointer off this four and also this local very well last Nord, which is in North Point. So if we said to this tunnel, this will simply remove this. Going to what? This right off This is still pointing to 67 Ritter was this tree again? The six will be printed again on just to verify your point. Oh, we can We can try to Sirte current Nordic cool to know and you will see that Oh, this nor will still exist with those. We have just said this extra point eternal and Martine disappointed at all. Full It's run it and received the sixties choice All the trees gone which we have deleted. But this last notice not removed, so we need to remove it on This will not work. So let's create a function. The removal Undo. We need to pass an actual going to We have the actual 0.2 so we can posit active point to. So if seasonal then return Nothing to deleted. If Ruby call to him, that is the root is the norm that is there were deleted and then deleted so critical to know and in return. Even if you skip this delete your cold will work as expected. What? I am just too clearing the memory occupied with this North Swiss. When we are removing this more, we're not just removing this point to. But we are also clearing the memory from the heat when the program terminates this memory Lord Metka Levy Oh, he claimed. But maybe your program is a long running program on. This may be happening multiple times so unnecessarily or Lingus memory is not. Would no Bill welter were single tickets? It's left. Is this? No, we need to delete this note. So we need to have a pointer to the parent off that mob because that left and right pointer are held in the parent. So if we want to delete six, we need to find this parent and set. It's right for Inter Terminal so we will take this. Which left is equal to this last nor then delete the last note and also said it's left tickled no and then return. So as soon as we delete dirt No, we don't we don't need to process further. Simply return similarly fourth right other ways. We will do the same for both offers Children. But the last NorthPoint rule room in the same No lettuces on over chord. No, you see this extra six is gone. So when really three six comes here on day in order to reverse, it'll be distances not exist. So 41 then for you, then six. No, let's try other cases. Let's still delete this route. Motor itself, for the key for root mode is one. So first let's gets over. Answer. So when we delete 16 will come here and the in order terrorism will be for two, 6534 to 653 So let's run it 4.653 as expected. No, let's try a few more kisses looks idiom. We have just one more n one. We got all the links I have removed and rupees in one onda rigidly three. Then nothing will be deleted. So in order to reversal of just one, nor will be one on again after deleting three, three does not exist so again one. So let's run it. So it's 11 No. What if I delete the route itself? So the tree here, just one note It is one and we delete that nor itself. So it becomes empty tree and nothing is Drinkard. So hopefully this works for all the scenarios. So now how can we avoid this in double trouble? So So once we Travers to find the de Nord on the last note and then again traversed to delete the last norm. So how can we get rid off in this? So ah, well ah, finding the key node itself. We come had the values we can have two more pointers. So when Ah, this last note was inserted into the q through the insert every note to the Q and the six world last Northway inserted into the queue. So when we insert any normal like north left or nor does right. We also keep two more pointers whether you know it was the left tail off its parent or Rachel of its parent. So when we insert left Norden toe the to be updated this left pointer equal to in the north , who's left, we're inserting. And when we're inserting the right note, be a bit the this be your point. So when the six were inserted, this was inserted eyes, food. Right. So this be our will hold nor going to go for Let's make these two changes. So here we inserted the left Nordoff, this node so peerless current Nord and also we need to certain other one No, because only one off the left or right Children with the last north. So it can be the left tail or Rachel. So here you are equal to current no, and feel equal to little. So Novia so only peel or PR will have a value other will windmill. So now her dand off this look, this PR will hold a value of four and be a little windmill. So we know that four is the there in both the last normal and it's the right sales will set the Rachel off PR TUNEL and lead nerd mode. So, yes, be in. Then he'll left the courtroom. No. And if yours then we are critical to know. And no, let's is another court. And again it works. Is that also freedom? Memory occupied way This we time nor doing here just to verify. So no, we have removed this function entirely. So the second reversal is not happening during the 1st 2 hours A little year keeping track offer experiment 9. Tree Traversals - Inorder, preorder, postorder: In this video, we will study order different types of reversals that are possible in a bind. Retreat. This listen is very crucial because many different types of algorithmic problems oh, are derived from the travellers off trees. So let's see. So in the case, off linear data structures like a raise link list, stacks argues generally retailers in just one way you nearly But in the case off trees, there are different types of traverse. It's possible full. It's a dizzy over bind retreat so we can divide the Trevor cells into mainly to paradigms. When is using the deft first searched approach where we go as deep as possible. Dilute, restart! Didn't eso This is by its nature recursive in native On the second approaches, Britt, first search that it you are visiting old. You look at its neighbors, then visit them and then go one level deep. And so on this inner lucky's from the terror cells in grafs and further in the coarsest, we will we have three main for nominal types of reversals. One is in order to reversal. Then we have the order and we'll start of we will shortly see the meaning off each of these and under breadth. First search, we have level order. Troublesome. We have a notion Off level entries. We gonna start level from one over. Jiro, let's start from one. So this one either level one these two and three year at level two, 45 and 600 at level three and seven. Either level food. Now let's see what is the meaning off each of these travel suits. So, in order to persons, we first we didn't know Left sub tree left sub tree full. Ah, by sub tree we mean on the tree that is rooted at the left sale is called left sub tree. So for one for nor one the left tail is too. So whatever is the complete trees with their two is the left sub tree. So in this case, is the entire tree to four and seven is the left sub tree of one. Similarly 35 and seven. This constituted rights of three off one civilly it's well it for every node in the tree. So if you look at to, it does not have a right sub tree because there in north, I told and it has a left sub tree rooted it for with two nodes so in in order to person frustrated left, sub tree, then regional route mood. Then we didn't know rates of tree in the order in order means in order, left than middle the right in pre order three means before or early. So here we are, always talking in terms of route. So our first real legit route mode, then left sub tree and then right sub tree. I'm using this triangle to denote a sub tree and in post order we have the vote comes last . So does it only difference in pre order and post order, so left right but root comes first. But in the case, off post order root comes lost and then for stays left treated and rights of treatment recruit so desired it three different ways and in level order The visit level one notes first done level to Lourdes and so on till the last level. So let's ah, run of example off all of the East River silt on this given tree. So first let's cedar in order troublesome. So in order for every nor revisit the all the north off its left sub tree, then the Nord itself. Then all the north's off, right sub tree. So we will call this four northern one. So here what will happen? It will call for everything in the left sub tree so it will call in order on lift. In this case, it's too. And this will call in order. It's lift and so on. So we going to the left and we reach here. There's no lives left sub tree of four So nothing is printed, then four is printed and then the right sub tree off four that is seven. So we are doing it. This part and this call would have come from here to wrap colder in order off lefts of drink. So all the elements of love left sub tree of tour printed So we will bring to itself and after printing to will call in order for all the Nords in the right sub tree which is not in this case. So it will not not drink anything and this call to in order who would have been called from one. So when calls in order to and then bring to one them in order three. So this happens when we call in order to one. So in order to Brent one, then in order three because to the left on trees, the right. But before printing one this in order to will again recursive Lee call in order off its left which is four and so on. So you you guard idea So once all elements offs left sub tree off when are printed we can print one. So we are done with these two steps and no in order three scored So in order three What will happen? The same function. It will call in order sleep then drink for you then in order six So in order five will again call in order off its left original So nothing will you printed then print the node which is flame. So all elements in the left sub tree off three year into printed. So now we can bring this three itself And one street sprinted called for all the North's off rates up Tree of three which is six. So we're done with in order travelers. So for every note you see that before printing any north drink all elements off left sub tree So before printing when we have to print all of these for if you see one, you will see that all elements on the left of one our parts off its left sub tree and all elements on the right of one are parts of its right. Saptari. Let's look at another example. Let's save year concern over this note to so there is to here too is there so all elements in the left sub tree off to should be printed before too. So on the left off you were four and seven which is in the left sub tree. In the right, we don't have anything. Similarly, if you look at North three, all elements in the left sub tree will come before three. So in this case, we have just one element five So five comes before three and six comes after three. And this holds true for all the lords. So with this idea, we can quickly see no other Trevor since it was just pre order in pre order, we do first, Brenda. So if we are doing the order on an old so we will first printer Nord, then pre order off lift, then reorder off rates up tree So for every north it really printer before any elements in the it's sub trees are printed so it will first sprint the one. Then it will call preorder for this left sub tree. So this will first print too. Then call it for its left sub tree. It will bring forth then seven and then it will bring three, then fate and then six you can hurt. Try and drawing the complete rickerson stack and you can try it for yourself. And then let's see the post order here first it calls host order off lift, then post order off. All right then, bring to the Nord itself in there. And so if you recall post order for one, it will first print everything in the left sub tree as well as rights of tree. And in the end it will print one. So one will come last and no, we're calling Post order on to. So again you will come last here and it will call four and seven. So 1st 7 then four. Then too. Then flame, then six and then three and then finally one. So when it's called for three, it will first bring five Been six, then three. So this is the rights of tree of one. So after printing right sub tree, finally one is printed and left. Sub tree was printed before that. And now let's look at level order reversal. So in this case, it will be level by levels were at level one we have just one. Then I'd level to weigh up to entry and recovers from left to right. So two and three comes next dinner at level three via 45 and six. So full five and six and finally be up. Seven. So in this video we'll see the implementation off preorder, post order and in order travel suits. So let's start writing the court. So this is the exact same tree that we saw in the example. And this is the basic structure defined for an old Now let's first build a tree. So we will. We have seven norms in this case, so we really find seven notes and let's copied 34567 23436 seven. So we have defined the notes knowledge set up the religions it so left off. One is to write over on his three and then left off. Two is four right off traditional, then in trees, leftists and flavor and in threes. All right to use in six and finally in Fools, Writers and seven. And let's define a route mood. It's not mystery. We can use Inman as a group, but let's explicitly define and one as the rope. And no, let's right the court for in order to herself first. So this root seasonal then return nothing to print. This will be useful when you keep calling recursive Lee the same function for its left and right. So for Gamble, one calls for two calls for four and then four calls for left sub tree regional, so it will pass in order now so it will simply return and come back to four. And then it will bring for. So is the rotational do? Nothing just stretched on, and then we will call in order root lift. Then we will drink the later in the current node, which is root. Let's separate the values, my abs space and then in order route right? So it's very simple. Just three lines, of course. So let's call this in order function here and let's run it. So let's sue corporate in separate line. So we have 4721536 full seven they're too then one. So if you look at one, all elements in the left have come before one and all elements to the right has come after one and the other travel since will be very similar. Hewlett's defined other Trevor So Centerville. So in the order we first bring the value and then pull started. We print the value in the lost No, let's call it for Phillips Cooler all of these three functions and then compared regionals. So in order is 4721536 The order will be one first similar to give some space here. So preorders one comes first, then for the left of tree to comes first. So to then four, then seven and then in the right word three comes first and five comes then six. And for post order one will come in the end and then first left of triple Come So 74 then too then for you 63 and finally one. So this is so we can implement pre order in order and post ordered reversals. In next week we will see how to do level order to reversals which will use the breadth first search, better name. 10. Inorder Traversal without Recursion - using Stack: in this video bills he ought to do in order traversable offer banditry. But we will not huge rickerson and we had seen in over or Lear listens. So let's see how we can do it without rickerson. So when we do it with Rickerson implicitly were using stack rickerson stack when we're calling one function. Ah, Mr. Into order for Yum Polis. This is the root node. We had seen the definitional in order where we used to rickerson and we called in order on left sub tree. And then when this in order returns completely so this in order off this too will in turn call it's left and now left is no. So it will Oh, start returning back. So after left part returns, we printed roots and data. And then we called in order off route. Right? So it rejects. So? So when we call in order for one, it calls for two. It calls for four and no, there is no left. So it returns and prince for on Ben. It calls for rights of tree where there is only seven so seven blueprinted and then this call to four will return back toe to and then you will be printed and there is no rights of tree. So this will return back to one and then this one will be printed. And then again, same thing for the right sub tree. But we're not allowed to go this So what? We're Do we have to replicate this using stack So we know that in a stack whatever we put last is the one which is warped first. Oh, so what we will do? We will keep a stack. Any silly will be empty and we can have Ah pointer lets a current node which will start from group So the signature off the functional so dream in the same We have to just change . The implement isn't so current. We will initialize too Go route So this is again in order group And ah while you currently is there We will keep putting it into the stacks when the silly one is there. So stack will hold one And after causing so after putting it on the stack what we will do we will make current equal to its left. So first we pushed to one toe the stack then current comes here then again We pushed into the stack. Then current comes here. So we're making current equal to currents lived No, left is more there. So be way When we pushed for and we may currently call do currents left current becomes null because left off for reasonable. So when current becomes normal So there will be a look which will run until current is there. And when this loop parents And in this look, we're just putting it into the stack and making current pickled fruits left. And when current becomes no, we will start dropping it from the stick so we will pocket and also drink it. So this will week well in tow. This Oh, in order on left was each is burned and the new two starts traversing back. So we bring to the pub element whatever report and then mix currently called It's right And again this Lou build in were current is normal. So in this case, it ah current becomes no laughter pushing 12 and four. So we print food after popping you So four is no popped four is gone from the stack Only one to is there and current becomes currents right which is seven and again this look brilliant till current is no. So we will put seven into the stack and make current equal to its left, which is until now again, current becomes no. So this Lou 1,000,000,000 end and we will pop the dis element. So seven will report we will print seven and we will make current tickle toe. It's right which is normal. So again, current seasonal. So this Lubell not execute at all, it will again pop. And now you will report and we will print too. On current is no currents right which is to write again, Mel. So we will again pop, which is Oneness parked and we will print it. And no, we will make current tickle to its right which is three and it'll current is there. We will keep pushing it into the stacks. So three is no coast into the stack and current becomes its left, which is fight so far, we also pushed. Then current becomes is it's left regional. So we will pop flavor, drink it here and make it so right as current regional. So again we will pop three Andi ah, make current straight which is six and then repeat this loop. So we will. It was six to this tack and then again Ah, do this. It's left, isn't also it will start of a warp six and it will terminate. So if you don't understand this, just try it on. 01 Another example and it will be clear. So let's right the court for this. So here is the same example that I have been using for different travellers and on the tree notice structure which consists off left, going to write pointer and a detail Ament. And this was the clear implement isn't off. In order to reversal using Rickerson, we will create a new implementation where we will not use Rickerson. Let's call it stuck. We called. We will be using stagnant appear on. We need toe include stair kit. So this is tech will hold north pointers and then we have one current norms Seamers what we saw in the example which is a group. And then we were doing some or prison continuously what we were doing. Oh, we were inserting into the stack the current naled and making critical to its left until we reached the end and this will ah respond to this first call Do in order left. So when we reached the end, we would have inserted Want to in fort into the stack. So once very stand, Uh, this loop ends so well, Couldn't Okay, who's the current into the steak? So I'm just writing step by step. Whatever we have seen in the explain ism and then currently quartile currents lift and this will keep on going on when it will reach the end. There is no left lord. Then we come out of this and what we do, we start, we pop just one element. We report just one element because you see, when once we're done with the left in order we stand, we print the current mold. So when we need to learn, we know forward The last element that was inserted in the stacks of when we pop poor will report So we will bring forth and then ah repeat the same for the rights of trio Probably elements So currently call Do It's no top. Begin the top element then for the same element. And we drink the value off this Nord and do to in order for. It's a very tough tree, so we just do this one's. And once again, this entire Lupul execute until current is there and we will do this. Still current is there or this is not empty. And finally, let's heard a new line here and no women in order for bit and without rickerson on the same tree. And let's compare the results if there seem or not. So you see, then moved. Results. There seems so. We have replicated the rickerson we have you're using in explicit Stack in the Corp. You can again ah, go through a few examples if it's not clear, and I think it's pretty straightforward and it should be clear, you will see that there is 1 to 1 correspondence between this deafness. Um, and what we have done in this Listen 11. Diameter of Binary Tree - LeetCode: Day 11 off target. Delete quoting talent and to live a little salt lead for problem number 54 victory and it's are claiming the diameter of the boundary. Treat the first, let's understand what it meant. Weight and diameter. So damaging is the distance McLean to Lourdes. Maximum distance between any two pair of north in the tree. For example, if you look at this tree the distance between four and flavors this one and two were to conduct a number of edges. Distance between one and four is toe distance between one and five. It also to distance treatment four and three years 3123 Who will be? Don't have any larger than we told them this either. Full 213 So this constitutes off every territory. This is 42 to 1123 the longest part you have to find between any two nodes. Similarly, wave to one thing. This also has damaged tree. So, Leo, your job is not to find actual part, but just the value toe. The line cough maxim part possible in this tree between any two moves is offline. So how we can solve this gun so in order to solve this for this, you will be given the pointed toe took note of the tree. You will look at it. It's left up three and write poetry. Uh, it may be possible that lifts of three has two very long branches. Oh, young one cool and so on. And rights of trees. Very small, maybe one or two notes. Do you see that? Go. If you start from here and go all the way up to here and come down in the second branch, you will get a longer part rather than one part you take in the left and one. You're right. So it may be possible after their damages the longest pass light in the lips of treaty and nothing from it. Great. Or the other case that the diameter may lie completely in the rights of Crete and nothing from Luxor tree. And the third possibility that, uh, one component off the path laid in left tree on delivering writes a pre. Or maybe it's stopping at root itself when the rights of crazy empty. So, in order to find the damage, you have to find Max off these three things. One namely total left. Second ease. Damn, it is off the right sub tree and 30 Then the past course proved in boot. These two cases, the part does not goto the turkeys. The part goes through. So you have to keep track of what is the our deepest Norden the lips of a tree. So their deaths off. This will be one. Oh, are we will come from welcome than the diesel. Were you? Why we don't wear deodorant to reject one? If I had one branch here, then you steptoe would have become one. And their gift of food has become too the maximum left or right less one. So you want to need to keep kettle Maxim that awful from the group. So in that case you will have the party going from room and you will see what is that depressed? I can go in the left tree from that will be we can call legend similarly working the deepest note. I can go in the right subject that we can call It's too So some off these two? No, we will compare these three on. We will pick the next room. So let's right the court for this. I hope this concept is here. We need to worry about treating are there are diameter of the lips of tree in that the party will not go toe diameter of right sub tree but again will not go to If it goes through the roof, we will see what is the deepest taken go in the left. And what did the deepest taken go in the right and were these two? So we are breaking this problem recursive lee. So he'd be calling the the off rupees calling your group left and the off route. Right? So this visit Because if problem Ofri Kerson on what else you need to consider duty Due to this third condition, you have to also keep track of what is the are the best you can go from each of the Lords. No one would be that you define separate function for calculating the height off a tree on one. So you will do martyred ever since off the street, That would not be optimal. So for five you'll called a height for its left and right, and it will again call it right. And I for left and right. So it will repeat because so here we will optimize our solution. So there we just do one carcelle of the tree. And in that only we will keep track up the height of no. So we can define a utility function. So this is the main focus. Be on. We can have a helper function, be it and we will pass the route. And also a reference toe value. Right, So these will be updated in that call. But this main content simply call returned route and pass. They hurt reference to an Indian. Get that. You do know I talked on inside this level. Great. All of this logic Andi will also off the the Lumet. That's a quarto, Mexico. Ah, it's one because what is the height off in order? It is the maximum. Mm, the defense they can go in the country and the best taken Go in trade. Some treat obituaries maximum with pick that you managed to and finally less one. When this we will keep track off, I eat off each of the north agile Onda. And finally we will compare these three on returned the maximum that start trading court for this. So the remain comfortably can have and obviously very functional. Let's call it damage and it also takes three. Note little on one policeman with friends to fight. And it will also return diameter So diameter it will return the value returned with the diameter and whatever is the height of that mood will be captured in this very well. So first, the basic if really little We're calling diameter for relief. No. Then for this height, well, first, you and we will also return you because the time interest you. But this is namely to be returning. This is the right. If the North is Notman, then we will have Let's initialize the it's one managed to do you know, did you know died so left and right country and similarly de even really know the damage left sub tree on the really affect you in building off a bit earlier When we call it's on the left sub tree And also there dammit! Terrible return! So Bothwell is we're getting similarly for rights of tree on. We also need to update Once we have called it on there can rights of free will update the Heitor current mood which will be Maxell. It's one. It's too less one. So here you will see that we're kind off keeping track off. Uh, the number of Lourdes. So you really and leave? No, we will call it for its left Visual will know. So it will return a hero. Excitable. Also be none too long to return. Zero you take the maximum, these two on it will return a hero. And then we had one. So for Leaf North, it's one for one level of it's too. So this height includes Oh, number North one. But so I did in terms of number of months, uh, just told and recorded E and no weirder. We have to return maximum treaty in people. This Max has multiple multiple. You can call next one is that you provide to values. Then it was picked them ice on these two. Other than that, you provide anything idealist. So if you have more than two value, you can provide any list because here we are, even we are due to Andrea. It's one plus. It's cool. We have three values so we can provide any alleged list. It will return the maximum of that. Um, here We just need to call this so it's only notes from room till the personal number of north on its study notes. So still only personal. Oh, looks is only 12 hours. So what's the line? Number 15? Okay, we're not going to return again. Take cool. So it works correctly and in lead called in all the problems involving on line three trees . They do you think put in this form this means level order cover of ST who wanted me nor the one. Then in the next level, there will be two looks who Let me write it here in case you're confused. So if the right one cool three Who How are you then? There denotes the tree. So they frustrate all the North's off level one or level zero. That is one. Then all the North's off level two, that is 213 Then the next Level four fight. Let's say we have to write and nor below for also and first level who? These two North terminal so well, right? 12345 No money there. Thanks. So that will you know the street a little And six. This is a very deep, Would you say what? Internally. There, Billy Tree from it In our test on your data on the next, submit our solution on our soldiers in index. 12. Symmetric Tree - LeetCode: carnivals all another lead court problem and hurts problem We're 101 entered scored symmetric tree on The task here is to find whether given Bindra tree is symmetric or not So what is symmetry mean here? So let's say we have this mind retreat So everything in the lefts of tree is just a mirror image off everything in the right sub tree So if you draw a line here from the middle it will act like it's a meter So here to is there as the left sub tree left Nordoff this one then who is there in the this part of the mineral? So these two are there different sides off meter and then left off to history here right off to history because in middle you will see that your left hand appears right and right Appears left similarly is right off to his fourth and left off to his four. And when any left north is missing, then the Chris morning right north should be missing. So if there's something like someone, order here and no Nord here then in orderto men in the symmetry, there should be exactly left nor with the same value. So I hope you understand. And to see a negative example of this If you're drawing middle here, you see that delay. It's fine to but right off to history. So we need a left off to with exact same value. So this violates the floor property off symmetry. So how can we solve this problem? So, first, if, ah, routine seasonal, then obviously we can return. True because there is no such street. If there is only one more, then all foods correct. Because if we deride the mirror divided with the mirror than hair, it's no here. Also original. So this is also valid. And if there's more number of nodes than what we will do first we need to take the left off group the value off the north in the left off route you say miss the right off route. Once they're dissatisfied, we can checking dirt. If this tree is the mirror off this tree or not. So we have a functional etc. Is a beautiful and we can pass to tree Stephen anti too. It will take whether Teevens military media do you do or not. So what is the condition? The value off, Stephen. Sort of be seen minutes value off to. So this is both first level of tech than their values should be same. If the value itself is not same, then it's violated at the root level itself. Once this is satisfied, they will go where and compared that Whatever is in the left sub tree of this norm, there may be more tree hanging over there. It's the mirror off. Whatever is the right sub tree of this so same function we could call recursive Lee. Do you, um, not left and t two dot right? And is the meter do you are not right And he too dark left. And if it's true for every sub tree below all the nodes, so from bottom it will start returning true and this will propagate IHL group. So any very fritz violated, we will return false. So let's see how well, right court for this. So this is the problem. It's explain the exact same thing and here we have a function. It's symmetric, which is are taking as important the route more so. First the base case. If we're more reasonable, then we will return. True, it's we need to create a function, Let's say is mirror or a lot of meters because there are 23 Lourdes d one. So we just need to take if the left sub tree of this route and right sub tree of this route are mirror images of each other or not. And we're done for route, lift and root. Right. And this can venal also. So we need to handle that in our mirror. So if both colonels, then it's fine. If one off the minal and the other is normal, then they're not merely Mrs because they don't even meant in the structure property. So is anyone of them, Arnold? So if not even or not t two, then the only way it can be true is that voter Colonel So Stephen, equal to Tito this weekend return sort of make belief only one of them is enough. Then this condition will be false. No. Is disconnection does not hold true. That is, none of them is no. Then we need to check if the values they're holding our same or not. So here we're calling for two and two. So is Stephen. Well is not equal to t two. Well, then return falls so straight away it will return. If, let's say here it was five, then we would Compared to is not Samos faith. So return falls. But if they're true, there seemed the values your seem. Then we need to process, uh, compare the same function on the left, off to and right of two and right off to and left off to. So we have to just return. Are a meter Steven left. We will compare deviance left of it, detour, right and are the meters. Do you run right? Anti too lift. So let's sit in it for our basic case. And it says that it's true. Let's make some changes here. Let's stick this case or make one of the north smell so it should break the constraint. And this should not be no symmetric. Look straight for just two unknown, so it seems to work. Or you can try with mortise decision. When satisfied, you can submitted Solarte Sluder so it so it says that it's faster than 49.2 full percent bullets stray again, and this time of the numbers have improved dramatically, or 24%. The numbers fluctuated it. So don't worry too much about that. Oh, you should focus on your algorithm if it doesn't. Oh, give good number after many trails. Then there is a problem in your algorithm. Now it gives 100% both in terms off time and space. So we are on the right track. 13. Construct Binary Search Tree from Preorder traversal: Let's see how, Toby by and Resource Street when you're just given the preorder troublesome Ondo, this is lead core problem or when you graduate. First of all, what is the meaning of the order? Travers In pre order what we do off first, revisit the route north of the tree. This is the route norm. So first we visit a group for eight were reprinted first and this is just ah reorder Trevor's Orloff Destry and we're just are seeing what should we look the order to reversal of this in order to build it back, First revisit the Roop and then we visit all the notes off left sub tree. So after eight, all the north's off left sub tree Welcome followed way All the north off rates up tree so in left sub tree again You recursive lee call the same function that is you're doing the pre order Trevor's off this sub tree So again this you re will apply here So for street will visit this note This is the root for this left sub tree So first it will visit five and then it will called preorder on its left sub tree And this lips of trees aeltus one. So it will call it on one. And this does not have left or or Rachel. So this is done. So no. The calling from some five On this level it will look for its rates of tree and call preorder on its rates of tree rates of trees. Route is this so it will first bring to root, then call preorder on its left and right return. Also, they will return. Finally this intercept trees done so this orginal calling function it had printed the group and then it has called pre ordering on its left. So this is also complete, so it will call preorder on it. Right? Know what is in right, right Is this emptory consisting off to Lourdes route is this norm So it will first into route and call preorder run. It's left, its left is empty so it returns immediately and it calls preorder on its right. So it's writes route is tool So it will first told before looking at anything whether I have left or right, it will first print itself ruled that is tool and then call preorder on its left, which is no so returns and then call preorder on its rate, which also needle surgery turns for lead. The school learned on the original call also ends so you can match their. This is exactly same as this, but no Here your job is not to print the in order to reversal of the tree pretence state. You are given the preorder only and you have to construct this tree back. So how we can do that. So we know that in pre order the first nor that was printed has to be route That is the definition off reordered. So we know that it is a root this informers in via now. Our task is what are the elements which are in the left and water the elements which are in the right. Since it is hereby and resource tree all the notes in the lefts of tree will be less them. The root note and the old elements in the rights of tree will be greater than Roquemore. This is the definition of Landry's history and we have also seen that all the north of lips of tree will come together. This will come before any towers alone. Rates of three starts, So did your group together already? Our only task is to find the first note which is greater than this Little more because all the right sub tree nodes will be greater than root node and they're group together. So I know that immediately after if left subtitle left sub tree adjust then it will be immediately after this after this room so we see five is lists so we continue. Continue? No. When we reach here, we see that it's more than group. So I know that from this index on work. So the 01234 So when I d x is for I know that for land on no matter what is the how many elements are after that we will not troubles. We just need to find the index off first element which is larger than route No, we know that this party's so from one who this idea x minus one This part of the lane left sub tree and from Idenix he learned relaying very saptari. So Noah, you don't need to change order And these are the pre order You have to keep disorder as it is so you will take the original victor and you can just asked to in this is like from index one. Who? Ah, three. So in next 123 It also dinners this for you 17 This is the pre order off left sub tree. Your task is to build a tree. So you see the bigger problem with this. This is the pre order off. A tree over ask is to build a tree. So we just build the route and we filtered. Arby's are the north's in the left and this is the pre order off left. So we have derided the problem into smaller chunks left half and raid off. So this same function, whatever was the main function we can call it on this smaller subset. Similarly, we call it the same function on in and pull temple with the preorder off rights up to rebuild it. So now the same consensually recorded here. So what? It sees that this is the first note of pre order. So this has to reroute So five is rude. No, find the first index forced element greater than five. It may be possible that there is no index greater than five in that case, right sub tree will be empty to hear it finds seven. So it knows that one police. And after this favor and before this index, everything is in the left sub tree. So it calls this function on there is one new alignment and this will again see that the first element, this one. So it has to regroup, then tries to find the first index a greater than one. What it does not find and there is nothing. So it returns. No, no. The schools, the same function on seven. And saying V seven is the first element of preorders seven has to be route and nothing here . So this cold complete No, you will see there and is the first elements or any little no friend the first index larger than in which is one. So from one to one less than this that is from 1 to 0. Decision invalid dreams. That means that there are no elements, so it will herding only and call the same function on this On this bill, Bill will to see you ve had built the street from this pre order it flame 178 favor 1 to 1 , then on the right, in until so desire. Same. So this is the approach that will follow. So let's right. The court for this first will write in C Plett list. Then we will modify them in oh, Java and Payton. So this is the same same problem being explained with the same example Fuller's begin. Oh, so there can be one inefficient way off, not space efficient way off building this. Ah, so we can create a copy of this. So this was the original rector. We create a small courtyard of this notice 517 and another cop it until and pass it to the original function. But not not real space efficient because we can use the or is no director itself, Onda, we just no need to know the start and end index off the subject because these or drink will never be disturbed. You're always grouped, but let's just see the space inefficiently. That will be much more easier to understand. So if three ordered or size is equal to Dio in return, no prettier else will rebuild the route. We know that there is some element so we can bill a little and the world will ordered. Always we do first element if there is just one element then returned the route that it only north else we could hear to some Berries a copy from the originals. And this people mortified because we don't need to make a copy. Here, left nodes. So is this element is less than Ah reorder Jiro, that is route. Then we pushed it to left logs. Your foot is greater than we cause to write notes. If it's a cool, then we're at group because we're traversing all the notes or we can start from one more than the route. Then we will not encounter the quickly condition. So no, we have made copies off left and right nodes and we will called route Brooks left equal to the same function. So we have just replicated what we saw in the explain is him and let's run it. Line 29. Okay, we in order Return decision Onward function is returned route. So this works. Ah, but we will not submit it since this does not seem to be If isn't so what we will, we will just create a new function and we will pass to it. The Indus is instead off making the actual copy. We will pass this index from 1 to 3. Create a tree out of this, the orders and from 4 to 5 build another and we will assign them to left and right, just as we did here. So let's create it seemed little function. Let's call it will build tree. And this will pick. If Victor is released, the same victors and doing this is left and right. And instead, off writing all of this lordy care, we will put it here and here we will return. Well, tree Geo and no, uh, let's reject. We need to make lots of changes here. So if it is more than our as we saw in this case Ah, here. If we call it on 12 make 12 route and from first index onwards will look for any value Lisbon and even more than 12 so straight of it. This idea is more than pull. In that case, it will be 1 to 0. So we have to a current. So forget about anything if it's in value. Oh, Index. So left is more than right. Then we have to return model prettier, it's We will create a route off. The first nor the first indexes will last in Mexico. Er, Motor Valley ordinances, if Liz listen are obviously less than or equal to our then their world. So they built little daughters first Nord on and it's very cool. Then there is just one more Soviet return route. For this is same mother live where we were aerating size equal to one. So that is this case. Then we start finding the first element more than forced element forced element to the right, right off first element, which is more than it more than the Roop. So while I d exists less than equal to work and preorder off, are you Dukes is listed in P order off ill. Then we do I the explicitness and then we will, right, We will call this function again. So what should be the first index forced index should real plus one. And we don't need to reword whether this is correct or not. If it'll becomes larger than our it will automatic collision term. No. And this will be called on Lee for leaf Lords, so helpless one and If I fix it pond, then I really exist. This index, the element which is more than it so we will do Ah left have drilled off one index less than ideas. So So, Bill, I really x minus one similarly right will be from Idenix still art and hopefully this work and it works list. Let's try on Ah, some more examples want to. So this will be one is the route to is the right So there should be some in between to fill the Nords, so it also works. It's correct one nil to So let's go ahead and submit. So for solace and it's accepted. So we will make it copy of this and no, we will write the same thing in Java. We remove the pointers on and in Cherry on this would be seem Ben. There is very mean, minimal difference when converting from sleeplessness to Java And no, let's see if it works. It does not compelling Inside G is not there. We need to call to lend untold Australian. Now it works, compiles and runs for over the best kisses and let's Summit and it works. So finally, let's replicated the same thing in Britain leant off list eggs. Hopefully, everything is fine. Look straight and it complains and work for there to discuss is so we can go ahead and submitted. So you see, it's exactly same in all the three languages, just some basic sent exchanges and the solution is accepted. So oh, you enjoyed Ah, the problem. You understood? Irritable. If not, try watching it again and try to write code yourself. 14. Binary Tree Maximum Path Sum: to this problem is to find the maximum part, some in a banditry. And it's problem number 1 24 off lead. Cool. And we will see a solution. Oh, in C plus plus Java and python. So first, let's understand the problem. So you're given a mind retreat. This is a man richer. You can see some negative nodes, some pointed to north so or stiffening it in both our lord and you have to find a part and the parties the continues. But you cannot have to 15 27. So this is one part and yours included. This that kind of party is not a lord like this. So does it really don't matter? General Three north apart. So part should be like this. It can be straight line. It can be one more, but not like this. So in this case Ah, the longest. But is this one not longest with the part with the maximum some. So let's see how we can find that. So if you remember the question on finding their diameter of divine retreat and there we were finding what is the longest they're the nose enough longest means the number of lords on that part and that we called the diameter of a tree here the notion as lately change instead of current in just the Nords, we will count Dear values. Here's the count does not matter. Some off their values and the party matters so you can see some similar tear. Although that problem has been level as easy. This has been liberalized hard, but I see that the concepts are very similar. So there are three possibilities. Just like this are diameter calculation we heard considered three scenarios here. Also, three sceneries or possible water does in our use, so decisional this is left of tree. This is it. Very tough tree. So first scenario is inert. Longest part lies completely left of tree Or let's call it even Tito Seconds interviews their their longest. Some part lies completely d to 39 years of dirt. It passes to the group. These are the only three scenarios and you have to include at least of unknown. So either that Nord we lane left right or we have a longer part. So these are the three scenarios all included in forced to kiss. His route is not included, so you can literally see records and happening here. When we're calling Max, impart some Let's call it impious. On route we need to take or just in this left factory, excluding everything. Even. So, what is the maximum off impious in left sub tree. Oh, and we need to also take a case. Where What is the maximum or some part in the rate of tree? And what is the 30 kiss? Not that part goes through route in. These two cases were just taking in this part. And this part on Drew is not interested in the third case, rupees included. So a while calling tricker simply for left and rights of treat we don't I need to just keep track of what is the value returned for the maxim But some We also need to keep track of one more thing. Just like this diameter case there we kept track off What is the the best part, including the root here we will keep track off What is the maximum part? Some. So when we're traversing left, we ever this value And when we go on, we keep track off. What is the maximum part? Some that they can get Ah, including the So it will be a straight path. So the case where rupees included this left parts of Mr It should not have any branch go that well. Well, it the definition of part. So we're just considering 30 case. These two cases are here, so this should be straight. But this should be straight. But it can be like this. So from here you can go left or right, but not boat. So no branches desire on continuous a straight lines. So we need to keep track off such kind off linear parts in the left part and write us. So we will ask one additional variable. My reference. Let's call it it. Call it H one, then it's too. And ah, here we have to include at least one Nord. So, no, once these two values return, let's say this. MPs left returns and even and it is very true turns d to and the maximum length parts, including routing left sub tree. Ah has a value of Phetchabun. And in Rachel's tree, it's each toe. No word. Oh, no. We keep track off when we need to keep track off for what is the it so decision tune look included, and this is It's too and even will be the what's limped in this part. And you do lose up Arthur Linton this part excluding the route. So when the call returns from this value, maybe this was called from some north table. So we need toe update the It's for this that is including this. Know what is their deepest, most valuable parts you can get. So there are a few scenarios. So let's severe considering for this mold, this is Let's left sub tree Mrs Rates Up Tree. Let's said this, it's one isn't negative. Let's exclude the value off visible for no. So what was the street parts? This isn't a good deals on negative. So will you add Everyone is too and this route Well, you're will you just add little value. So let's see. It's to export it to Then we know that if the air dis route value and this it's too, then we will get some better. It's so initially it was this. Whatever is the value of route, we have to anyhow include this route value because we want to find a straight but including this more so its values included. Let City no, you will think that which side I should pick. I cannot choose both side. I'm just finding this one sided it so either left or right with state. I will pick the max, whichever is greater. Let's say it too is greater than actual been very simply every places to no. If it's treated list, let's say less than zero then adding it to this does not improve our height, so we will not included So. First we will pick. The maximum is when it's too and visually larger. We'll check if it's larger than zero, then we will added to the route value. And that will be the It's for this case. So it's ability Max off. It's one is two or zero. Some may be both are negative. Then they will pick a zero and we have to mandatory. I heard the route north value. So this Alloudi, it's for this new world for which we have covered elevating MPs after left and right calculations are done. And finally, what will be the return value for this north? It will be the maximum off B one This first case or B to the second case and the thirties believe inert. It goes from group. So, uh, it was to route. So we have to include, well, bliss if, in part case we will take this it it's one and this it which is It's true. So if this is included, the epic and now we will include Adjumani. Settlement is more than Joe, so it's one ordeal Max off this this Maxwell's It's 20 So we have taken the three cases. First kiss, second case thirties we're route is mandatory, and these it's when it's tour or snow, depending on whether they're greater than Jiro or not. If both are greater than you, very good. We will take this part also this part also Andrew. They will get in this part and we will compare, which is maximum among history. So I hope it's clear now we will start implementing it first in sleeplessness. Then I will modify it for Java and Peyton. So this is a village that we're keeping track off, and we will pass it by reference alert to define helper function and be some and wavy returning into mean instead off usual deal because if we're taking for current mold and left are dis completely negative. Uh, so are chemically at the leaf mould. It will call it call for its left, and it will, you know so it will return zero so they will pick, which is maximum the current Nord or the left part. So we will always speak zero in that case. But that is not the case. We have to pick at least one, or even if everything is negative. So that's why this in terminus required otherwise. We zero. It will work for parts two cases, but if the answer is in negative, then it will fail and then it's on equal to zero or into me in here sort of member. This logic here are the it's for current, nor will be either. So this node we include, then we see oh, the max off It's one orange to hold you Max off. Divan did, too, - And let's straight. It works for the symbol case. Let's take this case so it's also giving a review. Often treat this safe. This was not earlier. Deciding is a new feature. If you rate the nag's, it will draw the tree also So this is pretty useful for defining your custom. You two kisses and it works. So in this case, it's minus its 42 and ah, let's stray one negative case well minus one minus two minus three. Same as this. So here it should read minus one. This is the largest. We have to include at least one normal and it works solar. It's word and some. And the solution in sea placeless is accepted. And now we will write it in Java. So I will copy this part on and here in orderto passageway value we cannot pass, isn't it? Will be positive value, not reference. So we need to possibly reference. So we will be using at all making teaser. Ah, and here also will pass a ptarmigan. Did you? - Oh , it's honest to will not compare wearily to get its value aan den and let's tray food walks andare renter matches for let's submit and the solution it except reading job as well. So finally we will do it in Brighton three. Oh, so here passing my reference will be setting variable in self itself. We will call it MP some if group is none Oh, if wrote is not always it understood. - Before calling it, we will see itself not its equal to minus matador. Ah, Eunice. And once it returns, this is actually a Pritchard and we will store it in a very belligerent similarly. And then it will be Max off. Maxwell Sichuan is too. Guettel. This is north. Then on here it will be, Let's see and it works. So let's go ahead and submit. Oh, want to treat our artistry? Okay, so here it was a mismatch. Let us see. Oh, this is playing. Root is non village in this health Northwich two unequal to self promote which Okay, we're not setting. It's This is not used sort of the self mortgage and this time it's correct. So police it should accept the solution. So it except this whole isn't quite inedible. So hope you understood this problem. The main thing was that there can be three possibilities or the ah max impart some lies completely in left sub tree or completely in rights of tree. In both cases, route is not included In third case, it passes through the route and they're also it can remote will scenarios. It includes the group that is mandatory. It can include or personally left or right part, so just to go to it and it's very clear. 15. Valid Sequence from Root to Leaves Path in Binary Tree: so tradition data to you. And the problem is to find given a string. Whether is a it is a valid sequence from room to leave. But so let's take one example. Then it will be clear. Let's say you're given this mind retreat. You are given a binder tree always so it will have just to change left and right. And what do you valued to leave part? Let's take this part gentle one Joe one and we have reached the leaf. And this is the oh string that you will be given. So you were given a tree. You are also given history. You have to just return whether it's valid or not. And varied part means you have to go from route all the way up to lease. So it may be possible that you are given Jiro 11 That's it. Like this case General 11 So you will see Yes, rooty geo. So it's fine. I go to next index. It's one I see with the left or right off rupees. One or not right is not one but left his one. So I come here and still it's valid. Then I go to next index. I see that next we lose one. So I see whether left or right off, this is one or not. Yes, it's one. So it come here and then very stand. So we will conclude that reactor was the entire area and we did not find anywhere. Listen, we always own some gold which satisfied it, so we don't have to return through here, but we have to return. False. One ad is no tickets required here that it's not only valid, but but it's a valid part from root to leaf. So this is not a leaf. It has two Children, even if it has one. Children. It's not a leaf, so for sticking dirt this or were traversing this area. But Terry, it should not violate at any point of time. You should have at least one solution, whether in the lifts of three or write Saptari on. The second case is that once you reach the end of this, I need to matches with enormous the tree, so there should always be in Nord, which will match given value. When you are here. It will match the Roop first Index. It's unimaginable second in next you should match one of the Children off Group toward Index. Oh, it should be. Nor that third level of the tree and so on. So if this had five numbers, then this would have It's morning Nordex sister level and that nor should be lease. So this case is true because we re still live and rotary still end So 1 to 1 Here, let's see this example Zero Yes, 00 Then we have eijiro So why not the north side? First level should be Jiro. Yes, we have still valid. Then we have one. So one of the northern one of the Children off this nor just any north but in this branch only so one of the Children of this Jiro should be one. It's not so it's violated here. So we return false. So all three are due to different region. There can be Let's take some more example. It's we have flame than four. Then two. Then one earned six and viewed given just flavor. So again something we match with root. Yes. Then we every stand. So we check if this is leaf or not. Clearly this is not leaf. We did not find any Miss Mitt in the value. But we found that when we have traversed this list, we're not yet released A leaf mould. So we returned falls and we chicken left or right boot. So here we will be given a function is valued sequence. You are given a route pointer to root of the tree and you were given a list. So what things we need to take If root is no their digital, these inordinate then we return. It's a sort reason Jew eso If area has some elements and trees empty noted there is no normal then clearly it souls. If trees empty, that is there is no note over disappointing to know and you are given an empty list then also you have to return. True. This is the base case. Other ways. We need to check the sequence in both left and right. Maybe it's not in the left margin. Right. There is a sequence, so we will check. Ah, one condition would be their teeth. So we need a helper function here which were be able pass one index. Let's call it the office. Since we were doing the offense kind of approach here we do the offense. Still we find one where listen or mismatch in value or released the leaf mould. And this area is not finished yet. And we returned back to the calling Fenson and we look for other possibilities. So this approach is called the Left Forces or the effect. So let's call it the office. We will pass route area and also one index. So what will it take if Erin next that is the value in their air Dis index is not equal to value off route. That means there is a mismatch, so return falls. If this is not a case, that means current element matches with the Good Lord. Then we take if RDX is arid or sage minus one. If it starts from zero, it means it is little last number in this area. Then we check if root easily for not so. In this case, we will check if this is a leaf or not. If it's leave, we return. True else falls. No. What is the next condition? If this is illusion also satisfied and it's not a it's not the last number in the list, then it will be some middle number in the list. For example, 1011 Then we may be here. Lady, you're one. Somewhere in the middle. Then what? We need to to check that the current North should not really first got here were not released. And so it's not relief. So it should have either left or right chilled. What sale? We don't don't know. So we will check. It can have both. But at least one child should be there. So we will take it. Your foot has a left, Sailed. We will call this funds and recursive Lee on the left child. And we will incriminate the index Way one so that we look for all Landis's beyond this in the left child, the same function. And if it has a Rachel, we will check the same thing in the right channel. We will pass the routed or trait, then same list and inexorable increment by one so that it looks from next index on worst he learned. So if any of these branches it finds a valid but and while it But we live in very stand of list. And also Elif Donald Then we will return. True, so Let's right the court for this It should be very simple. So dear, the three examples there disorder that I sort of representation. And it also says that we can use the first search approach solar to begin. So if not route that digital personal then return other way We will write helper function. We'll call it is valid and tree Nord start route better off int and one index And here we will take it The route well not equal to here Are adx return false And here we will call. This is valid here and we start from Jiro the first element of this list. No If so, they lose nautical to hear our ideas been returned falls there is a mismatch. If that is not the case, let's look at other case if I d xy Quito here are not sage minus one. That is this is good last number off this list then we have particular that this north should also be leaf mould. If there was a mismatch, we would have returned. That means we have a match on Lee thing. No, we need to make sure that this norms for reading leaf left is No, I better not here and not route. Right? If any of these conditions are false, that is. It has a left or a child or boot. Then this condition will be false and it will return falls. No. What is the next condition? We did not find a mismatch. And also this index is not the last index. That means this index is somewhere in the middle and our value matters within Lord. Then we will make sure that then that means that this had some totally at least left or right. We will makes your that there is a valid but either in the left or right sub tree nuttall So return We will learn to conditions first is dirt left? Is there not left to root lift and is valued left here? Are I really explicit one or so? If any of these conditions returned true, we will return True. If any of these return falls, we will return for us and we're done. So let's straight. Ah, some spelling mistake and two works for this condition. Let's heard other ones Judy ribbon and Jiro one when the tree will remain the same and it gives a review of the Tree on Digital 11 and you don't get over both of the sort of the falls and our answer matches with expected true false falls. So let's go ahead and submit, and the solution is accepted so we will write the same thing in Java. So I have cooperated on and basted if equal to normal return. Every North leant equal to zero, and then this handlers straight. Ah, bull Children, William. And it works in your wise well. So let's word and summer. And it was The solution is accepted in your husband. Well, it's finally submitted in my country. - Salute Seafood compiles complaints or not. So we have some. Sentimental is well, it is not defined. Noto works and give the correct answer. So let's word and summit. Another problem is accepted. Our solution is accepted in Britain as well. So I hope you enjoyed this 30 day off lead quoting challenge. Every day was a challenge in itself, and it was fun 16. Cousins in Binary Tree: to reveal Sealy Corp problem number 9 93 And it's called Cousins in Mine Retreat and we will see a soulless and visually based on depth first search. And it's time complexities ordering. And we will not use any auxiliary space for that. There are other solutions, Coalition said will know where we can use but forcers or we can even have, or the street replicated locally in the form off or the parent and distance from the group of each Nord. So we will refute. Discuss does ah solutions edible. But we will mainly focus on their differences based solution. So first, let's understand what is the meaning off origins in the mind? Retreat. So you see this mind retreat? This is banditry Every nor has it at max to Children. Oh, so if you see, look at 23 Did your siblings there are the same level and we will start our level from route or what will be our level? Jiro next will re level one. Next will be level two. So the Children off any north are you one level more than the parent nor no. If you consider two entry Ardeche regions No, because they ordered the same level. So for cousin, we need levels would be seem and parent different these other two conditions, So you're literally seem to entry. Both are level one or dear parent is common one, so they're not cousins, so it will be falls. Now let's see. Two and six are there. Questions are to spare into one's experiences. Trees apparently different but very little serve also different levels of regime, so this is again not bear off billions. Knowledge C four and six are because ins off first condition is. Are there several years for and six both at level two? Or do they have different parent looks like because parent or four is two and parent of six history, So both conditions are satisfied. So four and six are pigeons. No, no. What approach you can pick. Let's say you have one single Bindra tree and it will not change and you have multiple queries coming in for a while. Such pierce are these cuttings or not? Are these cousins or not? Let's in. Thousands and thousands off queries are coming to you based on a single by and retreat. Then it would be ways to store the information for each north in a dictionary. Well, which can contain no old and the values can contain level. And I didn't beard. So once you travels this tree in whatever manner you want the offense Serbia eaters you built this map so know this man has all the nodes and your level and parent earned in four . And then whenever the query comes Oh, this north can have the living digital value. So when a very quick ums are two entry off cousins so you will find this value for two you will see there for you It will be one comma one. So it's the level honest Their parent is really for you, for treat will be ah one comma one. So you will fit these two in constant time and you will sick ill are same beer also same So it's not. Then a query comes to common six. So for good will be once it 11 for six. It should be level should be to parents or bitty. So you will see that levels are different so you will return falls. So if that is the scenario that will depend on the huge casework algorithm you follow. So it's the algorithm is like that same mind retreat, but multiple multiple inquiries off this, then you're usually go for this. So this will be ordering time, this building the map and then all the subsequent queries will take Worf one time. But if it's given that Oh, you will be given a tree and because in pairs or in north appears and went in tow and you really just are the questions in this tree or not every time you get in Nutri. So this is Stephen. Next time you get a different tree on different or North appears and two for a second example. So if this is the scenario, then you don't need to store these things in a map. You will not make any use off. This will be used for just one query so you can save a space here and Judy afis. And that would also be leaner thing, because if the treasures changing by storing them, you're not getting anything you pick or and time to build a map than over in time for queries. Overall, it will be over in. But if there are much pulls off query based on a single tree, then them or paste the Everest time. Little subsequently substantially reducing this kind of approach. But in our case, looks like the test cases will read three and nor repair boat. So it's time you will get a different tree. So I thought it would be good to save some space and they will follow. Left for search. Uproot. So what approach will take? Oh, you're given is work more and were given to other values acceptably with Geno to Lourdes in a tree. And we have to return true or false, depending on whether X and y you're cousins or not. So what we look, we know that this is the main Folsom. Yes, so they know that rupees that level zero and it's Children will be its two Children at Max because it's by Henry will be at level one. So we see if the roots leftists present. Then what we will do will compare it any off. These, if left, is equal to x er by. You're not any of these. So is it's left emigrated idyll, Elliptical, Do X or not, and by discomfort vision. We're comparing the values in the court will write slightly differently. So is to equal toe this or not. Let's take a concrete example four and six. So is to equal to six or not. If it's equal, then we will update some value. We will have one level DX doing and these air holding the level values. Ultimately, we can have minus one. We know that minus one level does not exist. It starts from zero. So whenever we find, explore way is evil. Appreciate these values on duplicate, sir, not a lord. So this replicate Ah updated only ones. So if we find anything, they will see what is the level off the Lord that we're comparing? So it will be one more than that because when we are given Nord become pair. If it's left values equal to X or not or it's left well is equal to write or not similarly for right so it's little will be one more than the level of this. So we will create a function if one where we will also pass the level we will pass a route x and way. Then we also pass one level and poor route. It will resume so these ticks we learned here its roots left is there. We compare if left is equal to X or not. If left is equal to X what we do? The X equal to ni plus one So these the level off current Nord ex current Nord our route So he's reformed ex update their dicks also PX one parent we can keep What are the pattern sauce ex anyway? So we need four variables DX dy right Be experience or DX dy nor the level off explored X and Y you're logs Levi denote the level off Why, you note the X Denard parent affects no b y denotes patterned off whine are very simple. And when we're Travers industry and whenever we find X or Y, that is any of these notes we have did the Chris morning level and parent and its parent will be ruled similarly, we can compare it elliptical two way and two more things right is equal to X and right is equal to why these are not four cases. So whenever we reach any note, we see Fritz left critical to X or left physical two way or a very difficult weeks or write difficult away in all the four kisses the parent will be this nor the current known that which were visiting at the moment and ah dear levels the XRT Very, very one more than and ultimately when we operate all these four values will be returned from this function Anim parent, we compare whether the X is equal to delay or not and P X is not equal to be re and we will return accordingly. You can traverse the complete re but we can return prematurely. If we see that all the four values have been objected then we know that we hard we have found both the value somewhere in the middle itself. So we don't need to. There was the tree further salutes right the court for this approach. So for sterile rated in sleeplessness So each cousins is the main Folsom I will create one function avoid and we'll call it parent and left because you will be calculating the parent and left us these x and y nodes Onda, we will need thes three years and additionally we will pass if you will use where your reference bx do it Fuchs and you see their care parent, I am taking as interior because these notes have a value in teacher values and are duplicates are not there. So we can even compare their values and what else we need. We also need one level. Let's call it neatly. And here we will initialize those values in Vieques he called a hero you eagle hero in the X, equal to minus one into view equal to minus one. So these these are on initialized and we will get to know this from the value because minus one level does not exist in entry. We're starting from level zero, so it can be dear or more. And then we will call this function Aaron Dentist root exploit level for Ruthie zero then dx 1st 3 person D then p d x b way bx yui and then live in return. Be excellent vehicle to do it and b x sort not recall do viewing. So this will return true when both these conditions are through. Now let's fill this main function the auxiliary function that will do the main back in job please Israel artisanal, Then return. If route left that is left, there'll exist. Then we compare this left, busy cooled with the rex or way. Then the parent of X will be this route and libolo sexually B plus one level off current mold Li plus one else. If b boy, we will be ruled well and Dewey equal do need less one and we will do the same thing for right. And then what? We need to check if boutiques and why your farm. We don't need to drivers for the just return. So if dx not equal to minus one and the d we not equal to minus one, then return. We have four, Noble told them. Otherwise we will continue our search So d will be one more than me because we're doing it for it's still don't know Lift earned right and these should remains him under to let straight. It works for this example. Let's some mittens seafood Possible latest cases on the soldiers in it, accepted in C plus lis. No, we will do the same thing in Java and then Peyton, The logic is very simple. It should be clear. It's exactly what we saw in the Slade explanation. So here we will use atomic indigenous toe positive value was it? Wait a friend. Sorry. Otherwise if he pauses, entered really positive as value Onda sued remain team Then you can also cook these DX Dopp Experian as I remember very well of this class natural to work and if root equal toe don't return not cultural He exes atomic so we cannot assign it in Teacher, we will need to assert it Earn beaks North shirt Ni plus one So let's try it And it it's grips alert summit also regard some wrong internal POTUS Falls Okay, maybe due to this in the X normal it So let's copy this Just kiss We will run first on drone on this false, true, false, true annoyed mentis at least for their discus. Let's omit so in the previous cases we did not our compare this get it was always giving false because dx dy way are two different atomic indigents who it will always falls and our answer will always be falls And the first just case The answer was false that that's where it was matching. But for other test cases it was failing. No, It works in Java and has been accepted. We will know right The same thing in Bytom. Exact same logic, just three different languages. - And here we will put it in self itself. - Let's copy this thing. That's really much easier. - So , nerds, let's see if it works and it gives correct Rachel for bodies. Just kisses Solarte Some of the solution in Brighton three and the solution is accepted in Britain as well. 17. kth Smallest Element in a BST: Today we will see how to find Kate, a smallest element in a bind research street and this cake and we'll any fixed number. Also, it can be given, like for the smallest element for the smallest settlement. Or it can be given a General Kato smallest element. And here it's not a binder tree you to buy and resource tree. And we know that in buying the surgery or for any norm, if you look at the group, you can look at any other Nord. Old elements in the left sub tree are smaller than this root node and all elements in the rights of career larger than you. So here six is larger than five and ah in the left sub tree via 32 and four, so all of them are smaller than five. Similarly, if you look at three, you will see that in the left side. It's too. There are more elements. These will be smaller than three, so if it has a left child, it will be one or it can be smaller. So here, also its properties valued on the right side. It's four sort. This is larger country, so how can we find its smallest elements. So we know that if we do in order to have Ursula for by interest, Sastri than the original that is printed is sorted. So what, in order to ever senators, let's see tone an example first. So first we will understand in order, travelers, if we know in order troublesome than this problem to re very trivial. So in order to ever soon for a root means that first do in order to reverse a loss A route Lord left this left dorks the root off left sub tree. So all the north in the left sub tree ville revisited first. So vegetative, everything here then visit five, then visit everything here There can be a big three year also. So then, after doing this, after this call completes this will again call it call for its left and right. So once this call terminates, it would have printed all 32 and four. Then we print a route and then we do in order rules. All right, this is the in order to reversal. So after this returns, it would be printing do three and four in some order than we will print five Then we will print right sub tree which is six. So it will call for three. So what we will do before printing three through the Nord reversal off left. So it will come here. Here, left and right Er no So left will return empty All right. And then it has to print itself so it will print too. Then it will do it for rights up traditional so it will not bring anything. Then it will return to the calling function. So three had called this so the call has returned from the left sub tree of three. So it will print three Now itself the route. Then it will call it for the right sub tree which is four. So four will do it for left and right which colonel for left it will do. It will be null return than print itself for for right regional and then return back here. So this all the greetings have completed a tree. So this tree will again returned to five. That I have done my job. No, you can print yourself so than five is printed. Then it calls in order for its right sub tree, which is rooted at six. So what six will do? It will call for left sub tree. But it's no. So this is done. Then you'll print itself, which is six Bennett will do, or in order on its right with the alternates adjutants. And finally, everything returns back. Tudo ups tech And this is the result. So you can see this is sorted due to this mine decides property. And if we are asked to find turtle mint, it will be third from the left. In this in order, Traverso. So one will be that you do in order to complete in order to reverse it and then story in Harry and and bring to the Kate Element. But we can do some optimism here. Once we have, we stood three nodes that it wants. This print is called for three notes. We stopped there and return that element. We keep track off account. So every time we print the sprint drawers that were done with this element, I mean, we have restored this element this milord So whenever we're printing instead of printing here, we will not be printing it. But we will be just incriminating the count instead of print. So when you was a war to print, we really here. So we make Kontic will do one when it returns with drink three. So instead of printing three b, make county cool too to then it calls for its rights up tree and here left signal. So we want to print for But instead of printing, we make article two three. So every time we're printing it instead of printing, just incriminate the current. And I heard it take that is going trick or two or in general, in our case, it will be key then returned this value this will be the result result will be this route wrote value which were which we were printing here and we don't need to proceed further So this will terminate when become Then the current becomes k smooth If there is a in order travel Salafis tree and it's a big three and let's icky lays here Then once we have printed it, we will stop So we will only visit these many nodes so the time complexity will be ordered in. So let's right the court for this first real right In order to reversal, then we will mortified, but seeing the not much modification is needed. So let's very didn't see business first. So they're also building or this in order to a person. But we will not. They take this route that is mortifying the Beastie Notice structure. We don't need that salutes aerated. So we need to keep track off count. And Richard So we will create another function and we need to pass count and riddled by reference. Since we will be doing recursive calls and all of duty recursive call should have access studio Ah, global value off counter and Richert. So we will be passing. It may difference. So if left is there, do this for left. Okay, gaunt and reserved and then hair of your print route Little north of El. This would be originally in order to reverse. Instead of that, we will just keep track of how many elements we have printed. We're not actually printing, but just keeping track of the count. And if count is equal to okay, then we can stop her the result according to count and also return from here and do the same for right. - So let's stray. So it works for this case. Let's try the 2nd 1 which is a bigger example. Case three, and it matches The expectations is so let's go ahead and submit and regarded wrong into yes . Oh, this looks a bit funny. If confiscated and regional should not become to, it should be Rule 12. The value it's we were printing. I sort of had this soon. Let's straight to summer on this all. Isn't it accepted in C plus lists? Sorry for that mistake network Is Saleem sticked? Now let's do the same thing in Java. So here we will use it on making teacher, since we need to positive reference to get the intention value stored in atomic interior we use get and it's returned I present. So we are returning into on and result of these atomic in tears over even certain certain certain it's solar TSI. The count is, ah, comedian teachers nor distant teachers, so we can do counted or set equal to in conduct set. We can rate condor, get less one, but we have it really made songs on lean atomic interior for that, so it's get earned improvement, another ridge increment and get so looks like similar toe plus less something or like let's miscount or conflicts Lis. So we will use this ready made function here. Let's try again And this works as expected, Solarte Summit and the soldiers and is accepted in Java is will. Finally, we will do it in my country. It's nothing but just to in order to reversal with slight modification on here, we will put it himself. We don't need Tom 10 results, since they're presenting the self itself so we can get it from there who alerts summer. And this whole visit is accepted in by 10 as well. 18. Invert Binary Tree: Today we will solve a very simple by Nutri problem. It's lead Court 26 it's called in world by in retreat. So here you are given and bind retreat and you have to invert it that you can as you immediate keeping middle ear. And then whatever is the left becomes right and right becomes left. So let's see an example. So think of it, that dirty meter here. So what will happen? We will have five years and six is right so six would become left, then reveal become right and on three, also to his left. So it's far from the mirror. If you see in the mirror, the farther objects that will be for during decide also who will come here and four will come here. So you see that whatever is in the left sub tree has come in the right sub tree, and that is true for all the notes off the tree as well. So if you look at just this sub tree, then it's imported as well. So how we can do that? Let's see. It's a simple problem of rickerson, so let's call it I d for involuntary on route So what you will do first you need to do that . Oh, call this same functional left sub tree since you see that all the sub trees are in mortared as well. So we will call ah route dot Right equally to 80 route not left. So whatever is the left left is this one it'll dot left Just call idea on that and it will return. And no tree node or it will return the new norm. New rule. So what? Do what he's doing in worded form of this sub tree? Make this It's right. Sub tree root is here, so it will invert it and make it this three for two. So we will make it right off this. So we get this and we need to store left somewhere so temp equal to route left. So store their left in somewhere and then in fact, store the right since we're updating the right not right. So we have saved the uglier right and whatever is in mortared sub tree off left sub tree. We make that right. So this is the state No. And then would not left equal do ideals, Whatever value we had saved their right and then return. So how this will work and I hired an ill take care if route isn't little, then return fruit. So let's run the court through. Any jump in the route is here, so we will call in war tree on fight so it will save the right. It will do analytic. It will not return. Since it's not Colonel, it will store right equal to six, then five dot right equally to I d off to this mold. And again it will perform this knowledge IQ and a store right equal to four. And, uh, do you dart right equal to 80 off to And what is the invert inversion off this single? Not too. It's too itself. So it it's no becomes three dot right is to So let's android here three it's right is to them this link terminates. And then we called $3 left equally toe idea off this rate which we have saved early, right, which is four. And what is the inversion of this single note for itself? So three dot left is for now. Then this call also returns. So this, uh, returns the new route with history So this line returns and five dot writers dishneau so five door try to become scientists. And then after this thing returns, we will write $5 left equal toe I d off whatever right were saved, which is six. And what is the inversion of this 66 itself? So they too become six $5 left six. And finally we will return a route. So this new duties in return and makes your darkness is then voted for him This. So that's how the simple rickerson works. So let's write this same corden R C plus plus Java and Peyton. So if not route return route Ills dream Nord star right according to rule, right root of right equal to in work tree look left on the route left equal to in work treat right and return route So let's see it works So let's submit And this all isn't it accepted? So let's see, it takes just a millisecond and memory also is good So we are right here at the top 100%. Similarly in terms off looks like Gaby other it point for MB So we are somewhere here. This is 9.1 nb close to decisions. We are stopping to himself order in time and memory. No, let's write the same thing in Java and Peyton. They're too, and it works. So let's submit. And the soldiers in is accepted in Java as well. No, we will do the same thing in Fightin Tree, and it works. So let's submit and the soldiers any accepted in Brighton as well. 19. Search in BST: in this problem. We have research value in a bind. Resource Street. So this is the classical, uh, use case off searching them by and research Street. No change is made. So here we will look at every cursive as village, a creative approach, and both will depend on where the North is located. So if the North is located very deep, then that will depend on the number of nodes that will like before that. So height off the tree from route. Till that no, not will wither time. Complexity. So let's see Buddha Pretty first, we will look at a recursive approach. Then we will look at the I traded approach. So let's say we want to search for three years and this value may or may not representing the tree. If it's present, return pointed toe that mold. If it's not presented in return. No, we do not find it. So let's say we have to find three. It's presented, so we will return this point and you are given route off the tree, which is the usual case. So you have to implement this search. You were given the route. You are also given value so here we have the values tree. So what we will do Well, check if your duties in the Lord Not so. If a rule is no, then we can't do anything. Return. No. If route is not know, we will compare its value. It may be possible that the root is holding that value. So if fruit door to them is equal to this world that we want to search then returned route next. If who to dart well is more than vent. That means this route is more and in buying research, tree everything in the lefts of trees smaller than route. This world's true for all the routes all the north. So this route values larger which is the case in our case. Also five is larger than three. So we know that everything in the right sub tree it's larger than fruit. Fruit is larger. Everything else here would be larger. So we're strictly served in the laps of tree. So we will return search root not left and the value else return Search wrote a note right on value. So that's it. So it will call search on this Nord again. We will take you through additional or not. If it's marginal, we will take your first values equal to this value or not. So it here it will match so it will return this value treat. Let's say we want to serve seven. So what will happen? We will see. This is not equal to seven its value. So we will call the surgeon. So we're calling. Search on five is the world and seven is the value. So it will call search six and past seven. And here it seems that six is not equal to seven, so it's a smaller so it will call when it's right. But it's right is no so it will call Search No. Seven and when this call is made, it will check whether this first perimeter seasonal or not, it will be no. So it will return. Now that is, we do not find seven year. So this was the recursive approach. Let's look at the trade your approach, so let me know. The treat was 53 six and to run full. So again, let's say every function ege search root carnival. So we will have a tree node, couldn't we will initialize it toe root and why current is normal if current inal That means we have reached the leaf mould and beyond that And still we did not find that value That means we have to return No, we do not find that we never look at two notes at the same level in the search. Either we go left or right we go left So we're not searching anything and write similarly here We will take anyone off the branches and ultimately current will be criminal So current is here we see if current dot well is equal to well then return current we have found and we have reason They're Nord, so we return it Els If if current daughter well is more than well then what we should do? Karen Dorval is more than three that we want to search so we know that it cannot be in the right sub tree. So we sift current ear current tickle took are not left Ills current equal to current adult Right. So here there is no rickerson. We have a value and, uh, of your trading till current becomes no or we find the value. These will be the two scenarios we can find somewhere in this case, Karen becomes three. So next, when we reached the beginning off the loop again we will compare. We will find it and we will return it. Else we will return No or current. Both are same. Since this will end when current becomes no so dissolute Casement, we do not find No So I hope boot recursive An active approaches are clear. Let's look at another example. It's it's heaven. So current is here. It's less than value. So current becomes current, Not right. So current comes here again. It does not match so again current not values lous. So current becomes current dot Right for its right is no so current equals Do six not right and six note right is no the current will become on this Look will end and we will return Well, that is We did not find seven. No, let's right. The court for this injustice was Java and Peyton. So first we will write the recursive approach. So yes, north route return not a PTR. If we found the value, we return it. If route is greater than well then return left and well, if none other two cases are there, then that means this is more than this is less than well and looks see. So it works. Let's submit and the solution is accepted. Let's look at the time it takes. So it's not that great. It's around 13% only, no, we're at 45.53%. That is at the main distribution. So these things are random. We jumped from around this region to this region very quickly with the seams of missile. No, let's write the a creative solution here. Let's coming toward this part. What? We can also return current, what are same and this attractive tradition. He also accepted No, let's write both of these solutions in Java and by 10 as well. - And this whole reason is taking Jiro Millisecond. That means it's better than all the solutions. We don't have enough some essence, anything with submission early today. So this is the best solution. It takes zero milliseconds, so you cannot beat that. So let's see Inger life. We make it recursive. There is your difference in timing or not. Let's come in this hold. So in general, iterative solutions work better than recursive in the time complexity is similar, and we can confirm it, too. And it's recursive also takes Jiro milliseconds so we don't have enough distribution for run time. So this is the test. Cases may be quite small, so that's why both recursive and I tripped. You are taking zero millisecond edge. No, we will do it in Peyton and despite Gonzalez and takes 92 milliseconds. Finally, let's try the recursive for a reason, - and it takes 96 milliseconds between fighting. It's taking it. But a lot of your time, man in your boy, it's taking smaller time. 20. Count Complete Tree Nodes: in this problem, we have to count the number off notes in a complete mind retreat. So first, to understand what is a complete by Nutri and by in retreat as the name says it will have act next to child. But complete vendor tree means net. All the notes help to child except the North's at second last level, they can have one child, so there is a complete ban retreat. But this is also complete monetary. Since all the notes have two Children on Lee at last level, the notes may not be complete. So here we can have maximum one note next north. Next level, we can have two notes and next we can have four nodes than eight and so on. So it's to raise to the power level number if we start from level zero. This is the number of notes on that level in a complete ban, Richie. But this will not witness may not be valid at the last level. So this was a complete monetary disease als a complete banditry. This is also but this is not a complete of energy. So last level can have incomplete notes, but this would be as left as possible. So this is not a complete ban retreat. But if we just a move it to here, then it's a complete energy. This is also complete mandatory. So all levels careful except the last level they're done. Notes should be as left as possible. So this is another example off Complete ban retreat. So what is the tough job in counting the number of nodes? Any simple travel? Salud work. But here we have toe optimize universalism so that we take advantage on the completeness off three. So even if it's not complete banditry, you do it reversal. Then you will get the number of norms. So here it's complete. So how can we explored this condition? So we have to use this logic not at level l. There will be to raise to the power a number of Nords. So if you complete banditry had just 21 level, it will have one note. Let's first talk about the balanced case where everything is food. Then if it has two levels, then it will have three notes. If it has three levels. Yeah, here I am, starting from one level 123 Then you do love seven lords so it's equivalent to writing and by and representation like this. So one week it's one two bits. It's three tributes It 74 Bitch, it's 15 and you can see that if I feel this level edible, we will add eight original lords. So eight plus seven is 15. So what we will do, we will start left pointer and the right point. So left pointer will always go left until it reaches leave. Nor so here it will count whenever left is not know it will count. So here it's one. Do 123 for no left. Reasonable. So it says that left ideas for similarly this pointer will go on Lee. Right? So what is the way to do that? So initially left and right both our route. Then while l L'Ecole toe left keep going left and also keep in preventing count left count so it will return for similarly for right. You keep going right instead of left and here it will stop So it will return for so it will say, Hey, my, uh, left right is four right, eight it also for And if it's given that it's complete banditry. Dark means all the notes at left and the last north will be last level will be as left as possible. So if you take this example here, left would return for notes. 1234 But right would return 12 three only. In that case, we cannot applied this formula. So if we get this family, we return to raise to the power four minus one that is 15 and that will be correct. But in this case, we will not return that. So this optimism we will try to find smaller sub tree. So some smaller sub tree of this will be complete when Richie. So if we don't find that scenario, what we will do, we will add one toe the count and we will go one layer deep. So instead of calling this function on this mold, we will call it on this part and this part separately. So this hair, we will find that this is a complete banditry. So here we will a straight away return. 07 And what will this part treatem this will against it left itis to write It is one. So again it will say that I am not a complete banditry with all levels spilled. My last level is not filled. So from the right called tow this rate one again it will add one and recursive Lee call. Let me write it In this color, it will add one for Disney World and go one layer deep to left and right and it will call the same function. Recursive Leon, this and this No, again in the left part, it's unbalanced. So it will. Let's make blocks for left and right. So it's un balanced. So it will call one plus global air deep that is here. Here it will be balanced just one. So it will return one and right will return to you plus and zero here it will simply return one since there is one level and both are same so it will return one. No, add all of these So this is too so this will ultimately be too. Now this is two plus one plus one. So it's four. So for the ordinary tree, when we had a red for Route, seven would return from left, which was balanced a straight away. So it returned seven then for left, we had to recursive Lee. Call it. And ultimately we added all these and got four. So know what is the final answer? One plus seven plus four. That is 12. No, let's count it here. One note. Let me highlight it. 12345678 9 10 11 12 So the answer is correct. So what would be the way to write the court? Let's write it in. See if Littlejohn pattern and we will see what is the way to write it. Exact same logic. We will replicate there. So there's this problem and, uh, this is a sample tree off a complete mind retreat. Last level is not filled. It can be filled, or it may not be fooled. So this case is that if lt's empty current is, there is no nor didn't industry and other ways We take left and right and can clear their heights. So three note Lefty called the route right. A call to root and I left is equal to zero height. Right? Musical hero? No, for left. Keep going left. So I left. It's listless and left equal to left left, so ultimately it will exit when we reach a lift. No, similarly for right. So it will calculate the value off. Deepest Naled Deepest, right? Most know And if both are seem that is despite right of this left most node and right off, right? Most Lord, it seemed that means this Oh, our trees not just complete mandatory, but all the levels are also filled. So we will return using this formula to raise to the power height minus one. So if it still is equal to it, are return. So if you left sift one day one it becomes too. That is tourist to part zero. This is tourist to the power to Oh, sorry If you left Crypto one by one you get to that is to wrested power one, this is two rested part two. So here you have to return to raise to develop It's ill or HR boater seem minus one If this is not the case, then you had one for root and you go one lady notice recursive leak on call on its left sub tree and right sub tree. So ultimately you will find some some sub trees Really complete ultimately in the left part one plus the same folks him count towards Oh, lift Root Not left because this nor will we know this lift route left bliss going to George . Oh, right. And let's see. Oh, what these data here can't. Okay, we should call it return and morning. And this gifts six, which is as expected. So let's submit this and this Holy Senate accepted. No, we will write the same thing in Java and Peyton, if it is null returned zero there is no no. So, currently zero. So this calculated the left right, Keep going. Left height of the left, most no. And this calculate the height off, right? Most node. If both are same, then return the formula. Using this formula. Do it with Farage minus one. If it's not the case and go one layer deep and recursive Lee, call it on left and right, and add one for this route. And this is also correct. So let's submit on the solace in it except reading Java on the run. Time is zero milliseconds, which is the best among submissions. And no, we will write the same logic in fighting tree. If the vote is none, then county zero. Since there is no note industry, it's ill in our larder. Right off the left, Most node on right, most node in the tree. So if there seem that means that tree is not only complete, but all the north, Sir, all the levels are completely filled. So in that case we can simply return to restore power. It's minus one and the solution is correct. Solarte submit and the pipe and so listen is also accepted. 21. Count Unique Binary Search Trees - Catalan Number: In this problem, we have to find the number of unique mind research trees from a given set off numbers. So here you will be given one input in That means that you have numbers from 1234 all the way up to and you have all these and numbers how many unique boundaries those trees you can form. So if you remember in buying research tree this is a binary tree first Awful. Then it maintains the search property notice For every note, all the nodes in the right sub tree are more than this note and all the north's in left sub tree are smaller than this note. So this is true for all the notes in the minus history. So let's see how we can count the number off unique mind resource trees. You don't have to our put the buying resource to you. You just have to work with the count. Here is your meaning Example. If we have values want to, we can make these two boundaries a street. One is the route to with the rights of right tell of this since two larger it cannot occur in the left. Similarly, if two is the route one cannot occur in the left sub tree. Let's take a bigger example. Let's take the example of three so we will have one to three. This is one take the middle image of this so three will be in Route two is a smaller so in the left and one in the further left. Not exactly mirror, but the safe is middle remit. Then let's take one adult again when we have considered so to entry board Will Leiner writes up tree. So this is one possibility and we have seen that which to we can arrange it in two ways so you can see straightaway that we're breaking it into smaller chunks the 61 then we're left with 213 and we already know that for two numbers there are two unique buying resource trees. When is 23? 2nd 1 was 32 So if you look at just this part and this part this comes from this base case So this is we're done with route one. No, let's take the routers to then we have 123 So we will make all of the these numbers at route one other time. So we made one other route and we were left with two notes We airing them then we met this to as the route than one is in the left or the region. The right we have to make in the service property. So between Lord, how many ways we can arrange just one. And with you know not also we will have one. So these are the base cases for one note one for Jiro one. So when two its root We have wearing this in the left sub tree on. We have to arrange this in the rights of trick. This can be arranging just toe one way. This can also be arranging just one of the so only one possibility went to is the root next . Then treat the route. Then in the right sub tree there will be nothing since there is no element larger than three. So it's empty here and in the lips of tree. We have one in tow and we know that one in tow can be arranged in two ways. This is the 1st 1 to 1. Next is 12 again. This comes from this case So no, let's ticket General case. Let's say we have in numbers 123 Kate somewhere here than in his ear. So with one when one is the route, how many possibilities are there in the left? There will be nothing in the right. We will have in the minus one. So for three, what did we do? If we have three, then we can break it into one end. Gerund too. One of them, One of the notes. I will make agile route so we will have one less value to take here. So the some off left and right should be in minus one. And when is little short of the landlord's? So when we have three v up, Where'd all the three possibilities? In one case there are Jiro notes in the left sub tree. Let's we have 123 If we make one as the root in the left, we will happen Zero right. We will have to values. So this is this case. Then we will make to federal than in the left. We will have one, right? We will have one when we make Trias the route we will have to in the left sub tree These two and in the rites up tribunal Abdul. So in order to solve for three, we need the values off Jiro wanting toe Similarly in order to solve for the case off in Lourdes, we will need the solution for 0123 all the way up to end minus one So you can see that we can save this competition in some DP area off the sage off in prison. So this is your dynamic programming problem. So we will start bottom up first we know the base case stills, dear anyone So we start from two. So for two, we can make 1st 1 as a group for always the some off. These two will be one less than this since one of them is route. So for you it will be Gerawan here The some sort we want and 10 deterred only two possibilities. Let's write down for four poor Better practice Jiro three, some sort of the old history. Then 12 then toe one and three judo. Similarly for five. You can get the idea when one is the route. No, we will have deer in the left and four in the right than 13 Then, too, then 31 and finally for Joe. So you didn't know the solution from zero till four. We will get. We can calculate the value of fight and let's look out if we have a route north. This is fixed and did up M Nords in the left sub tree and in nodes in the rates of tree. All of them we have already solved, since this will be less than the value we're solving. So how many possibilities are there? If we can arrange this in embrace And this in NV's, let's understand this with a simple counting problem, let's say even he can occur in three days. Let's call it even you too Eatery, or rather even air to a tree and even be can occurring two ways. Let's say Beaven and we to then in how many ways and be both events can occur together. So we have to look at all the facilities, even if to a tree, we will be too, so it can be able to take one of these values. We will take one of these values. Total possibilities are take all communism's so even and in buttes people, then this is one possibility. Then keep even fixed and, uh, take all the possibilities. Don't be so here. This denotes this one. This one so even be too them all law absence are adjusted when this is even. Then you take it to be even. It will be too. Then it really even eight Reba treat In general, if there are in ways in which this event can occur and anyways in invest, this event can occur. Then together, taken, occurring M cross in anyways. Similarly, in our problem, when we're solving for in, let's call it f often then you remember this diagram that we have to take all the possibilities and heard them so split it into gear on four when first noted the route then when seconding nor is the route. Then there will be one in the left sub tree and three in the rights of tree and so on. There some is always for So for General Case FM, it will be, uh let's let's write it first. Then we will. Some at the some isn't so. It will be Jiro in minus one plus and we will see. What is this? Ah, then if let's call it F Prime one in minus to plus O. R. Two in ministry, there's some is always in minus one all the way up to and minus 10 So this means that there are Jiro notes in the left sub tree and minus one, not in the right sub tree, so we can arrange them in FN minus one ways and this in effigy away. So total will be multiplication of those. So it's ah if kill Dame's if in the minus ki minus one since there's some has to be in minus one so this can be arranged in F gave it on the right sub tree. Can we are engine. This menu is so together there are this many possibilities and que goes from zero to in the minus one. So whatever value we're calculating, we will run a loop from zero to n minus one, and we have already solved it since we are solving it from left to right. So over time, complexity will be for Jiro for two people need one are two calculations for three will need to calculations for four Beverley Trickle prisons and so on. Shirts one plus two plus all the way up, two in minus one. So in multiplied way in president or in minus one multiplied weigh in, there does not matter. So order and square. And what is the space we have used? We will be storing the solutions from GeoTel last value we will calculate from left and go till right and finally returned the last value since we. This was the Austin. The question that we want to arrange this many notes in boundary so street form. So let's right the court for this. So first we will write it in sleeplessness. So if an is less than toe, that is any gear or one don't return one. This is the base case, and then we will have Victor Elephant. Let's call it a swell and we're taking it, says one more than in. Since we have a possibility of diesel notes as well who? That's where you kept again it as in Pressman. And now let's add the base kiss. For Jiro, there is one way or one Nord Dairy again, one way. So there is 1 to 1 correspondence in Texas from your twin on the values direct also from here to him. So no confusion here. So this is the outer loop where we're calculating for of and is this I? And in the loop we will add all the values from Jiro till and minus what like this form. So this will be J or K, so this we would have already solves in jail. Well is the night and next is J minus I minus one so that the some off this and this is humaneness one. But it should be. I am a ninja. Minnesota. So there's some is always remain is one. So there's some some off. All these piers is always in minus one when we're solving for And so here is acting as in and finally the last value. If I will video finally and the solution is accepted And if we see the time it takes zero milliseconds, that is our solution is among the top off the accepting submissions. No, let's write the same thing in Java and Peyton on everything else would remain seem and the solution is also accepted. And it's time complexities again. Jiro millisecond, that is we're around the top of the submissions. Finally, we will write it in my country the year the base cases, then for I in range, toe and plus one and the pipes and solution is also accepted. 22. Sum of Root to Leaf Numbers - Recursion: It's another banditry problem. And if you love solving, buying retreat problems and if you love rickerson, then you will love this problem. So it says that you have to find the some off route to leave numbers, not brutally parts. So every leaf denotes apart from root to leave. You don't have to add the some off their digits, but you have to at the number represented by this. For example, this denotes for 95. This denotes 40 and this denotes for 91. So take these numbers as digits off a single number and returned this some off. All of those. So here we will return for 95 plus for 91 place 40. So whatever is this some you will return that value. So let's see how we will solve it. So let's say a case where we have just one note little five. So it had just one route one leave. Everything is want this. So the result is fight just one you via for you to then how many numbers are there? Just one again. 52. So here we will return 52. Now let's say we have another brunch one, then we have two lives. Two lives means to numbers. Two parts front room to live, so five to his one on second is 51 So total will be when you're three. So how we're solving it for us, it looks very trivial. But how you write the court for this. So before reaching any note, we will pass a value to the note below it. So route will have a value. It will pass the same value boots left child. And it's Rachel. If they exist and what these Children will do, what your belly was given to it, it will multiply it with 10 and add the remaining values return. For example, this route will pass on four to both of them. So it passes for your older process for so what it will do. It knows that whatever was the number represented before me in the hierarchy uh, there, due to that follow hair onwards will just be appended after this. This values by struggled. And let's say there are three more digits starting from this, even the to the tree. So this was 1 25 and these are 346 total memorable. We want to fight 346 So this number one passed to us. So what we will do, we will multiply. Tend to it. It will become 1 to 50 plus whatever we want. Three. So it will become 1253 And then we will pass this value to below. I need to be looking multi play with 10 and adforce again We will pass one layer further on again. It will. I want to play worked in and out of six. So it will become this one. This is how we all right numbers and decimal. So 12 means 10 plus two 1 53 means this is multiplied. Very 100. This is multiplied by 50 and this is multiplied. Wait three and we're trying to replicate it. So what we will do, we will have in global result variable So we'll keep aerial variable and it will be initialized to Jiro. And whenever we reach a leaf mould, people kind of keeping trouble Water there Duits still reaching here And we will are to Richard. So for staying we start reversal from here. It's left and right are valid, so we don't do anything. So we passed for two below. So it adds it multiplies it right then So it makes it 40. Whatever did it was a prostitute and past 40 to its left and right heard the current value also. So it will become 49 and past 49 to left and right. So the task off every Nordea's toe, whatever value it is given, multiply waitin and upend the current value and just one more information. All the numbers are from 0 to 9. So that the just single digit number and that is very crucial. So it will pass 49 to good bye, even one. No, it is that it's a leave. No, both left and right. Er, no. So what did we do? It will again multiply waitin at five. So it will become for 95. And since it's leave note it will update the real. So regional becomes for 95 again. This called will terminate on the next call will be made for this right note on again. 49 was passed from here. Same valuably passed to both left and right if they're present So again, uh multiplies that waiting. And as the current value that is for 91 and then it sees that it's left and right. Both are nil. That means it's a leaf. So we have reached the end off the part. So whatever is the value heard to the result. So this values also added to the region. Next, this call will also terminate here, and this will terminate here and it will pass again. The four for was passed to this branch, so saying valuable part here. So what this will do? This will blindly monetary play weight in and add the current value, which is zero. So it's 40 and then it was either it's left and right, Colonel. That means we have reached a leave. No. So we have to add the current value. So the visual and this is what we had expected for 95 plus 4 91 plus 40. So let's right the court for this. First, we will write it in C plus, Listening Job and Peyton. So the base case is that if the route is empty, route is not know what is normal and then return. If we will does not meld them. Let's keep it global reeled, which is zero and we will pass this result at the reference to recursive calls which we will define in a moment on a terrible freedom logic. And then we will return the final Reared No, we really finally cursive function. Let's call it, find some. This well is the value that is being passed to Lord levels for example, this poor past four to its below level. And this north Marty plays whatever values passed oot and urged the current value. So it becomes 49 and again propagated below. If there are notes otherwise return otherwise, addict to result. This is what we're doing. Just one task. So let's right that here and we can keep this realtor. I remember very well also where we can posit very difference so that every call is updating , adding to the result which was in its allies to Jiro. So here what we will do whatever ever lose passed to me. Well, multiply ratan and add the current budget which is the well value in this north not back well and after adding this, we check if it's leaf at this value to result if not propagate this value below on leave. We will add value that the leaf which is a valid part. So if not, do not lift and not root, not right. That means it's a leaf. Then we are to result and also return. I don't need to proceed further. If it's not leave, no, then it will have either left or right or both. So if left is there, then find some left on. We will propagate this value Current recalculated here and also the region so yielded passed by reference. You can see it here So every call will. Every leaf will add its current value from rue till the current no toe the same really and the same thing for right, if right is present, propagated the same value on and then we need to call this function here and to root zero is propagated. Let's say we have just one more. Let's have you have just him. So you can think of that. We're calling that same recursive function. Find some on route and we're passing a value of zero to it. So this is even about the route. Some hypothetical level. Jiro. It does not have any north, so we will pass a value of zero to this route initially, so this road will multiply Jiro by 10 and earned the current value. So Jiro multiplied. Wait any Jiro plus Tim, which is didn't it will not return digesting leaves, so let's make it it. So this will be eight, and if it's leave, it will return it, which will be correct. So that's where we're passing. Deal to the route that is the first call and then rejected by reference. And let's see if it passes the test case. It works. So let's some. And this whole reason is accepted on a textile mill is again, Let's straight again. This time it milliseconds understand. For milliseconds, you can see decreasing without even making any change, and pretty sure it can reach even zero milliseconds. It's four, but you can try a few times. It can reach here also, so, no, let's do the same thing in Java. So let's copy dysfunction and then we will define it. I remember your judo and we don't need to pass original, since we have made it member wherever, - Let's see and this works alerts submit here. It's and Jerome politican in yellow, so it's better than 100%. And now let's write the same thing in pay per item three. - So here. Also, we have made result at a member of this who this same result will be accessed across different calls off this recursive function. So let's submit, and the Buyten's Allyson is also accepted. 23. Reverse-order Level Order Traversal of Binary Tree: This is a simple problem. Off label order travels. Only difference is that instead of traversing from notice five, 36 and 24 we will traverse in the opposite order. Or at least we will return the result in the opposite order. So here we will return that 24 She visited the last level, then 36 and finally the route notice fight. So these same color north will be printed together in a in A list or a vector. And finally, it will be Victor Victor's. So how we can do that? So we will again follow a breadth first search approach, which is generally used for level order traverses. You can use our defence also, but this is much more simple. So what we will do? Well, uh, create a Q and insert route into it. So five in certain? No. While Q is not empty, we will prop it. That is in. So we popped Cunard pop and what we will do, we will see. What is the sage off? Are you before popping, let's had the site Kildare stage. So we know that, uh, these elements are at a given level to initially you have just one. So we know that at the first level there will be just one north. So we will gonna look for my equal toe 02 sides minus one. We will in sort everything into a vector. Let's call it notes. This is not the global or regional directive jilted somewhere here and it's Victor off Victors, this is local worked for one level or you can call it level lords. So we will do north snort, pushed back or insert whatever is the function available disporting Nord or its value? Rather, this is a three note type on inside three naled. We have a value off type int and two more tree nuts which will do not left and right. So we inserted value into this vector so it will insert all the North's at a given level. And finally, after this visible insurgent result again pushed back our upend or insert whatever is available or our aired and finally revealed return reverse of reald. So if you're inserting the beginning, you don't need to reverse. But if you're inserting in the back, then reverse it. So let's run through this example. So we have this 536 and then we have to wear full. So five regions are turning Took you que is no fight. It's not empty. So we will pop flame and we have a north vector which is empty. So we insert into it five. And here the SAGES one. So we will do it one time before popping. We need to see the site and then part that many times. And for every popped insurgents left and right into the queue, So Q becomes five Sparks of three and six is uncertain. Now again, we will see if it's not empty. This one level is complete. No SAGES. So we will pop two times, repeat good times and equally toe killed Artpop, which is three and put its left and right into the cue that is two armed foot and this tree's popped. So we have done You'd want thing next again, pop One more element that it six. So this is popped and it's left and right. And also we will not inserted. No, this second level is done and in this note, we have inserted in the value of each other. We have popped 36 so here in the global Richert. It was empty initially. Then he'd become this. Will you fight? Then we insert this value 36 and now this level is complete before starting this level. So I was too. So we prop it two times and whatever everyone was booked inserted into this. No, we started the next level. Now again, cues not empty. Then what is the sage sizes again to? So we will prop it two times. And here again, we have a new North's list. So first part Dylan will be too. It's left and writer notes or nothing will be pushed. Who comes here the next? We pop four when it's four again, No left and right, So we will not add anything and we insert this into the list result list. So result is no flight 36 and then we insert this new level 24 and now the Q becomes empty . Everything that were inserted has been parked, so we returned this list in the reverse order. If you're already inserting in the beginning, then it would have been fight. And before that, we insert 36 and then before that 24 So you reverse it we get 24 36 and Fleet. This would be the answer. So let's right the court for this and we will do it in C plus plus Java and python. All three. So one example is given here 15 7 is the last level. So it comes first than 9 20 And finally the route that history If real business that is there no note industry don't return this empty really hurt else. Career to do Off Treanor 0.2, this is this is this tendered, Brett for search algorithm here, So we will do it in time. So first calculate decides so in is cute dark sage. So this is the levels no notes at a given level and we know know it's site it's in. So better create victor of that say beforehand. This will be popular parte de elements and times and then north's eye. You could do North Van and then what we have to do be a particular left or right or presenter. So if left is there posted left into the queue, if right is there pushed the right into the queue And finally, here in the real world we push back this north factor. And finally we will reversing this The yard since here we are traversing from beginning, we have inserting in the end. So this will be talked down here. We have to return bottom up in decreasing order of levels. And this matches with expected answers. Let's submit and the solution is accepted on we're here. Let's try one more time. No, let's try this in Yella, this ball will return as well as for development. We don't need to end up here and, uh, North snort with that. So we need toe to it and then if left his Notman so we will insert in the beginning so that we don't need to reverse it. And it works in Java. Let's summit and the solution is accepted on here. Although it's around two milliseconds. So most of the solutions are concentrated in this range and it's a long time, so you can expect very is in here. Finally, we will write it in by country. So here the court will be much cleaner, much less cold. We're not using this in any burials. Who and the patents all isn't it also accepted 24. Maximum Width of Binary Tree: Today we will see another banditry problem and it's finding the maximum Witold banditry at any level off this give entry. This problem has multiple versions on earlier. What I thought it was likely different from that. So I thought that maybe I need to come the number of notes at each level and return the maximum off such values. So in that case we would have returned toe. Since none of the levels have more than two notes. Here we have two notes, two notes, but this problem was slightly different. So here, even if some notes are absent, you have to fill in those notes. So here we will not fill it since this is after the last note but in between. So you need to consider the first note on the last note at a given level and you have to assume that they're the missing notes are present. So the victor will be three since this poison is empty or it's not, but we will not adhere. Similar lease. This left cell was missing, but who was here as the right child. Then we would have not filled this left then the which would have been too. So let's see an example here. So this here we have reeked of one here We have a tough toe. All the notes are filled. There is no empty node. So had any living. We can have to reach to the powers that money off empty spaces. So if you make a complete mind retreat and fill all the nodes then you will have something like this. So you just need to first and last. Let's a first is this last is this? Then it will be three similar leaf for stiffness And last is this one the near it will be 123456 So there will be six even if this degenerates are absent or even if some notes in between are absent. Still this statistics. So you've got some idea, but how we will solve it if we just to do simple Beinfest, Then we will be or inserting this in the queue. Then when we pop it, we live in certain tree in six and now you say will be to so we will get a side of to next for the next two elements that history and six will prop them and also insert their Children in tow. You so we will again insert to win four, so we will never get more than two. So what we will do instead off simply using the North's people also assign index to them. So if you have worked with, if you have implemented by and reheat, then you must be aware of this dirt and Bindra heap. Is it complete banditry and at the last level, some north, maybe empty on the left, sifted as possible. So here, what is the index? It's starting next one. It's sitting next to three, 4567 and so on. So we implement. We can implement combined re hip using A because we know that all these intermediate levels are filled. Only last level is not filled, so its decision next one. Then the next office left child will be left off in order. The next ideas will be two times I. D. X and right will be two times ideas unless one So one times two is two price off twice of one plus one is three. Then it's a devilish for and you see in export. Then four plus one is five so there is your difference of one here. Similarly, double of 36 on this index is six and 27 so on. So even if these notes are not present, we know they're in. This is so what we will do. We will assign and index all one. You can also start with zero. Let's assigned you than the former levels. Likely change 2012 to the This is absent for fifth sixties older option. So here's the formula is there. It will be twice plus one, and this is twice plus two because we started from Joe. So what we can do you insert? Not just no, but also it's index. So in that way we will know that the first element attacked police entry. Last one is that poisoned five. And in between, we have to fill anyway. So using this these two values we can find the verdict 3 to 5. That means 34 and five that is three. So let's run through this examples of insert five MD rowing to the Q and the Q is not empty . So we will continue, so it's root is empty darkening. There is no no, so result will be zero. But if route is not empty, what is there then? At least which will be one. So we need allegedly dealt with one. Then we pop this five year five is the root note, the renewed and you is its correct position. And then we look at the sides off cubes SAGES want. So we will pop one element and insert them into the cube. So we will insert 03 31 and six to into the queue Now to say he becomes too. So we know that these are the North had the same level, so we will process to off them. We can create side before and this is just normal Be office. So we popped three out of this. And at this point, when we're finished with one night reason, we will see that What is the first element? What is the last element? So what is the index of first Element One index of last element is to So what is there difference? Orbit? It's last minus first that is to minus one plus one. So here it will be too regarded better region. So we will also check result equals Toe Max off existing result and end index minus START Index plus one. So here result will become, too. Next again, it's not empty. It will pop three and insert. It's left notice are to return next off. Three. It's societies empty, so it was not inserted. Next, it'll pop six, and it's a childless for retained Excel. Slave right is empty, so it will not insert now this Q has two elements. Now again, we will take what is the first index? It's three last index. It's five. So result will be Max off. Existing result in that is to and five Ministry Plus one is three. So the journal becomes three and then we will prop it. There is nothing to push. Both are empty, some liberal puppet and finally, Ritter this result. So I hope this is clear. Let's try to write this in C plus plus and Peyton, there is no nor did in the streets or returned zero. Then if it is there, then result initialized to one. Then you B If tree nor the star on the 2nd 1 is index starting from do you? You can also use make pair, but you can use this initial ledger list started the start index and this second value in despair denotes in that index. First, is the tree no So I d x off this Nordea's Ah, the 2nd 1 second element of despair. So we will use this for a while inserting its Children. So the index off which left child will be two times already explicit mint. And in next offer, I tell, will be two times I did plus two. So it left is there then poor sitting to look you on What should be the index two times index plus one. So I d x is the index off current? No, similarly for right one and finally here we will return Reared It's not and is the trigger shouldn't be back from 10 back and this works for this case. So let's try a few more guesses. So this denotes destry. So if we make this treasonable, then it will be five here and nine here, so that should be against same answer for and you can see the tree being drawn here. My little This is a cool feature for three years and we make it. No, it will be gone. So you see this trees gone still, It's before this is the left. Tell of this. This is the right channel of this. So let's run it and it's for Let's submit and we run into some signed integer overflow at Line 29. So this two times I DX is going is overflowing the limit offs. Ancient Egypt. So we see that the Indus is are growing exponentially. So let's look at this. Let's look at one example So let's say we have the street. Let's take a general tree at level one. We have starting from 0012 than 3456 Start this level. We're condemning one index 11 of the teachers here we're consuming to here. There are four notes here. We will have eight notes 16 32 and after some time you see that it's becoming a use number . So in general it's to raise to the power level number. So it's exponential. Here it's tourists power Jiro. So with a few number off nodes, let's even if we have a sparse tree like this, then we're checking for left and right. Let's say we have something like this. It's not increasing, but we have just two notes at each level. But this is the left most note and these are the right most note. All the intermediate Nords in this is will be Condoned even if they're not present. So we'll be signing the correct in. This is so it will be zero. 123 456 seven it 9 10 11 12 13 14. So you see that even if North Star absent, we are consuming that many number off in this is and quickly after are 32 level. You can see that the number of North will be to restore for 32 or even our after tart even levels. It will be one plus two plus all the way up to two rested for 30. Even so, we will consume the into Max limit. Similarly, even if you use long long on, you decide to 64 bits. Still, after 60 63 levels, all those values will weaken you. So what we will do here? We will do some up to me, Jason. So once we have, we're processing nodes level ways. So we processed this one and then we popped it out, and then we pushed next level lords. Then we processed all of these and pushed next Nevil Lords. So we're only working with one level at a time, or you can sit two levels after time. So when that reason ends, then, uh, strictly there is all the North's in the cure off one level. So we will start popping them and start putting their Children into the cube. So we're only bothered at work two levels after time. So once we're done with this, what we can do, Uh, we know that the first index is three years on the next. UNIX is six on last index. So does it matter if the indices are from 3 to 6? Or is it from 0 to 3? If we keep this distance or if we offset all of digitalis is the agreement them by fixed amount? It does not change anything. And here then this is our seven to let's say it's six. So 14 it 7 to 14. So what will happen if I make it Jiro toe three instead of 3 to 6? It will be our twice off this place, one that is one twice off this plus two thirties. It so if we make it 0 to 3 instead off 3 to 6. So it was earlier 3 to 6. We made a deal. Three. Then it's Children. Index off. This will become one and index off. This will become it. We have to double it and add one for left and we have to double it and add to for right. So again, you see that here the differences. Seven Here also their differences. Seven. And in the next level also, it will propagate like this. So once we're done with the level of evil uh, reset it. So we will take the first index added zero always. So let's say it's starting from when you go to four on dis indexes. Understood. 2040 year time putting some random number. This will be not like this. One of them will be ordered. One of them will be even. So So here it will become Geos. So we will document everything by this beginning index so it will become zero. And from here also, we will subtract this so it will become one euro to fight. So it will be one year to five instead, off are to Europe for it. And this will be Jiro instead of when you're 23 So this will do for preventing that. What flu that was happening. We were keeping track off all the previous values which we don't need to. So let's update over for listen. So you see, we are subtracting This is start from my DX so that it will not medically reflected here. And this Oleson is accepted. There is no world flu and we are around here. Most of the solutions are concentrated here only Now let's write treating fightin and inserting this sort of the same edge inserting here only your heart first means you, Jiro. And second off this means in next one and the patents Oleson is also accepted. 25. Check if 2 Binary Trees are Same - Iterative + Recursive: in this problem wear given to bind retreats and we have to return whether they're equal or not. And by equal, we mean this would be structural equal. And here, if you see these two trees, they're structurally seem. This one has left and right, left and right. And this one has left, right, left, right, so they have exact same structure. But that is not enough. We have to check the values also. So five is equal to fight trees equal to 366 So if you flip one of these support comes here to go there structurally, they will be seen. But the left off three will hold a value for if we flip it. But on this side, it's too for that are doing it was important. It should be exactly seem so. We will see a recursive and at rated solution for this the recursive solution would be an easy solution and it will be the preferred way off solving it unless you're asked to solve it attractively die treaty version would be a bit difficult compared to the consumerism. And this is a very cozy version will be very simple. And you can write it in three lines. Of course, you can even merge them into one line. Of course, if you combine different conditions and in this iterative approach we will take the hint off or breakfast reversal off graphs. We will do it in level order first, but it will be quite some amount of modification will be required in tow. Normal be office. So it will be were tougher than that. Normal be If it's so, we will see what other differences. First, let's look at the recursive way of solving it so clearly you will first compare their rooms . So when you are given a function you were given a tree Naled you're given two pointers to, you know, be on tree node que So first thing is that you are given the roots so first routes should be seem so if one of them is no better. But we know other ways we will return falls. So if both colonel, then it's fine motor vehicle. There are no boat, trees are empty. So your food b is a quarto. No and you is equal terminal. Then return Drew. If one of them is marginal or one of them is minal or delusional, then return False. So if both Arnold it will return from here itself. So you proceeded here. That means both are normal. But if one of them is not, then that means other is normal because both cannot be known here. It both were not. We would have returned from here. So in this case, we return false and no in the next lane, it means that both are marginal. If any of them Arnold or both or not, it would have already returned before coming to this line. So here we are sealed at both are not know So we will check your values. So if you don't well or didn't c++, it will be. This arrow is not equal to q dot Well, then return False. Otherwise this route it same on what we need to do off. We will check for this left sub tree. So if the complete trees are same then this left sub tree stood also the same as this left sub tree And this rights actress would be Seamus This rates up tree So if it's valid until this point, it has not returned from here. That means here it's fine for the route. It's fine. So if you return whatever is dysfunction I'm calling it if you don't f be left que lift. So that will check if this sub treats him as this and the same funds him be date que right and we're done. So what this function will do again? Recursive Lee, call on this on this so fast it will match the route. If there same, it will recursive Lee Colon this and this and similarly on this and this. So when it's called for two and two, it will check routes are saying the value values also seem Both are not know So it will call for it's left and this left So both Colonel So it will come here and it will return true So this will return true to the calling from him This will return true to its calling function and it will come back to and these are already seem so ultimately it will return true to this part three similarly, four will also return true and finally three will return true and six will return true So this will return true. This will also return true so true and true means truth. So in this case, true will be returned. Now let's see how we will solve it attractively. So if you're not family with Britt for strippers and better toe, review Beinfest video and see how we can use a Q toe. Do our breakfast reversal or, if it's a tribute, do it. Level order troubles are forced to root it blistered than next level, the next level and so so once your family with BFS, you're good to go. So there are some subtle differences from normal beerfest. One definitely is that here we are doing be efficient to our trees or autograph simultaneously in parallel. In normal BFs, we are just having one. Q b r Doing one big office, so we have one. Q For this one, let's call it Cuban. Let's call it cute toe. So what we do begin do the same sick compare if we have to wear D checks that if one is not others with Livinon, if only one of them is not returned False. If there were losers, same, then we're good to go. So after the Arctic, let's call this part of the quarters are equal. I'm calling it a let's put it in a phantom are equal. So sick. Uh, in this function we passed B and Q. So if our equal p and Q or rather if are not equal, then don't need to proceed further return false. So this function will end here itself at group level. But if they are equal, that is this condition did not hold true then in Cuban. Push this. This is from this first rumored and it's not interior. This will be Q off renal or in C plus Mystery not pointer like this. So both are tree node pointers. In this case, it's fight five minutes are guilty Nords tree nor the structure. Cuban has this place que two has also fight. Then, uh, here we will not just do level ordered reversal and not compare level a level. For example, let's say we're at some level. Let's hear Kato level in forestry and kid leveling, sir Country And here let's we have I didn't 20 years to North's Onley at this level and here we have tailed off site six and seven. This is that kid level in frustrate an insect entry we have again 10 20 so if we compared this level, you may be guessing that if we do simple be office on compare level, way, level for equality, then we're good to go. But we're not going to for their modifications required in the big office. So here we will see that both are same at this level, Kate Level. So at this level, it's fine. We returned True and in fact, we are true to this level. But let's say here we have flight, then we have six and seven. So you re simply, uh, check for this level and insert your Children in a queue. So hear the cue will have after we finished with this level that you will have a fight. Six and seven digital video, only three notes in a queue. You were processing level order and here in Kyoto we will have five. Six earned seven. So when we pop first element compared with it Ah, popped element of Q to their same. So we popped next element 36 compares their against him. Next, report this note seven and compare their same. So we would say that even at this level there, same. But we see that they're not same here. This 10 has two Children for 76 here tonight. I just want to fight here. 20 has one side. What Year? 20 has two tails. But if we just are concerned about a particular level, we would never discover this kind off animal e. Maybe that below this everything it seems so it will remain as true. But we have to return falls here. So what is required? So instead of doing simple, be office when we pull up an element, we compare them. So when we pop the pop from boat even and cute too, we compare if they're equal using the same logic. This function, that title article where we will learn the logic, these three checks. And apart from that, we have to check one more thing. That it's left side is also equal to its left, and it's right. So little trickle Duits right side. So if 10 and 20 are in the queue before processing care to level, we'll pop in from both of these. So we popped in from first cute and from Second Cube they are equal. This will return true. Then we check their left circle so this will also return true. Then we will take the right are also equal both journal then that's fine. Dysfunction will return true. But here one is not. No one isn't so. This will return falls and our check will feel So these are if you are changes required. Putin normal, be office. So now let's right the court for this in C plus plus Java and Peyton. So you can go through this example The general very simple examples. And here you see that to his left child here to the writer. So they're different. So just structurally being same is not enough Here also, the ordinary changed to 112 So they're falls here. It's exactly seem so frustrating. Door recourse even simpler solution that is, if not be and not cute. Then return to maternal. If not be or not que return false. Only one of them is no. If both are not no, not tell them we check their values p dot well, not equal to your door. Well return False novelties valued its values also seem if it a just so return. So let's see if it runs and disorders and is accepted so again it's Formula Second. But if you try a few times, it can be your milliseconds as well. And what is the time complexity here. So we are traversing this tree once, both the treat. So if they're in north and here, there and nodes, it will be ordered and plus him. And what is the space complexity? So we're not using any explicit space, but space will be taken by the stack that it used internal in this rickerson recursive stack. So it again can your daughter off. And so both space and time are off linear order. No, we will. Right there. I treat every. So let's come into toe. And you must have noticed that we're checking this multiple times this chick. So we will put it in a separate function and we will call it is equal. And this will also take two notes, three notes to compare false and false else returns. True. So this is equal function. No, we will start me in court. So first we have to check for route. So we will do if, uh not is it cool P and Q. Then there's well isn't at the root level itself. You return force. Otherwise we will create to accuse. It's called them Cuban and U two And then in Cuban they will put speak and this is Cuban. And in Q two pool push you then PM cure seem so we'll check while Q one is not empty. So we take the first element from would accuse and in sleeplessness front just returns. It does not proper Delmon, so we need to call Cuban, not Pop, and you told not to all support those elements. Then we will check if is equal or rather is not equal. This anyone and to them return falls. And after taking the elements, we also check their Children on. Do we know what is the region? So we saw the region. They're just checking the element which is part from the Q is not enough. We have to also check match their Children so left with left and right with right, this will also be seem, then only people their left and right. Otherwise we will return from here itself. So this notes are seen. But that's not enough. We will check for their Children. That is, if not is equal someone Victor copy this one after taking the north dignity left. If they're not equal, return falls. And this, uh And when can we One of them can be So we need her melt IQ. Otherwise, we will get, um, bad access this point original. So there is some thought that here in legal, you can select it on the press tab so it will sift it. If you have a long block off court like this and you want to sift it, you select it and press tab. And if you want to indent left, sift plus step left, two left are seem so what we need to do if the left Can we seem when voter now also So here we are not allergic. Do you wonder with and no one left and similarly we have to do for all right and then we're going to go finally will return through here on this so iterative approach is also accepted eso for a job in point and I will go ahead with this recursive it. If you got this idea clear, you can try to implement it in German fightin, whichever is your favorite programming language. It would also give you a good practice off the office, - and this sort of thing is accepted, and he rolled over here. It's just a millisecond, but still years here. Maybe, uh, we do not have enough accepted submission. So they started. Not available. But if we're dear milliseconds, we can expect now we're right in the operation. And in fact, for most people, it will be in that region only all the methods are converting toe orphan. No, We will do it in by country and the Saudis any, except written by tonight evil. 26. Zigzag Traversal of Binary Tree: in this problem, we upto troublesome banditry in level order. But we have to do it in its exact manner. So it's a natural extension off the simple level Order troublesome. If you do level order, traverse all of this, we will first bring five. Then three and six are next level. Then we print went for in disorder left left to right. But here the difference is that first you will start from this to this. So you go from left to right at the first level and you are in the side. So you return from the side and first print six day entry. Now you reach this end left and so what you do in the next level you travels from left to right and you continue like this so you can see this integrated left to right everything then right to left, left to right, right to left and so on. So just to give a brief recap off level or the troublesome if you already know it too then it will be a quick revision for you. So in leveller traverse and what we do in simple level or Traversa, we keep Q and we pushed the first north to it. So five post here, then we see how many notes are at a given level. So previous level. We had one note and decision noted by the side of this Q. So say, David, right here below. So now we erect next level. So this denotes so just when we reach this level, the side of the QD notes how many north where in the previous level. So we see that there are one. They were just one node, so we run a loop. According to Jiro Toe, Whatever is the sage minus one that many times pop from the Q and why we're doing this loop ? Because we need painful not just in one sequence, like 536 to 4. But we need them in separate lists. A list off list where each list will hold North Star for a given level. So when we come to the next level, we should know how many notes were in the previous level because we will be inserting in the same queue so it will grow. So when we pop this element and we put it left and right to the Q. So we will lose Track off How many notes were there in the queue before we started putting north off Next level. That's when we heard this loop. And in this case, it's just one. So it will pop five. So So whenever we pop, we put into it local vector or list. In this case, it will just pop one and it was Check if it has left or right or boat, it will insert them in the queue. So fire is popped. It has left three. So people insert three into the queue. It also has rights. So we will insert six into like you. No, this level snorts we have inserted. We come to next level. So we see how many notes are there in the Cube. There are two. That means in the previous never to notes were there. So we will start posting them one by one. So for I equals do judo And one whatever is the site this time. So I just do so it was run two times, Little pop three and look at its left, right put into the Cube. So three reports so six is remaining to win for our pushed and then we also pop six. We will do it two times since earlier We had no notes, not when foreign in the queue. So we part three and six. So a portrait in a new list. Now again we come to the last level after the last level. So these are rolling the last level loans. So we popped too. And there are no left rate, so we will not put it. Then we part for and again there are no left rates or even not presenting no disk use empty . So we returned. This court terminates this level order called and these are the originals. 536 and to food. So here what we need to do first thing we have to insert five. Next time hope we will insert six entry. So in this case, you would say that Keep reverse variable bullion Initially you can set it to true. And when we are done with this, look outside it What we can do reverse equal do not off flavors so it will toggle between levels. For one level, it will be true for next it will become not of that that is false again, it will become not on that and that is true again and so on. So let's see how we will do it. Let's say we write some general level. Oh, let's call it to see and deal for simplicity. Let's assume there are only two notes in this and there are many more nodes of it. It'd just one level and it has some time. Or like E if g. It's so I'm just focusing on it. General level. Let's call it level off the tree. So there are two possibilities. This level we had either printed like CND. So this was the state of Q or the other. Possibility is there. We had printed it in reverse order D. C. Depending on whether this was before this level. We are We were in this side or this side. So the other two possibilities No. If CD is the case that it from left to right, then this will be printed in reverse order. That is, it's G if e. And in this case, if d. C. Noted we came from the site. Now we're in this side, so we will bring it in or puts it into the list. This level list in order E f idiot. So I have written about the possibilities. So in this case, let's say you are using another Q or dick. You in. Q. You can only push in there, but Inere dick, you you can put in the beginning as well. Adjourned. So, uh, so what? Here. How we can achieve this. So first we have to park Si. So what we will do? So how can we drink these before DNF? Because first people pop, see and see how child DNF. But these are coming in there and what we can do here in this case, we will prop in an element. And ah, people have ridicule. It's Colin Dick, You in the queue beginnings heard from both beginning and end and similarly removals. So in this did you we will post firmed whatever notice part. Let's call it X extort left, then so make you nervous, then acute post print. Exe not right. And we will do for all these notes. So what will happen? So first we proxy So it's left his e So this dick use empty so it pushed e was front or back does not matter for the first element. Next it's right is if so, we're always doing post print. So if it's pushed in front, off it next element Probable Whitney so left off these g So we put in front of everything, then write it. It puts in front, off everything. So again, see no in this or dick you. We have ex g f e whatever be required. So we can simply append this Nick, you whoever or is no que so discourage. Just like this original level order, trouble silk you and we will continue to do you is not empty. So whatever the content of this dick you a pen ducked into that you so this these two would have already been popped. You would have become empty. And then we add this to the queue. So this becomes the content off you before going to the next level and here what you can do again. We can have an Dechaume and dick. You dirt these book first. So what we can do in this case, the Q dirt again push front and extort right? Then extort left. It also wear evening post print. But here first we're putting the right. Then left, then right then left. How many elements these are for all elements eccentric You? It will do the same thing. So first these popped. So write off these. It's so it is pushed. Then left is G. So jeez, pushed in front. The next element part will be see So it's right is if and it's left his e So this is the content off. Thank you. And the Q has became empty, so he upended this into the queue. So Q now becomes distinct. So we are taking care of both the cases. So one of them will be reversed, other one will be reversed equal to force. So whatever we say there that we will keep a 1,000,000,000 reverse equal toe falls in the beginning. And when we're done with one look, this four Look, this denotes popping elements off one level. So after that, we will chocolate, and in one of the cases we will do this thing left followed by right. In other case, we will do right, followed by a left, and then apparently stick you to go to you and they will continue to use empty. So this is very similar to a normal level order, Traversa. So let's right the court for this. You can go to this example. It's also similar to our example. So we come in the first little from left So three, then we come to the right side. So next is 29 This is 20 and nine and now we're in left side. So we will travels from left to right That is people in and seven So the base cases is that if the route is empty or rotational then we have to return empty vector other ways We have to return a vector of Victor off int and then we have a dick. You also I think I made a mistake here. So this Arthur thing will also be our dick you Because giving c++ only support police operation and it's pushed in there and pop from the front. It does not support inserting travel. But dick you supports insert function also where you can pass y traitors begin to end. So you we already have this Nick you they will prosecutor, begin on the second I traitor ridiculed art. And so we're not using cues we are using just like you. So let's keep Andy que what we will call it Q. Since toe keep it similar to our normal level or trimmers and cured or Bush Mac fruit. And then let's keep that reversing. Also, bull reverse equal to troops and, well, not you don't everybody. And then inside this, what we do first thing we do is current just like normal level order reversal. So cute dirt, sage. And then we run the loop and what we were doing, uh, we will have a temporary victor, which we have to insert in this vector of Victor's. So this time, internal victor will be vector corresponding to a given level, and this is combined with So each time we are creating a local victor and we're putting into the bigger victor and we will also have this internally que, which were pending to the ultra dick you. - Since you said that Cuba will specify whether we want toe pop from front or back. So we're using it like a Q only only facility we want. It was this insert function. Other than that, we're not using it for any other dick. Your prison. We're using it as a cue only if reverse is true. We will do something. What we will do if it's reversed, then we will first push left so you can do it. Rough work on Convince yourself Run through one example and you will get to know in the reverse case. First we will put left and then right. And in the other case, we will do to oppose it And in this case, it really simply a poor you to frustrate. Then left andare turned off this look which will be not one level. So this denotes one level. What we do que dot Insert in the water cube insert. This is in disc you from where to insert So this will be empties when does not matter. And from this I travel from where to where? So we will insert everything Vehicular Begin Indyk you dirt and and then in the our final result This level is complete when this Liukin's we're done with one level. So we will insert all the North Coast morning to deck level like this to the out of frigid and we have to double the rivers. This is very important one never done for next level, it will be negative on this not off rivers, so it will toggle between to force to force and so on. And finally we return Richard. So this was not very different from normal level order traversing. The only thing is that we added this reverse logic, particularly large objecting, and this works for this case. Let's try. Let's submitted there is something wrong. We will try some examples and this is accepted and you can see that it's ah Jerome politican, that is we are right here more better than 100% of the accepted submissions. So this seems to be an efficient solution, although you can see lots of Berries in here. 27. Construct Binary Tree from Inorder and Postorder traversal: In this video, we will be generating a bind victory given its in order and post order reversals. So, first of all, let's see what are in order and post order trouble. Since so imposed order to oversell, we have to print everything off the left sub tree followed by a rating in the right sub tree and then the route. And this sort of hold true for all the sub trees as well. So this is the post order Traverso route will come in there and left. Sub tree has 32 and four so you can see two for entry coming first than the rights of 3 36 Dundas wrote itself. And if you look at this sub tree that is this these three elements then here also trees the root. So it will come in their first left nor will come then right now or it had more notes than all of them would have occurred first together, then all the notes in the right sub tree and then finally the route. So the most ordered reversal know what is in order troublesome in our in order to reversal first print everything in the left sub tree, then the root note, then everything in the rights up. So if you look at this route is five so five is here. Everything to the left of root comes before route. Everything to the right of root comes after route. And if you look at this smaller sub tree, then trees the root. So trees here, everything to the left on Lee Tweezers comes before it and them the right sub tree. So this is the definition of post order in order know how can we generate it given these two Trevor cells. So we're giving these two, but were asked to generate the street from this. So what we can do from in order? We don't get any idea. But from post order, we get an idea that the main route the top level route will be occurring in them. So we know that five is the group. So let's forget this picture for no Oh, let's build it from these two. So we know that five is in learned. That means five Sandro fight. No, no Bill in order help here. So we have seen that everything. The left part off the route left sub tree occurs before fire and everything to the right off. All right. Sub tree of five workers after five, so search for five years. So we found five year and this is not a bindi. Sastri in buying Jesus to in order is also sorted. Since everything in the left is a smaller, everything in the right is larger. But this is a general bind retreat. So we search for fight we upon the route. Research for 55 is here. So we know that these elements must win the left sub tree and these elements in the right sub tree. So we know that sixes in this part on 234 is in this part. Now we have one less element. We have divided the problem into two parts. Now ever task is to construct left sub tree from this and writes up through from this So most order troublesome for this is 243 This is the same original area we can use from here to here. And in order to reverse Elise 234 And in this case, both is six and six sitting. There is only one element. No, Let's construct this. So there is every person here. First you find the root. Then whatever is the main function that is built Treat. You call that on this smaller problem? It will build the left sub tree. So here again, three is the last value in this sport ordered reversal So trivial Widow route off the sentry So three will be here group no search for three and in order to Russell trees here. So everything to left off it. Good window left sub tree and everything to the right Off it will window right sub tree In this case very one only one element. So we can a straight adroit And here there is just one element. So this is the route? No, this will return to the calling from some So we can right here route is this rooty call to neutrino and put the value off disposed order there so it will be constructed then root dot left equal to the same function that is built tree and you will pass the same Mary by reference so that we don't make multiple copies of it We will only pass in This is so in the beginning Index really from zero to win or didn't minus one. In this case, the index will be Joe too. Do you want to? And in next year will be again Joe Toe. So these occur together everything in the left sub tree will occur, occur together only their order will be different here. So whatever is the opposite here will work here also. So we're calling the same funds. So if this is the main from some big tree the building you tickle toe new tree naled and whatever is the last Norden this post order and then ruled out lefty call to call the same function military and passed the same Mary and passed twin nieces start and end similarly ruled out right equal to the same recursive function Billitteri, pasties, arid And also what in this is to use So the main funds and that will be given to us We'll just have post order and in order as list. But we need to address knowing this is as the starter and you can do better but that also if you make a copy of this so copy this part and past positive post order copied this part pass it as post Order for this called the right sub tree. Similarly, copy this part, create a new a smaller list and pass it so you can do with this original function also, but that will result in multiple copies, although that will be much easier. You can sometimes make mistakes while calculating, starting in and witnesses especially very plus minus one. So you need to do some rough work for that. So I hope that is clear here on we can build a tree using this uproot. So let's right the court for this in secret now and Peyton. So this is another example which is different from the example again again here in port order, treason learned. So we know that three. The route in order research for trees, trees here. So everything to the left off it is in the left sub tree that is nine. Everything toe the right off it is in the right sub tree that is 15 27. And again you can look in this part 20 is the last elements of 20 the route and in in order to search for 20 in this part twenties here to the right of 37 to the left of it is 15. So this will create a separate recursive version of this where we will pass in. This is also let's and our BC to denote. This is the main recursive function that we will use And here we will pass to more values first indexing in order and one more than last. You can also pass the last Also, that will depend on how you manage discord even denotes that beginning off post ordered reversal in this ordinary we're not seeing in this area. We could have passed a copy And this is one more than ending index. No, here what we will do. We can hurt some base chick and it's given that it will not be invalid case like in order and post order, you will have same number of hogs although it's not given in lead court booze cases are 100 . Generally inputs are valid and not invalid. If input is invalid, then these are generally mentioned. So let's assume that these are valid that does these have same elements. It will not be the case that here we have 12345 And here we have 6789 10 so there will be a complete mismatch or the number of elements are different. So a during those cases are correct. Onley check People are dessert. If which side is do you them return? No prettier that is empty tree. So in this case, this is a valid input. You will just passed to empty lists. But if we enter any other value like unequal stages then does your invalid inputs and other ways what we can have the size capturing a very well We will use it sometimes. - So in the beginning we will pass everything complete area so dear to endear twin You can also positive two in minus one. Just make sure to handle it here and no Here what we will do if Ivan is more than or equal to I to So here we are passing in not in minus one. So this if in order and if beginning and end our boat in then this is invalid case So this is one one index pastor The last index that is the case with begin and end i tractors Beginnings. The first is the editor of First Element and is one past of the last element. So that is not a valid index. So it's very cool then. That means there is no element to search or people greater than equal to p two. Then return Look no prettier. And what is the root last element off? Post order and last indexes be to minus one. So duties no constructed. Know what we will do? We have to search for this value in in order. Traversa. So here. These are not sorted. So we cannot use my niece. Sort, It was really near thing sort. So if you want to speed it up, you can help in that you can populate a map here. So indictment enter the value as the key and the cursed morning index has the value. So here you can straight away get where this values occurring in order in constantly. So you need just one man for in order in post order. We don't you run into certain that so that will be constant time so you can do that up to medicine and is keeping it for now. So that will improve your time complexity, since you will do it. Oh, in often here just one times and then we will keep on passing that map by difference on whatever time is taken, it will be taken by the building of tree and not in searching. But if you are using a linear certain in the first, uh, in the first call, you will searching the complete Eric that is in elements. And this call this breaks name put into two parts with one element removed the route. So again you have in minus one elements to search that will further break into two more. So we will have four well for sub trees. So remove are two more notes, but still that is off the order offense. So we have to know search make a certain maximum in minus three values, so that will depend on how deep the tree is. So if it's kind of balance treatment over time, taken away. Search ability in Logan, Since Logan times really making making this call and in each call, we will roughly searching for in values. So that optimization you can easily make you just Oh, I tricked through this in order keep it in a map. So there that time is eliminated. That will be constant times Only time will be in building the tree which will be off. And since we will be looking at all the notes So I'm living there on you to make the optimism. So we will use the inbuilt function find we can also run a look from this I went away to and search for this. Will you boat or something? This fine relies heavily in the area. Uh, in order. Dordt beginning in. Fine. We need to pass the way. Traitors. So we don't need to size from beginning, but just from even try to And what? We need to search this. Well, so this will return, though. I traitor off the element. This element in this in order. So we will calculate their def. How far it is from Ivan. Ivan is the beginning. I was the one more than and so it will be found somewhere in Britain. Windows? So this difficult complained that so this is I t minus it. Is this a traitor? And even you're the first index which we can find by in order. Dark begin. Plus, even so, let's open the bracket. So this will become minus. So this is their difference upset from even if first element is this element that is it occurs that I even prison if will be deal. No, we will recursive Lee, call it on. Left on, Right. No, we need to take it off. These in This is so earlier It was hurting from I went away to know we have found you hurt this I t And we know how far it is from even so what we will do here? I even will remain same first tunics and I too will change. So we have to search one index before this. Well, what I d was formed, So let's see here. So, for example, three was group we searched for three year and what we did this is independent part this part and this is separate part. So three has divided it into two parts. So here tops. It was What? So this is Joe. This is one. So this time the big mingled remains him and will remain one over table tops it. So it's, uh I even plus diff And in post order, uh, this is assault. So even will remains. Him and Peter will be. How many elements are there. So this upset also denotes how many elements are in the left sub tree. This is what this does rooted here. There are so many elements in the lift that means same number of element will be in the post order. So pre order and post order will always have same number of elements. So this def also divides this thing. So this will give an idea that how many elements we have to take beginning you seem and will be people. Plus, if and for right, we have to look after this three wazirs, everything to the right. Off it is, uh, in the right sub tree. So here, this last index is not in you. So I took it remains him and Ivan will be I even plus if, Plus, when we have to go past the Thursday element, this tree is no gone. We have to look after this. So there's a plus one and then I to remain same in this case and again, even plus diff. And here the road was in there. And so whatever is the number of norms in the left part. We have to just return that, and immediately after that right sub tree will start here after lips up tree root occurs then right sub tree. So we had ordered Ah, plus one here. But in post orders, we will not. And that so it will be just even pleasant if and not even place the 1st 1 And then we took minus one since this route is gone from them. So Peter was here earlier one past three. So trees gone. So Peter should come here. So our little three to minus one very simple. And this will recursive liberal left and right. And finally we will return the group and let's run over court, uh, new and this matters. So let's summit and the solution is accepted and we had around 36% look straight once more . If timing improves again, it's fluctuating. So try once with the optimism for that map. So travels this in order. Keep everything in the map, the value and the horrendous is and use that here. If that improve the thing they someone want or not. No, that's right. It in number. - So this find is not available. So we will do a manual search. I equal to you and in four and according toa level, I list them I to plus plus I. So if this matches with in order A, then we will break. We will not continue. I take it away Burned brick. So again, this site is holding the position off the found element. So over other form local remain as duties. So no artifice calculated so everything else would be trivial here on blurts right. The main force, him and the jobless are listening also accepted on it slightly better. We are in this main distribution. So most of the solutions are in this region. And here again we have not used optimism. So here also try using the map for this find to get rid of this and do it in constant time . No, we will write this in Ah Bytom. And here we have to pass. These were different, so we will add them to self and we don't need to posit him. You can also process slice, But again that will create copy here. So here again we don't need this. Look, we can use the index Wilson. So this builder turned index off this element in in order and then this everything else remains him. The former lie number. Eat. Okay. Self is not passed here again. Lane number eight. Okay, So this is the mystic. No, this works full. It's submit. And the solution is accepted in Britain. And here we're here. 28. Vertical Order traversal of Binary Tree: In this problem, we have to do a vertical order traversal of a binary tree. And this has been asked quite a few times in the interviews of Facebook and Amazon, and also a few times on Google, Microsoft, and Apple. So let us first understand the problem. So here we have to traverse it vertically. So we have already seen some of the traversals lake level order, in-order, pre-order, post-order. So here we will traverse vertically. So first, start from leftmost column. So we have a notion of column, and we will call this as level or rule. So we will start from leftmost. There is no element to the left of full. And we will shortly see what is the notion of column. So whichever sport forced and this ordering is important, even this order of vectors and within that vector and order of elements that is important. Then we traverse too. So you can see two here. Then we have 156. And why these are together. So this means they are in the same column and we will see why this is so then three and then seven roughly, you can see that we are traversing from left to right and within a column via keeping the top element first. So we are starting from top to bottom. We are looking from up to down. So whichever is at the top, we will print first or including the real, foster them, the element below it and then below it. So we traverse from left to right and top to bottom. So now let's define the notion of columns. So root is at column 0. So this is the middle. So if you write UP around these Cartesian axis, this is the column or way and then descend. We have positive disagree at negative value of x. So exactly same. We have to think of Rukeyser pivot here. So root has a column number of 0. And when we go left, its column is one less. So this column number is minus1, diseconomies minus2. And when we go rate, we increment the column. So this column modulo 43 plus 147, it will be plus two. And from trivial wing left, so decrement one, so it becomes 0. And here from two we're going rate, so increment one, so it becomes 0. So you see that there are three elements with the same column, that is 0, which are 156. And we have kept here 156. And it's not because faith comes first in this room, it's because five is smaller. So first we will arrange them based on our column clearly. So this minus two is the smallest columns. So this four, then minus one, we have just two. So there is no confusion. Then we have 0. In general, we have three elements and we adding them based on the rule number. So when via multiple elements, CVD debt, the smallest real number. So one is at row number Of this, these elements are at row number one, row number two. So DRC image levels and Raj increasing from top to down. So here, one is the clear winner, winner Iit's true number 0. So we put it first, then 5-6, both direct rule number two, so which should be put first. So again, multiple elements have same row and column V competitive value. So five is smaller, so we keep faith Foster. So if we had six year and five-year In the original tree, then still the result will be the same only, it's not because five was coming first. So this is the basis of comparison. No, I hope the problem statement is clear. So then, then the column number is one. So at one we have just three. Then column number is two. So at two we have just seven. And this is the result. So how we will build decision? So we will traverse the tree and there are multiple ways of traversing. You can use BFS approach or DFS approach. Here we will use DFS approach since that's more neutral and recursive way of traversing. So we will start traversal from loop. Root is one, its row number 0, its column number is 0. And we will maintain a global Cass. And this gas, we will keep track of what elements are in a given column. So ultimately we should have minus2. So here C0 will be key, will be column number, and value will be a vector of or a list of all elements corresponding to that column vector of vectors. And each element we will store a ruined value, rho n value. So this is the structure of this gas. Initially it is empty. So we start from group. We get the column number and this is rule, this is column and this is NADH. Rule number 0 condom material. We check the CAS whether this key is present or not. It is not present. So we inserted a new key and this element one at row number one and the value is one. Then it will call DFS on its left. Its left is two. So this is not the value to, this is an order to it has evaluating it to two and its row number is 11 more than parent and column is one less since it's the left child. And it will also call DFS tree rule number one and column number plus one. Then these two will call for 45. So here in DFS, what we will do in DFS, we will compare this column, whether this is presenting gas or not. If it is present, we will just append this value, current node's value into it along with rule number. If it is not present, we insert a new key and one element here. So for this call, minus1 is not present. So insert minus1 and its row number is one and values two. Then this will call DFS on for row number two, column number minus2 and DFS five, row number two, column number. Neil. In this call, we will check whether minus2 is present or not. It is not present. So we will insert it. Rule number two, value four. And then 00 is already present, so we just appended to it. Or rule number two value phi. And then we come here, plus one is not present. 13. Then this will call for 67. So DFS six, row number two and column number 0. Again, 0 is present, so just append it to six. And also DFS. Seven to row number is two, column number is two. So two is not present. So now when this, now this DFS call terminates. And one more thing we will do, we will also keep track of what is the smallest column that we encountered in this entire traversal and also largest column. So mean call equal to minus two. This is the smallest column number and macroscale CTO plus two. And when this traversal completes, we will have discuss. So let me write this again. So I have rewritten discuss. Now what we will do once this gas is built. So let's write our main function. Let's call it vertical order traversal. And we are passing the R2P. So here what we did, we did DFS on route row number 0, column material. And this will build a gas. Gas is now built, which is this one. Gas is broken this in DFS call in this fashion what we saw here. And then we have min and max C. So this we have after this DFS terminates, then what we need to do, our results would include in this polymer to foster the smallest column, the next one, and so on in increasing order. So we know the min and max call. So what we will do for C equal to min c two maxi, we get the elements corresponding to this column from this gas. So initially c will be minus two. So four minus two, we have this value. So when we started, there's just one element, so nothing to sort. So it will be twofold. And in this twofold, first 20 ROW_NUMBER, second one is the actual value and we are just interested in value integer. So we fetch this for second element and result which was empty. We insert this photo and this is the only element, so just one element. Next, C becomes minus one. So we go here and get minus1, Again, one-element, nothing to sort. So get the second value, put it in a vector, and inserting the result. Then c becomes 0. For 0, we come here, we have three elements. So now we need to sort. So first we will see the row number. So smallest row number comes first. So clearly one is the winner here. It has a row number of 0. So it comes first. But 456 rule number is equal to, so between these two Drake, whichever value just smaller. So five is smaller. So direct flight first and add seen earlier. If even if 600 year and five year still we would have written 5-6. So here's the business of comparisons is the value itself when they're in the same room. And then six. So we will just extract the second element of this pair, first digital, which is just used for comparison, sorting and nothing else. We are just interested in value. Then column number one. So we come here, which is 13, just one element, nothing to sort. Then C becomes two Maxis, T2. And we come here to seven meeting to sort. And we return this, this is our final layer. So I hope this is clear. So let's write the code for this in C plus plus and item. I will skip in Java for this exercise eight. So this is our main function. We will need to define a DFS ozone. So first result is a vector of vector of int. So if root is null, then return them to desert. Else we will keep one cache. Keys the columns, so it's int and then the values vector of pair of ruin actual value. So rho is int and int. You can see the values int. Let's call it cache. And then means equal to 0, max equal to 0. And then we will call DFS on this route, row number 0, column 0. Let's define the difference first. And then we need to use this gas inside this. So let's pass this, make a difference. And we will also be updating min, Si and maxi. So row number 0, column homogeneous and guess and then mini-c, Maxie. And when this dfs terminate, we should have this gas, Minsky and Maxis ready. So what reason, right in DFS? If norm is null PTR. And then we return. And then we check this is the column that is passed to us. So either it has been already inserted in the cast, some elements corresponding to that column, or this is not present. So if it's present, then we will simply appended to it. So this gases will return the vector of elements. So we will appended to it the current row numbers of Telemann digital number. And secondly is the value else and this was not present here. So inserted motors emptying, just handling. If the key is not present, we cannot directly access using this. So naturally this check is required. So we insert the column number and then rho m value. And then we update the Minsky. And we will recursively call this one left-hand rate of this mode. So if this were a leaf node, it will be none. So it will automatically return from their total number will be one more than the current node for a decision. Since it's left column, we're going to be one less. For rate column is one mode. So then this dfs terminate. We have these things ready, the CAS, Minsky and Maxie. So what we will do SQL to Min Si C less than max C plus one plus plus C. We can also solve this implicit. We don't need to make a copy here. But for simplicity I'm making a copy. We don't need even we can pass this solids, used this only. And then decision backdrop pairs. So we need a way of computing it. And the comparison is based on rule number, which is the first element. And if roads are equal, then based on certain number. So our competitor will take two pills. So this means that if the other value of this pair is less than p1 first, but this is not the only criteria. If this is not true, then we have to also check. If p1 dot thrust is equal to p2 dot-dot-dot, that those numbers are equal. Then if p1 dot second is less than p2 dot second, which it actually known value. And then we put B1 first. If none of these cases are satisfied, put b to foster in the sorting. So this gas C is now sorted. So what we will do, we will have a vector that we want to insert in the yard distributor vector of int. Since in result, we expect a trophy homes that it actually known values and not the rule number. So we will extract and second element from this vector and put it into this vector. So we are getting the secondary, the value in putting into this vector. And finally, we inserted into result. And after iterating through all the columns, we return the result. Line number 2016. And this works umber density wrong. The competitor is run pivot. Should be p2 dot first, and then first second. So we were comparing apples with oranges here, P1, Northwestern Bureau. Second, notice, Correct. And the solution is accepted. And the solution is better than 93.7% and it's very close to the best one. So what is there? Time complexity here? So here we are clearly iterating through all the elements. We are traversing this complete tree. So clearly o n is there at least. But after that traversal, we get this gas, which we need to sort individually. So the sum of all elements, in all the elements, in this case, it is same as the elements here. And at max, that says, in some case, we have all elements compared come in order of n. In this society will take n log in time. And it's just we are split, splitting the complete end into different ends like N1, N2, N3, and sorting them individually. So overall it can take in login time. But in most cases, it should be, let say we divide into n parts, then n by ten log in button. So it will be and login only. You can do more time complexity analysis, but it looks like in login here. Now let's write the same thing in Python. So we will have a result which is a vector or a list. And if the root equal to, then return result, LSB will have a cache, which is a dictionary. And then we will define our dfs function. And here we don't need to pass these discuss and the min and max since we have added this to the self. So if this column has already, if we have already inserted subelements corresponding to this column, we will simply get dark vector and append this value also the rule and the current value. Else we are inserting it for the first thing. So you can also initialize and this bit empty list corresponding to C and then just appended. So both are same. And this will be here. And then we call DFS on its left. And its row number will be one more and column will be one less for left. For rate. Again, rule one more column is also one more. So this DFS terminates. And when this completes for this tree, then we will have this Mansi Maxie and casts ready for us. So we just need to do the sorting. So foresee in range. So this c will take a value of minus 2 first for our gambled in minus1, 012. So we pick the vector corresponding to this column and sorted. And the business of sorting will be the first value, which is rule number. And then second value versus the value itself. If through numbers are same, then we will extract value from all the elements of this vector and puts it into this vector which will be pushed to the result. Also, we have not called the DFS itself here, we should call DFS on R2P, Ruggiero column gill. So this will be missing. Let's run it again. And Python volition is also accepted. And here also we are good. We are at the peak of the distribution. So I hope all the solution is clear. The min, crux of the problem is in building this gas when we are traversing. So then we go left, the column number decreases by one. Then we will rate column number increases by one. And we're keeping track of what all elements are in a given column number for all the columns. And then we finally certainties based on rule number followed by the value of the elements. 29. Closest Binary Search Tree Value: In this problem, we have to find a value which is closest to value of one of the nodes in a given binary search tree. So let's say we are given this binary search tree and we are given a target value. And the target values, let say 3.6. So this is a binary search tree. So everything in the left sub tree, every node in the left sub tree will have a value less than the R2P. And everything in the right subtree has a value more than root two. If you look at this tree, then you will find that this norm for it has the value closest to 3.6. If you subtract from five, you get 1.4. Here you get 0.6. The difference we are interested in absolute value. Here you get a difference of 0.4. So this is the closest you can verify for other nodes as well. And this question has been frequently asked in interviews of Facebook, and it's very frequent. So let's see how we will solve it. So when straight way would be to do the traversal of this tree, complete tree and keep track of the minimum. So we have a target equal to 3.6. So we start traversal from here. You can do any traversal or any of those traversals will take often if there are n number of nodes in this tree. So you are after the R2P, you compare the value, you got a difference of 1.4. Then you go here, you compare again. Now you get a value of 0.6. So you get rid of the order, order value since you are the better value, 0.6, and you also keep track of the original budget, then you come to two. The value is 1.6, so you don't update it, then you come to four values, 0.4. So you are the better value. Similarly you go to six and you don't get a better value. So this will be a new way of doing it. If you're not coming with, coming up with any solution, you can do this traversal. And that should be fine fought initial approach. So that will take O of n time. Clearly, there is no magic tricks here, but we can do some optimization here. So let's say there are a few cases. So we will definitely start from the root. And this is our target. So maybe root is equal to the target. This is one scenario, one good scenario where you can straight away written. Second case would be that naught root, root two dot value Vn. Second root dot VL is more than Target. And third, root two dot v l is less than target. So in this case, we can return root dot val. We don't need to compare since the difference is 0. But let's say root, roots values more than target, which is the case in this example. So we know that everything in this right subtree here we have just one element, but we can help thousands of elements in the right subtree. So if root is more than target, then all of these are more than, more than root also. So if route header difference of let say delta, that means root minus target was delta. And everything in this is more than root itself. So you are adding something to route, let's say x. So this delta will increase. So there is no point in looking in right subtree. So you come here, you either take left subtree, right subtree. You can also return based on disk. So next you come to three. Again. If this value is less than target, there is no point in exploring the left subtree since these are further smaller, so your delta will increase. So at any point of pain. So this is the same scenario here, what we got. So if root is less than target, then everything in the left will also be less than target. And in fact, there will be less than root also, so there will be farther away from the target. So let's draw something here. So let's say this is Target. And in one case, root is here. So this is one case. And the other scenarios that route can be here. These are the two scenarios and tardies that root is here. So if root is here, everything in the right sub tree will be here, here through, if this is the distance of target from root, the distance of directed from all these nodes will be even larger. Desert, right subtrees, nodes in right sub-tree. Similarly in the other scenario, these two will not occur simultaneously. Either this will occur or this will occur. And in the other case, rupees less than target. So this is the difference. Everything in the left sub tree will be lengths and we're here to the left of root. So delta will be further larger. So there is no point in looking at left subtree. So what we are doing, you can clearly see we come to route. We either take left or right. Martin bought like civic tech left here again, we either take left or right movement. Let's again take left here also, we choose one of those, and so on. And we will stop when we reach the end or we get a value exactly equal to target. So what is the time complexity here? How many nodes we will traverse? So in the worst-case, if we are unlucky, we will choose the part that is having the highest deft. So we have different branches in the tree. Some of them end early. So these are leaf node, is a leaf node. So some of them, and very early, some of them go very deep. Not all believe econ left. So in the worst-case began app off its H is the height of the tree. And again, for binary search tree, the height can go up to off. In when we have a linear tree late dark, let's say we have 12345 and so on. So definitely the worst-case is off height. But height can in turn be often. So it can be often were definitely we are doing a lot of optimism in our naive approach. We cannot claim that the time complexity will be all fetch there. We have to visit all the nodes. But in this case, in the worst case, we reject the part which is off longest length. So in this case we will say off its. So let's write the code for this. We will write in C plus, plus Java and Python. So you can go through this navels or given one example, which is very similar to the example we saw. So if root two l Is more than target. Then there is no point in searching in right subtree. So we have to only search in left subtree. But we will also check if left subtree exists or not. If Rudolph valleys larger than target, then everything in the right subtree is larger than root. And if left subtree does not exist, then we have to return the root itself. So we check if left is present, then we will traverse in the left. Otherwise we will return. And let's say the root returns glue just value. We are calling it recursively. Root left and target remain same. It did not seen. So this will return this value for the left subtree, which is though value closest in the left subtree of the root. And we compare if EBS L minus target is less than EBS val minus charge to them. We returned, else we return root. And the second will be exactly similar to this. It has to return either here or here. And let them target exists. Or if none of these scenarios are there, that means root value equal to target, then return val. And this works for this case, but this example is not good enough here. It was the root itself, so we are not sure whether we have written all the guesses correctly. So let's make our value of 3.4. So this would be, this would return three. And this returns three next to, let's make it 2.6. So it should return again tree and it's valid. So let's submit. And the solution is accepted. And we are around here, 79% of the excepted submissions. Now we will write it in Java and Python. So if you have understood it, there is, there should not be any confusion here. Also accepted. And again, we hear it on a 100%. Finally, we loaded in. And the volition is also accepted. 30. Path Sum III: In this video, we will solve part some version tree problem. And it's one of the favorite interview questions as to why Amazon. So here we are given a binary tree and we have to find different parts, just counterparts and not the actual parts with some given value. And the condition is that it should not start from root or it's not mandatory that it starts from Luke. It can start from anywhere below root also, or including Rudolf robot. And it need not finished at the leaf. So it can start somewhere in the middle and end somewhere before reaching the lift. So that's fine. Only thing is that we can only go downwards. It's not that some part we include here, and some part we include here. So the part should not be eaten like this, which spreads from left going through till Right. So there will be one starting node, and from there we will always come down. So it may be like this, not branches. So if we come down from here and here also, then this will be branched. This will not be apart. So let's see how we can find that we will be given some target sum. And the sum of that parts will be nodes on the path will be equal to NAC target, target. So here the sum is eight and we have ten here. So if you see here, you see that 53, this is one part with some miss it, then we have this 521. If you sum them again, it's it. Similarly, if you sum this minus 311, again it, it, Cleveland negative values are there. So there are three parts. So in this case we will written three. No. Oh, how did we arrive at these solutions? So what are the solutions? We have? 5-3 then via phi R 21 and we have minus 311. There are two things. In one case, we have to look for, but which includes route. So if include route in the part than the remaining sum will be yt minus the current value that is minus 2x. And negative alarm since the North's can be negative. So if it goes negative, it does not mean that we cannot find any part below it. So we can find, so case one, we have to look for all the parts which including root. This is case one and case two, where root is not included. So what will happen? In this case? Sum is updated. So in this case, sum is updated to some minus Router.route l. And in this case, some remains same. It is not changed at all. Since we have not included the route, we are explicitly dividing it into two scenarios. In one case we are including the root and trying to find the remaining sum below it. In either case, we're not including it at all. So we will try to find the exact same sum in just this part left sub-tree and right sub-tree. So this is the difference, or in one case, sum is reduced. Or maybe increased if this value is negative. In other case, it remains same. So we need a way to distinguish between these two sums. So we will have a main function, let's call it hotpots sum. And it takes root and sum. And now we have to divide it into two parts, case one and case two. Let us call them F1 and F2. In one case, we will pass the sum. So let's pass the sum in both of those. And then while defining them, we will differentiate. So in one case, we will calculate f of one Rutan dot left and then pass the exact sum plus N2 rate. And exact sum in this function called sum never changes. So this is the case where we are excluding the R2P and trying to find the exact sum in its sub-trees. So this will be done by oven. We can use part some as one of these, F1 or F2. So we will make the changes in the core. So this takes care of one case. Then the other cases, we have to include the current value and pass the remaining sum. So the job of that function will be to always include the current value since bricks are not allowed. So you include that and parse the remaining sampling children. And there, we should not mix the two things in this case. In this case, it's not that we have past, let say here we had eight and this value was two. So we passed six here as the sum. The job of this function is to find part of length six. So in this case, we have to always include this value. It is not that we did not include that. And here we found a part six and we return its current. So this two and this six cannot be included. So one function whose job is to always include the current value and pass the remaining value. We cannot mix the two functions. So this F2, what it will look, it will include the current value. So it will call F2 Rutenberg left and some minus root of L plus F2 Router.route right. Some minus root naught over l. So this is the second case. So the way F1 and F2 are defined is different. So we can also use the original function has F1. And here what we will do. So you should be convinced that this would work if V divided separately into F1 and F2. And what we do from Potsdam is that we simply written F1 plus F2 root sum. Then F1 and F2 handle it differently. In one case it always exclude in uppercase Integer includes. Also. In this case, what we will do, we can define it like this. So in this case, we also have to look if roots value. Is equal to sum. So we had been including a few nodes before it. And know we are here at this value, let say. And the remaining Sam was three. And before it we had some minus T. So we had to find a path of length three, and this value itself is three. So we increment the counter by one. So while returning we can add one to it. So this is one more thing that we need to pick it. And in both these functions, if root is null, we return 0. So in part some we can rate, but some parts and will act as F1. I left some plus, but some, right? Some plus, whatever is F2. So pass route. And so it will start including root and passing the remaining values. So this would be able to complete function. Let's write this in C plus, plus Java and Python. So I have pretty much covered everything what's given here except for this and this. We don't need for our kids. And what's the number of nodes? We will not be writing anything specific to this. So if root is null, return 0, else return, but some of them, we are excluding it. And let's define another function also. So if this is the function where we're always including the current value and then proceeding below. So if at any node we reach in order the required some below it, including the current node, it's a Muslim. Then we increment the result. We add to the result. So we have not reached the sum. So whether we have reached the summer, not if we have already reached the Sun, then we will pass JRuby fluid. Since 0 is also possible, there can be positive and negative. So we just increment of root left and the sum minus 2k. And the same thing for the right. And finally, we return the result. So we pass the same sum and tried to find the sum in the left. So this, we'll do that thing. Then. Then this function takes care of including the root and everything below it. And then the same thing for us was right. And the solution is accepted. And we are writers. So we're right here in the top. June, if you try a few times, I'm pretty sure you can reach the top also. So let's write this in Java. And the Java solution is also accepted. And here we are slightly around this peak, so there are a few distributions and we are in this distribution. Now let's write this in Python. And the Python solace and is also acceptor. So what is the time complexity here? If you see we are in one case, we are not including it and then calling it recursively on left and same on rate, so that whichever was the complete tree. And we have another function where we include this and again, call it recursively on left-hand rate. So we are doing to traversal of this tree. So it's off in. And if you look at the space complexity, then we can have in worst-case, a long tree and all the nodes are in the stack from since tag. So if you can't function stack as the space, then that will be often. So Tammy's different, definitely often. It's in fact Beethoven or the space. If you can't, function stack ISPs and then it can walk too often. Other ways. If you don't count it, you are only looking for auxiliary space. Then we are not using too many variables, so it should be off one in that case. 31. Sum of Left Leaves: This is one of the EGL binary tree problems where we have to find the sum of all the left leaps. So how we should approach this problem? So a simpler version of this would be that find the sum of all the leaves in a binary tree. In that case, what you will do, you will start traversal. You can pick any of those traversals of the trees and you have to check whether the current node is leaf or not. And what is the way to check that it's left and right tail should be null. For jumble. There is no left child nor Rachel to it's a leaf. Similarly for four, similarly 46. So in that problem you would simply add the value of the node to do some Nadia had been maintaining. So that was simpler version here. There is slight modification to that, that it should not be just delete, it should be left leaf. For example, in this we have three leaves, but two is the only lift, lift, left leap means it should be done. Loved child of its parent for you also leave. But it's the right child of experiments. Similarly, six is the right child of its parent. Let's say we had something like this here. And let's say it was then then 210 what would have been left child? So what thing you need to make in your earlier approach? So when you are traversing, if McClellan will start from the root since you are given the root pointer only of the tree. So when you call the traversal on left jail, you pass an additional flag, true, to indicate that it's the left child of its parent. So this will be called for 346, you will pass false. So six will know that I am rates a lot my patent, so that if I am leaf, I will not end the value. And then six calls recursively for its left side, it will again pass true for left and falls for rate. And this will be done by everything. So trivial pass through here and false here. And every time we are checking whether we have, we are leaf or not. Note you will find that I am a leaf, then it will check ME left child of my parents. Yes. So it adds the value of two to the sum that we are maintaining them. Ultimately when we reach for it will check that I believe, yes. But it will take ME left child of my parents. So it will see that no, I am not. Because I heard guarded value falls from a parent, so it will not add its value. Next, five is not leave, six is not leave, but ten is leaf. So it will check whether I am left, Jay Lerner and it will find that true. So it will add into it. So total it will be done. So writing the corpse would be very simple. So we should have some, some leaves, left clips in fact. Or let us call this L, L insert. And we pass route. And a flag. Boolean flag to false. So this is L five, false. Then if is leaf. And what will be the check? It will be very simple. Nor dot left is null, nor dot right is null. So if leaf and this pedometers, so let's call it node N, and this is a left. So it is leave this NORC and is left. Then some plus equal to n naught value. And we return from here. If this is not leaf. So if n dot left is there, then recursively call left and pass through. And if N naught is there, then call SLL n dot, right? But plus false. So it's a very small group. So if you are a family with Jefferson, Then you so drag discord very easily. Now let's write it in C plus plus and java. So it should be very simple what we saw. So there is a base case which we had not talked here. So if root is empty, root is null, that is, tree is empty, then return nil. Else we will have a variable for some initialize to 0. And let's call our function sum of Left believes. We can have the same name, but it will have different parameters and different return types. So we are passing this extra flag is left here what it should be first check the leaf. And checking leaf is required only when its left child if it's a rachael, no need to check the leaf if is left and so it satisfy the condition. So sum plus equal to val and return. Else continuity traversal. For left we will pass through and forward rate, we will pass fault. So if there is just one node, let say just to one node, that is loop. So we will consider that not the left leaf. If there is a just to one node in the tree, node is a leaf, but we will not consider that. We will pass 0. In that case. That way we are passing false for the Root, Mean root of the tree and the value matches. So let's try a few more cases. Let severe empty, then it should return 0. Let say the L1 norm. Then we have to, then left is null. Right is three. So this is 24, this will return 0, this should return 0, this should return 0. And it's correct. Let's submit and accepted. So what is the time complexity here? And just we are doing one traversal, so it's off in any little number of nodes in the tree. No, let's write the same thing in Java and Python. You didn't non-return. Otherwise we will call this traversal traversing the tree. I'm just accepted it in my country. And low. In the main function we will check if. And the Python solution is also accepted. 32. Delete Node in BST: In this video, we will see how to delete a node in a binary search tree. So first of all, what the binary search tree, it is a binary tree, so it can have at max two children. And it maintains the search property. That is, all the nodes in the left sub tree has a value less than the root mood. And all the values in the right subtree have a value of more than root node. And this is true for all the modes. For example, this is valid for this MOOC. Four on the left subtree will have less value than fight. Similarly, it's also valid for the small. So left side will have smaller value. So such properties are maintained for all the modes. So in this, we have to delete a node, so we will be given one value. For example, let's say we are given that pointer to this root node. And we are also given a value to delete, delete Lipset tree. So first we have to sludge that value and then we have to delete their value. These are the two steps. And if that value is not present, we will not do anything and we will leave their tree and changed. So let's see what are the different scenarios and what we should do in each scenario. So first case is that that node is not present itself. So let's say we want to delete 15. We come here, we compare that 15 is more than ten, so we go to the right side, then we see that 15 is more than coal. So we go to the right side. But right child is null, so 15 was not fun, so nothing will be changed. Next guesses. So case one was value not fond. In this case, nothing to read them. Second kisses nord, that we want to delete. Node containing the value that we want to delete is the leaf node. So let's say we want to delete either for Maine or 12. So phosphate will search it. So let's say you want to delete four. So what we will do, we will compare with the root. It's less than root. So come to the left side, we will never go to the right side again. So either we take the left or right mode. So again, 40 is less than this, so we come to the left side and no foreach same as the current node. So we have to delete it. So simply make this molten null to this node is gone and the liftoff or seven is not null. So this non-defective ligand goes away. So this is the simple, simplest scenario where its leaf node, then what we do, find the node, one more pointer and make it null. And we are done. Then we have another scenario where it's not a leaf node. For example, let's see here. This is the third case where we want to delete non-leaf node. And let's say we want to delete seven here. So we compare with Tim. It's less than ten. So we can go here, call the same function, delete function that we want to implement. So delete root if and also there will be one value. So if root two value is more than value, then we have to delete in left part. So the root dot left equal to delete root left. And the value that we want to delete. So this would return pointer, this delete coltan that root node. So in this case, seven was less than value. So the liftoff or ten will become whatever it is, the root return by distance Delete on its left. So we believe on the recursive function to do its job. So this recursive function job is to find and delete a node in the tree rooted at this node. So now you know that that subtree is in the left part, since each value is less than root. So we call that function again on its left subtree and positive value. So assuming that this function works correctly, it will return the noodle updated root of the tree. So it will delete one from this subtree and return the updated root. And that will be done left off them. And similarly, you can write the case where this value is less than the liter, right? And targets will be even. Root val is same as well. In this case, we are at the current node, so we have to delete the current mode. So when this or deleted coral for this subtree, then in this call route will be seven. And when we compare its value, it will match. So it will enter this scenario. That is, we have to delete the current mode. So we check if it's left and right channel, then that will be the previous scenario, that is leaf node. So that is the way to check here also. So I am not written the court, but that is how we will check. So if it's left and right terminal, simply make it null. But if it's left is presented, right is present. Them. We have to do some work. So let's see, left is present. So in that case, we will find the predecessor, in-order predecessor. So one of the properties of binary search trees that if we print the in-order traversal of this tree, then we get this sorted order. So if this is a root node, all the values in lifts up left sub tree will be here on the validation rates of trivially here. And in this tree, in this subtree, we have to delete this root node. So either you delete the exactly predecessor of this or the successor of this. So whatever is the value copied here. So four comes here and then deleted. No, or it's a valid Since we are finding on the largest in this park. So this predecessor is the largest in this part, and the success rate is smallest in this part. So if you copy either this or this to due to this node and then deleting this, the search property will weaken valued. But if left is not there. So if left is there, then find the predecessor copied here and delete NAT predecessor. And we will do each of these recursively. So now let's look at the case where left is nitrogen. So it's up to you to check right or left, it's up to you. So if you pick first check the right, you have to pick the in-order successor. In order successor is the smallest among these. In order predecessor is not largest among these. So if you copy one of these, two, this root node and then delete this. So it's TreeSet salary valid. So here let's say we have to delete. Seven and there is one mistake here. So this will be main and distribute. Since this is left of this future is smaller. So we have to delete seven here. So we come here, we call delete n seven and this ten is not interesting. What Nordic Tim, let me circle it. So it will check if its value is more than this or less. So this value is less than current norm. So N dot left equal to delete ten, not left. And I will write seven here. This circle denoting the norm and the values seven. Now, it will check that seven matches with the current node. So we have to delete this. So we check if seven has left, dot-dot-dot, it has left, then finder in order predecessor. If it's not, do them. So first of all, check whether it is leaf or not. So if not left and moderate them, make it null. It's a leaf node. If left is they're finding order predecessor, copy to value here and delete the Calder delete_one In order to predecessors. And in this case, right is there, left is not there. So root of L equal to in-order successor of this node. So in order successor is word. You go write once and then keep going left. So you come to nine and keep going left until you reach, until the left pointer is null. So that will be in order, successor and predecessor will be go left and then keep going, right. So this will be the largest in this subtree. Why? Because the rate of this will be larger than this. In the left, everything will be smaller than this. And we're going right. And going right means larger value. So keep going rate until right is null. So this will be the largest value in this subtree, left subtree. So it will be in order predecessor. Similarly here we go right to enter the right sub tree. And anything to the right of this will be larger than this. So we keep going. Left wing lift means smaller value. So this is the smallest in the sub tree, right? Sub tree of seven. So finding order successor, which is eight. So its value now becomes it. Then it surveyed will be calling the same function, delete our On its right sub tree, that is rooted rate. And we have to delete, in this case, this v AB copied the value here, now we have to delete it. So I'll just pass that value. Root not well. And it will take care of this. It will again come here. See, nine is here, so it is smaller, so it will go left. And again, it matches. Then it checks whether its leaf or not. If its leaf, it will just make it null. So ultimately, the final deletion will happen only at the leaf level. So this is how we handle all the cases. Now let's write the code for this. Let's analyze the time complexity also. So what we are doing, we are starting from RUP and then depending on the value, we either go left or right, not mood. So in worst case, we have to pick the branch with the highest in-depth. So time complexity will be order of height. It's balanced to a good extent, then it will be log n, where n is the number of nodes. So if it is balanced, then the height will be our daughter of login. So that's my time complexity will be real data of login and space. We're not using explicit to space. If you countless recursion stack space to convey that, then it again, can we order of height? So let's write the cool. If root is null, then not include them. If values. Then we have to delete it. Right art. So left part and the router itself will be unchanged. Only right will change. And very similar to this will be the left cookies. And lt means we have to delete the current node. So here we will have to find the successor or predecessor. So first check if it's a leaf or not. And that will be the good case. If not crude dot left and not root, right? Then each leaf, then I'll just make it null. If left is present. Find in order predecessor. And we will define this function shortly. And then so this value is now updated with the value of in-order predecessor. So we have to find and delete that value in the left part. And the equivalent case will be. Or we can ignore this. If, if water Narayanan and left is not null, then this else means right did not Min and left it in. And we will also define this function. So predecessor, we have to just move one school left and then keep wing write equal to root node left. And we are already checking for the validity of a group. So it will be only called when this little cleft is valid. So no check required for root. And then relay. And when rate becomes null, return is very similar, will be the in-order predecessor, successor. So let's see. I'm originally accepted and it's better than 90%. So there is some optimism that you can make here. So for example, here we are finding the in-order predecessor. So it traverses from this routable. Or let's say we were finding the in-order predecessor of three. Or let us take a bigger example. We were finding in order successor. Let's see, we have a right sub tree and it went here than here. So it traversed this part. So we're calling this a two dot rate equal to delete in this part. So that will again traverse this part. So you can save some time there. And by keeping track of the parent node where you found net value in order successor, and then directly go there. So that will be some optimization here. So let us complete this in by two. So daunting here and what changes are required? Finally, we will look in, so you can see some difference here that it because it will be preferred in order predecessor or successor. So if you choose successor, your different answer me very. Since you pick the largest top left are the smallest of rate, and that will make a difference. And the Python code is an exception. 33. Sort All elements of 2 BSTs: In this problem, we have two binary search trees. Not just when retreats, but binary search trees. And what we have to do, we have to return a list where the elements will be all the elements of a binary search tree one and all elements of secondary. So if there are even duplicate values, it will be there and it should be in the sorted order. So regarding binary search trees, you must know that when we do in-order traversal of binary search trees and, and the elements are in the sorted order. So how can we do that? So let's say we have two binary search tree. Then in that case, what should be triggered? We have total of two to 46 plus 511 elements. So the smallest is this one. These are the two smallest, smallest among these two. Then next is three. The next is one of these foot. And then the other four, then 56789101224681011. So this would be the answer. So how we can do that? So when oh, very straightaway solace and won't be dark, traverse the forestry in any order, not necessarily in order, order, post order any order. Just visit all the nodes and put it in a list no matter what order. So 49871012. And then put these in after that. So 23465, then sort this. So what will be the time complexity here? So you have to return this list anyway, so you are not using any extra space for that other than the required result. So here if we have immigrants and in this we have n elements, then time taken will be m Here in here, followed by m plus n plus n plus n log m plus n. So this will dominate this you can ignore. So this is order N complexity. You can do some books here. You can do it slightly better. So do it in, in-order. So forth. 7891012. So first let's use the same list. There are multiple ways of solving it and you must have figured out a few ways. So decision NIL Low end, then we will write the contents of second one in green. So 23456. So this yellow and this green are already sorted since we have taken in order traversal. Here, if you are starting the completing the week traversal you take does not matter because we are sorting it after on here also we will sort, but we know that if you do in-order traversal, this will be sorted. Similarly, this will be starting. These two are from different trees and we're not using any extra space. This is the list that we want to return anyway. Not keep the pointer of foster one. For both of these, whichever is the smaller put deck. Post data ahead of this two comes here and it's disappears from here and then increment the pointer again compared to the smaller suppose three here after this. So this does not help much since if this is some kind of container and in cplusplus, I guess you have to return a vector. So inserting in between and then sifting everything that's often. So it may even reduce the time complexity, increased the time complexity to n square, that is m plus n squared. So it does not help. But you can use this same thing that is keep two separate lists. So keep to temporary lists. And then what we will do, we will do the idea similar to Mozart. So we have two list. We have to merge them into one. So we have two pointers. One here, one here. This is initially empty vector. Or you can, if you know the site, you can initialize the index site. Do you smaller? So insert two here. We are just pushing back, so it's constant time. Then we compare with 343 and we compare four. And for anyone, then 70445575677, sorry, six. And then this is empty, then put 7891012, and this is the answer. So what is the time complexity here? So to get these two, we took M plus N, We did traversals and then merging you take another n plus n time. So overall time complexity will be m plus n. But here we have two species. One is for this result. So in any case you have to use this piece of m plus n since we have to return this list. But here we are used to extra services also. So this would also work fine. It's simple to understand and you should try this. We will go one step further. And instead of using two complete sage vectors, so in this case, we will definitely use m plus n space because the size of this Foster vector will be m Sigal, the second vector will be in. So slight improvement we can do is that we can do it in one path. That is while doing the in-order traversal itself. We keep a stack. So here we will do in order traversal using stack and not recursive. So just to briefly recap how to do in-order traversal of a tree or without recursion. So we keep a stack of it plus root into the stack. So any shear, and then keep going left. Update the current pointer. So current is here. We have inserted current and then current becomes its left. So you come here and again insert the current and current conserves always left. So we insert four and current digits left. So current is now, current will become null. So we stop. When we stop what we do, we pop this top, top element supported here. And whatever we have popped. Our current becomes it's right. It's right, is empty, so nothing will be pushed here. So now this is the stack. Again, be Puppet seven. And whatever you have popped was its right. So we post-its right. These two are gone now. And again, repeat the same process that is keep going left until current is null. So current is here. We pushed it, current is here, we pushed it, current becomes null, so we perfect. Okay, so some inconsistency here, because we have made nine as the left of it, which is invaluable. It should be, this will be nine, and this would be it. The tree was drawn wrong. So then we came here, we would have pushed nine here instead of it. And then eight. And now current is null, so it is here. This is gone. The nine, none of them hung, right child. So we can keep popping $90 a pop. Then we pop them and then we push it right, that is 12. And then current comes here and we try to go left, but it's null. So we popped up. Nl, its rate is also known and we are done. So this is the way we do in-order traversal using stack. Stack will not be always containing all elements. It will contain at max, this kind of depth of the tree. So here, what optimization we can make instead of using two complete say's, vectors and species, we can have two stacks, S1 and S2, and then do in-order traversal for both of these. So remember we keep going left, keep pushing to the stack until current becomes null. And we're always making current equal to its left. So we come here, here now it's null. Similarly here, here now it's null. So let's run through this example again. So we have post-tax these all around. This is nine, this is eight. S1, S2, S1 is 431. So it has m seven. For now we will stop since current has become one. If we make it left and is two, we will have 532. So here we will stop and then compare the top values, which is smaller. So clearly Twitter is smaller. So please popped and we'll look at its rate. Its right is null. So we will not insert anything, go to three. And then up three. Or rather compare first because here we have two stacks. So again, three is the smaller, the pop tree and puts it right. Again. So these are, this is done again compared to 40 smaller. Let's understand. We picked this one. So four, we popped. We removed from here. It is right is null. So we come here. Now again, we compare 74, this four. So this is also popped and we go back to five. Next conversion will be from 705. So we will pick favorites. Then five is popped and we inserted, right, that is six. And here we compare. 676 is printed and we pop it. It's right is null, it's left is not. This is done. Then we have seven here. So we popped Bob's Ellen and usage rate 70, iterative nine. And keep going. Left. It also, now we will stop. Now we will compare against this, but this is already empty, so no need to compare, just the normal in-order traversal process. It iterate is nothing to fear. Then report name. Its rate is also null, nothing to loose here. So next one is 1010 is in the stack. So the puppet. And then posits right, that is 12. Next, we tried to go left, but it's nothing's there. So we pop bell and we are done. So this is the list. So here, at a given time, the stack was holding at max three elements. So that will be proportional to the depth of the tree. So here the space will be of the order of it's x1 plus x2. You can take the maximum worst-case deft. So from m plus N2, N1 plus N2. But again, this is not that important. You will anyway be returning a list of size m plus n. This will just slate optimism and making the algorithm a bit more elegant. So let's implement this last step loot. So before that, I would highly recommend that you just take a small binary tree, no matter it's mandatory or binary search tree, and are trained to do in-order traversal off from that tree using stack. And once you are comfortable writing that, then try to implement this. This mattered, and that should be simpler for you. So let's begin. So these are a few examples. Nothing special. Layer 23 node pointer and we have a stacks S1, S2. Then the result vector, r1 and r2 are the roots of the two trees. So it's late route when is there or group two is there? S1 is not empty or S2 is not empty. We will continue so that we put all the elements in the result and don't miss alternating. So first process the root one by one. So this will act as the current that we were talking. Current norm for the tree one, S1 dot Whose root one and root one equal to root one left. So this will stop them. Left is null. So this will be the minimum, minimum in four Street at the state when this while loop ends. Similarly. Similarly for x2, now this will be the minimum. The top of the stack will be the minimum in the tree which VM anarchic inserted in redirect. Then there are a few scenarios. Either S2 is empty. If estrogen D1, then we pop Only from S1. Or there is another case where we will pop from Islam, which is s1 is not empty. And S1 dot, dot, dot val. So this top will return a null pointer. So in order to get the value, we need to use this that. So when S2 is empty, this, this part will not be executed. So this part is execute, executed only when S2 is not empty and S1 is not empty, we are adding anyway. So this case is for the case where both S1 and S2 are non-empty, then we will compare the top values. But if one of them is empty, then just pick from the second one and we will write an equivalent case, equivalent opposite case, that if S1 is empty, then pick everything from S2, or if both are there and the other case. So we have tried to combine it intelligent, intelligently so that if S2 is empty there, we will pick, you will always pop from S1. Or the second scenario is that both are non-empty. So S2 is not empty and S1 is not empty and is smaller than the top of a sonnet is smallest. So in both the scenarios, we will only pick from S1. So root 21 equal to s1 dot, dot. And then pop it. And we will have exact scenario of this will be, we will bought from S2 to S1 is empty. So if S1 is empty, you will always pop from his two or both are non-empty. M is two, top is smaller. So line 17, I accepted, and we're right around 96% of the acceptor submissions. So you can see we have two peaks. Mean distribution is in this part and it's highly distributed. So let's rewrite this in Java and Python. Okay? Separately. And this works. Submit, solution is accepted. And next we will write this in like three. So minus one means last element list. So it's acting as tech accepted. 34. Maximum Depth of Binary Tree: This is another binary tree problem. Here, you are given a binary tree and you have to find the maximum left on binary tree. So clearly if you have a binary tree like that, so Dr. means or how deep you can go. Maybe there was an old here also. So in that case, this is the deepest part, the leaf net as far the strong root. So in this case, you have to be 1234. So how do we calculate it? Again, it's a recursive problem as like many other main retrieved problems. So let's see how we can solve it using recursion. So remember Dr. We had taught that in recursion, we have to solve for some function in terms of n. So here, let's say n is nothing but the height of the tree. So we have to think of given f x minus1, how we can solve it. So remember that I'll be hub height, which is this one. So this spot, we'll go from root and it will take one of the children of R2P, maybe both have same heightened, but at least one of them will have that part. So now lets say we have to calculate maximum depth from here. But let's say you are given maximum depth from 23. So two says that the maximum depth from me or maximum height from me is three. And the right child says that the maximum depth from me is one. So this root will see that if I take this, I will reach the deepest. So, so given the solution for 23, you can find the solution for Q1. So this was the concept nag react dot. Well, studying how to solve recurssion problems. Now, if h minus one will depend on f, h minus two and all the way up to F. So what should be GTL 47? The height will be one. And if it goes further to one of its children, its left child will say that I have a deal because it's null. Similarly, right, child. So base case would be that if it's null, then you, So this is the case of n node is null. So now this problem is clear. Let say we have to rate the Max-Cut max and deft. And we're given 2p. So base cases, if root is equal to null, then return or else we will return one plus max of these two max of this drift. And this, whichever is max and one for this root itself. So one plus max of max deft same function recursively. Root left and maximum liftoff. Right? That's it. And our recursive function is complete. So let's write to different languages. So first let's right down into the plusses. And I was always, so let's submit. And the solution is accepted. And it's, it millisecond that is better than 96.4% submissions. So now let us see what is the time complexity here. So here we are just doing one traversal of this tree. So it's just visiting each normal ones. So painless of daughter off in space, can we, in the worst case, it can be of an order of when due to that stack. It may be linear kind of tree and not really balanced tree. Then all of these will win the call stack. This we will call this, this will call listeners will call this hands-on space. Can we, or in general, H max, maximum height. Let us complete it for other languages. And it's even better. Knowledge solute in Python three. And the acceptor. 35. Tilt of Binary Tree: In this problem, we will see how to find the tilt of a binary tree. So what do we mean make dQ? So you might have seen a weighing scale like this. So we have two plates. We keep rates on one of the plates, the skill and actual object to be measured on the pen. And then we hold it like this. So whichever is heavier, it gets on that side. So exactly same concept is borrowed here. So first of all, it's binary, so very similar to this one. And then what does depend on if both the weights are same, there will be not. It will be horizontal. If one of the weights, weights on one of the sites is a more than it will delete on that side. And it will depend on total weight. If we have five objects here, it will be the weight of all the five objects combined. Similarly in the binary tree, we may have, let say, ten nodes in the left side, five nodes in the right side. So the sum total of all the nodes and sum total of all the nodes in the right. And whatever is the difference, if differences do, delete it also 0. So we are interested in absolute difference of all the weights in left subtree, all the weights in right subtree. That is the truth of each node 43. So let's run through this example. So let's draw this tree. So what did the tilta Phi in order to calculate the delta phi, we will need the rates of combined weights of all these marks. So it does not know yet what is the combined sum. So it will ask its left child, I want the cumulative weight of the subtree rooted at you. So this also does not know. So it propagates further and it asks its left and right child, give me Doc combined total weight of subtrees rooted at you. Now it comes to, to, not to notice that there is no left sale nor a tilde. Or it asks its left and right tail, which are null, so it returns 0. So do news denser. So it can immediately return two. So two also fills itself too. And it returns two here for all the nodes denser. So it returns four. Now this knows that it's six years, the sum total, because this return to return for. So you can see the recursion here. The root calls left, left calls it's left and right. And once left wisdom, it will call the right and so on. This will happen for all the nodes. So it's just like any standard tree traversal. Now, six mod three node tree knows that the combined sum of all the nodes, me is six, so it returns six here. Then it asks its right child, six, which most dancers, six. So now it knows that it's 12. So this was six and this three also needs to be added here. So this is a mistake. This is nine. Four plus two plus three. So what will dancers from left and so from rate and add the current value. Just like any traversal in this case, most likely a post-order. So ask him traverse the left subtree and get the cumulative sum, right subtree and get the cumulative sum and add itself. Or you can get this value, then add this value, and then this flow in-order will also work. And now it returns nine-year. It returns six here. So 96 is 15 plus 520. So this three nodes represents the cumulative sum. Now using this, we can calculate the 2D. So here for this node fight, so don't look at this. It corresponds to phi. Left part is nine, right is six, so 23. And you can manually verify that four plus two plus three is nine. And this 86 or differences three. For three, the differences four minus 224 to four leaf nodes tilt is 0, so 000. And in this question we are just interested in total cumulative 2T. And we are not interested in this tree. So it will be three plus two, that is phi. So we can do it in a here we used to traversal phosphor disc calculating the cumulative sum. And then for calculating the date, we can combine these two steps. So we have a recursive function, let's say find, dude. What did we do? We can call another recursive function. Let's call it dfs and we pass the route. And what did we do? It will check if it's null or not, if it's non-return. Needle. Other ways calculate the sum for left subtree. So DFS left them DFS, right? Then add these three values. Or take a global tilt which is initialized to 0. So now it has the left some, right some. So it will calculate, delete whatever was the global tilt, add to it Absolute value of L minus arc, and also return the cumulative sum, that is L plus R plus root value. And from here we will just call BFS route and then return the 2D, this duty updated way, all the nodes, whenever they get this sum, whenever they have this sum in the left-hand rate, they can calculate their own tilt. And that's it. So what is the time complexity? Just one traversal of this tree. So it's often. And the space, we are not using any extra variable other than some local variables. But this tree may be very skewed. And we may end up adding all the nodes in the recursive stack. If it's perfectly balanced, we will not have more than are the rich. But in this case we can have off n if the trees very unbalanced. So these are the time and space complexities. So let's write the code for this. So we will need greet variable initialized to 0, and then we will write a recursive function, let's call it Find some. And we will pass the reference. So if this is a leaf node, this route, this route left to aluminum 0, right will also return 0. So d2 will also the engineering that case. Otherwise. If one of the nodes is null, then that is new. And here we will just call find some root and return to it later from this 2d. And this literally all the recursive calls. And let's see, undeclared R2P. And the solution is accepted. We will do it in Java and Python. And instead of passing made reference. We can also have it a member variable. And then finally we will Luton like them. So we go to the wrong into the flame sums, we need to call it. And the play. 36. Convert Sorted list to Balanced Binary Search Tree: Hello friends. In this video, we'll see how to convert a sorted LinkedList to a balanced binary search tree. Balanced binary search tree is a binary search tree. So with maintaining the search property and also the difference between their draft off left and right subtrees. So if there is a node here and we have a subtree here, and the maximum depth theory, let's say five. Then in this part it cannot be more than six or less than four. So difference can be at maximum one. And this will be true for all the nodes. That is, for all the nodes, you look at left and right subtrees, and the difference will not be more than plus minus 1. So for example, we have this sorted list, 1, 2, 3, 4, 5. And if we can work to a balanced binary search tree, it will be something like this. So if you see what is the liftoff left subtree of the root node tree, then it's two right side all sorts to, so for treats valid for two left subtree has a depth of one, right subtrees nil, so it has a depth of 0, so differences one. So again, the property is valid at two. Similarly, you can see that it's well, to all of who, all the five notes, it's valid at 500 hertz, 10. So differences one at one, both are 0, so difference is 0. Similarly here. So this is a balanced binary search tree. Now let's see how we can convert. What is the algorithm here? So when we are given a list, we have a bunch of values. Let's take a generic case. We have, let's say a number of values given to us in a form of LinkedList. This is not a hurry, so you have to iterate one at a time. So we have many elements and these are sorted. And you see that when we do the inorder traversal of a binary search tree, we get a sorted list. So this is already sorted. So you can think of it as the inorder traversal of the resulting binary search tree which we are trying to build. But this is not a simple binary search tree, it's balanced. So left sub tree, all the nodes have left subtree followed by the root node, followed by all the nodes of the right subtree. So this will be the order. So root will lie somewhere in the middle. So if it's 4D, it will exactly in the middle. If it's even, it will be one of these. You can pick one of these. So the algorithm is dead. We find the middle of the list. So at this point we only know a warp that the middle nodes would be root. So we make this as the root. Then we have this remaining elements in the left sub tree. So all the L will come here, then root will come here, then all the nodes of the right will come here in this list. So now you see that is naturally recursive is coming here. We are breaking the problem into smaller problems. Earlier we had a bigger list, which was l plus r plus r one, no middle. We have extracted as the root. And then in the left part, we have this list of length L. In the right sub tree, we have this list of length r. So the same function, whatever function we had written to. Do this conversion can be played on this part and the right part. Now we have a smaller problem. Again here we will find the middle, make this root. So let's take a concrete example. Let's take our original example, 1, 2, 3, 4, 5. Let's have five elements. Next is null. So in order to find the middle, we all know the slow and fast pointer concept. So we can have a slow and fast. You can initialize in multiple ways. You can keep both of them in the beginning, then derivative of one element. So let's assume is initializer for osteogenesis layer. And slow moves way one-step fast, most weight two steps. So when the farthest reaches to the end or one before then, when we hold the tail, then we stop. Then flow will be somewhere in the middle, either rejecting the lot, this one. So let's do it. So next solo will come here first, we'll come here. So fast we are advancing weight two steps next, next. Now again, slow can come here, and fast can come here are the null. Or you're going to stop here itself. Then the next, next is null, you can stop. Then this flow is at the middle. If it was odd number, then we would not have more Lisman than the middle was. Next up slow or you can have taken this also has the mid. So this way we find the middle. So what time it takes? It takes often if the length of listed him, it takes O of m to find the middle. So this is first step. So after this step, what happens? We make three as the root. And we call the same function on 12. And then recursively call the same function on 45. After n steps. In the next steps, we will have this n by two elements here. Roughly, I'm not writing plus minus one. This will not change the time complexity and then invite beautifully here. So again, this time though finding the root will take In my two times. And similarly here in by two times. So for a balanced binary search tree, this will terminate when we have single nodes itself, then it will reconstitute them. And what is the height of a balanced binary search tree? It's login. So each step we are taking in time. So here, m by two plus n by two. Again m. Similarly here. And by 4 plus n by four plus n plus n by four, again M. And this limit is login. For all n will be n log n. Time complexity here is off. In login space. We are not explicitly using any extra space. We will just modify this list itself. So for example, when we find the middle of the list, so we have this 1, 2, 3. For fame, and it's next is null. So we foundered three as the middle. We made this as the root and its left and right. So rate is fine. The, we'll call this on the next of this three. So it will call on 45. But if you look at this part, if you simply call this recursive function on this head left part, then this next pointer will think that so in the list we have only access to header. Using that we step until we reach the end. So this point is crucial. You have to disconnected you to make it null. Otherwise, it will treat this whole thing as the list and it will go on again and again. So this we will do in the core space we will treat today or one and time as in Logan. And you got the idea how we're doing it. So let's write the code for this in C plus, plus java and Python. And there is one mistake here, so it should be 109 problem. I forgot to change it. So now we will write the code. So this is another example. Again, this is ordered and we get a similar structure. So let's take the base case. If the head itself is null, that is, list is empty, then nothing to return, return null point. Similarly, if the next of head is null, that is, there is just one element. Again, there is nothing to worry. We will return just didn't order of a tree and the structures are different. In a tree. We have left rate in a list we have next. So return new TreeNode. And what does the constructor? It takes a value as the value of the node, which will be value of this head itself. So these are the base cases. Now let's find the middle. For that we will have ListNode flow equal to 100. And fast is equal to Next. And fast. Next. Next. Next is there and fast next next is there. Again, you can do it as per your choice. You can stop when the next is null itself. And you can allow it to go to the null. Also, sadistic may not be required depending on your use case. It's up to you. You will need to modify the code accordingly. So fast becomes. So. Let's write slow first to know when this loop ends. Slow will be aired the middle. Or in this case we are stopping even when next, next is null. So flow, ideally this would be one before middle. Then we have to break this symmetry. Remember this? Otherwise it will treat this whole list as the left part of the list. Then the root node, mid value, and the root left equal to the same function on herd. But we have disconnected it after slope. So from head tilts Lupe loved part. And similarly. And finally we return the R2P. So this is very intuitive. I hope you understand, you know, let's run it. Hopefully there is no area null pointer of L2 norm line 28. If a null pointer. So forced FASD headed next, so head next is null, motif had next is null. So this would be headed next, this case. So if head next season we return this. There is one node keys knowledge straight. Now it seems to be correct. So let's submit. And the solution is, you know, we will do the same thing in Java by three.