{S30} Sep2025 Intro to recursion and Validate BST

Añadido: 2026-05-16

[00:00:07]Hello everybody. Let's start today. Uh today we are going to start with recussion. Uh the first problem that we'll be doing is validate BSV.

[00:00:17]So what's a BSC? Firstly getting into the anybody how do you define a BST?

[00:00:32]got them.

[00:00:40]It's a binary search tree wherein we divide the array into half.

[00:00:46]We um divide the search space into half and every time we >> um iterate we try to reduce the search by half and try to sort it sort out the >> anybody else that's a good start.

[00:01:06]>> What is the BST?

[00:01:10]>> The left side elements are smaller than right side. left the left side elements are smaller than the root. All right, everybody google find out what is BST.

[00:01:25]At this level you should be knowing more about BST or just read the problem. That was enough for knowing about BSC.

[00:01:44]Are you sh What's a BST?

[00:01:51]>> Um, sorry. That's what I'm I'm trying to read towards >> Neil, can you help with BSP?

[00:02:02]>> Yeah. So as far as I could uh I know like all the nodes for every node uh left uh side of the node should be lesser than the uh node itself and the right side of the node.

[00:02:14]>> Yeah.

[00:02:16]>> The node or greater than the root. Yeah.

[00:02:20]>> Okay. And one more important point left this doesn't complete the BST.

[00:02:27]One more thing about BST is what?

[00:02:30]>> No duplicate values. No duplicate values.

[00:02:35]What? One more.

[00:02:36]>> It should be a complete complete binary tree.

[00:02:39]>> It doesn't need to be a complete binary tree.

[00:02:42]>> Google it.

[00:02:43]>> Just just Google it. Complete BST is a complete BST. I've never said that. It's a complete two notes.

[00:02:52]>> Less than less than or equal to boot.

[00:02:56]>> Left and right with uh should also be BST.

[00:03:00]left three and right sub when when we have no duplicates then there this should not be there. Now that if we if we are either should this should not be there or this should not be there. If you're saying equality equality can be there then you are uh you're conflicting with the other statement.

[00:03:18]>> All right. Somebody was somebody was saying that equal to uh if it is equal to then I should not be writing this.

[00:03:23]Okay.

[00:03:25]All right. Left child should be smaller than the root. tight should be smaller greater than the root. I actually wanted to go into the next discussion about the uh about the BST but um surprisingly it's the first path that um students are having doubts about the BST only. All right, left uh baby is lesser than the root. Right? Baby is greater than the root and I have every sub tree is a BST.

[00:04:02]All right.

[00:04:04]So these are the three rules that we have.

[00:04:09]Can somebody tell me the the values of a fourlevel complete PST?

[00:04:15]Can somebody try to give a fourlevel complete BST or just give it a give it a good shot?

[00:04:34]Okay. What is complete BSC?

[00:04:37]What does complete means?

[00:04:41]Each root uh each node has their roots left and right both.

[00:04:46]>> Yeah. Each root each node has left and right maybe.

[00:04:51]All right.

[00:04:53]So four level BST. Anybody? Vishad, do you want to give it a try?

[00:04:58]>> Uh four level BST complete BS. Yeah.

[00:05:10]So we have uh that means we have four levels right the uh I mean like uh I mean 2 to four uh nodes will be there in the last level >> two three >> so >> let's have eight nodes >> this will be here so first there a root and then there are uh two uh uh two uh uh nodes and then the >> give me the root value. They have >> give me the root value that you have to >> one and then you can have uh sorry I mean uh we can uh we can have negative values right >> you need to have negative values if you are starting with one >> yeah uh one then on this side we can have minus one or zero left left of three >> okay >> uh two Okay.

[00:06:15]>> Uh - one. Sorry. No.

[00:06:19]>> Uh - 5. You can say minus 5.

[00:06:24]>> Uh left sub tree of the zero minus 5.

[00:06:28]>> Okay.

[00:06:29]>> Right.

[00:06:31]>> Uh no no it can it cannot be it it has to be more than zero. Right. So I guess root we can say we can take 10 or 100.

[00:06:43]>> Okay. Um anybody else wants to give it a try?

[00:06:48]>> Uh we can start with eight. Root node 8.

[00:06:51]>> Okay.

[00:06:52]And then uh left uh would be four 2 left two and one 3 6 5 7 5 and 7.

[00:07:09]>> Good.

[00:07:10]>> Yeah. Then like 12 left is 10 and uh sorry uh 9 and 11 uh 14 13 and 15 but that's a good try four level complete BSC and if I have to check whether it is a BST 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Perfect it's It's a BSC that we have and it satisfies all the rules that we are talking about or given in the problem that is left baby should be lesser than the root, right baby should be greater than the root and each sub tree should be a BST. How do I determine whether it is a BST or not? Based upon three rules either I can use three rules. Is there any other way that I can check whether it is a BST or not?

[00:08:13]I can check it with the three rules that we have. left is smaller than the the root right is greater than the root and every sub tree is a BST but other than this is there any other way that we can check whether a BST is a BST or not >> we can um print all the nodes and see if it's in sorted order >> we can print all the nodes okay >> we print a code to >> no no not like this uh starting from the left most node from one.

[00:08:46]>> Okay. So in order >> Okay. If we do in order traversal >> in order >> if we do in order traversal in order traversal should be sorted or send it.

[00:09:05]What is in order traversal?

[00:09:12]Left sub tree, root and then right sub tree.

[00:09:15]>> Left root and right is in order traversal.

[00:09:20]Is there any other traversal in trees?

[00:09:24]So in order reversal is not only in BSTs it's on trees. All right.

[00:09:31]>> Pre-order post order >> pre-order.

[00:09:34]>> Okay. What what happens in pre-order traversal?

[00:09:38]>> Root comes first and left right. Loop left right.

[00:09:44]All right.

[00:09:46]Any other post order? Post order left, right, and root.

[00:09:58]It's the position of the root that determines whether a traversal is uh in order traversal, pre-order traversal or post-order traversal. The BST's in order traversal is always going to be sorted or ascending in order.

[00:10:11]This is also in order traversal only right root left.

[00:10:24]This is also pre-ordered traversal that is root right left.

[00:10:32]This is also postordered reversal only where we have right, left and root.

[00:10:41]All right. The position of the root determines whether it is in order traversal, whether it is pre-order traversal, whether it is post order traversal.

[00:10:51]But whenever we are given a in order pre-order, post order traversal by default we will be taking left comes before right. For example, left comes before right. left comes before right.

[00:11:02]Left comes before right over here. Not the other way around that right is coming before left. Okay.

[00:11:10]The in order traversal of a BST is sorted in nature. And that's what I did when I was looking at this. I was doing 1 2 1 2 3 4 5 6 7 then 8 left n root then right sub tree in the right left left 9 root 10 right 11 Left done root 12 then right sub tree in right left one 13 14 is the root and 15 is the right all right so in in order traversal left then root then right that is the order that we are going to do now we will go to the validating the BST for example one of the ways is that I can do the in tra reversal and I can check all these I can put all these elements in a list and I I can check whether it is ascending in nature or not but let's put the validating the BST on the back burner for now let's focus on recussion the nitty-g gritties the under the hood things of recussion each and everything about recussion we are we are going to learn we write a recursive function on this tree.

[00:12:51]Let's call that function a helper private helper and we have three node root over here.

[00:13:10]Generally the in order traversal is written like this that is helper root dot leftft.

[00:13:24]Let's put system print.

[00:13:30]It's actually system.out.print.

[00:13:33]Let's call it app and system dot print root dot value and then helper off root.

[00:14:13]And if root is equal to null, delta Let's call it one. Let's call it line two. Line three.

[00:14:47]Line four.

[00:14:52]Can somebody tell me what is this code written for?

[00:14:59]This is a very famous algorithm in BST in order traversal.

[00:15:05]>> In order traversal we are doing in traversal left then root processing of the root then the right. All right. So this is in order traversal but what we are going to do is we are going to do couple of more things. Print down.

[00:15:23]print root and we have a stack recursive stack and we will be understanding the rules of recussion and we will not be leaving any blind spot.

[00:15:46]Let's call it line five and we have to print the values over here.

[00:15:53]So what will be printed first? All right. Firstly, when we start our recussion from here, what will be going inside the recursive stack?

[00:16:03]What will be there inside the recursive stack?

[00:16:08]Function >> function calls >> or function calls. Okay. Yeah, it will be function call. But what will be the root at that time?

[00:16:20]Four.

[00:16:27]All right. Anybody else?

[00:16:32]Eight. Anybody else?

[00:16:41]The first first uh frame will be will start right eight and then uh >> that calls four and then >> functional call on eight >> and that >> if there will be function >> just just a moment if there is a functional call on four where is the functional call of eight remains?

[00:17:12]that will be in the that will be still in this uh >> not you I'm talking to the students who are saying that okay functional call of four will be the first recursive call that I will be adding it means what where is this functional call of a the initial function call of it >> isn't the very first uh at at the beginning at the beginning of the function Isn't the root value as eight?

[00:17:39]So in line two when we put in root. Four goes in.

[00:17:45]>> Okay. If four goes inside the stack, where is functional call of eight in the universe?

[00:17:51]>> It's still in the memory in the stack like in the main uh after the main functions stack frame it will be function 8's stack frame and on top of that will be uh function four the stack frame of function four. So, so the function first functional call inside our call stack which is going to act as a recursive stack over here is functional call of eight.

[00:18:16]All right. So when we come okay anybody who can tell me what will be the order of prints over here. What will be the output of this function >> in order 1 2 3 4 5 6 7 8 9 10.

[00:18:32]>> Look at the print statements.

[00:18:34]Oh, there we uh up one and up two, up three, up four. Up in order.

[00:18:55]Mhm. Anybody else?

[00:19:11]All right, let's try to do it uh one by one together. Uh give full focus. Okay, so function call of eight will be the first function call. We'll go to line number one. Is my root equal to null? We are at eight. 8 is the root.

[00:19:26]All right. Then helper of root.

[00:19:30]Recussion goes over here. Helper call off that is function call on left is called four.

[00:19:39]All right. We have returned from here only we have gone to helper call.

[00:19:45]The earlier one still remains that is there inside the stack.

[00:19:49]Then we come to line number one again.

[00:19:52]Is my root equal to null? Is this equal to null? No, it is not equal to null. In that scenario, we go to line number two.

[00:19:59]That is roots left for left is two.

[00:20:03]There is a functional call at two now which hits the function right here. Line number one. Is my root equal to null?

[00:20:12]No, my root is not equal to null.

[00:20:16]We go to line number two. Helper caller two's left that is one is what is happening.

[00:20:24]All right. Helper of one. Root is equal to one. Is my root equal to null? No.

[00:20:30]Root is not equal to null.

[00:20:33]We go over here. Helper on root.

[00:20:36]Functional caller. Null happened.

[00:20:48]We go over here. Helper on null. Is my root equal to null? Yes, my root is equal to null.

[00:20:59]All right. When root is equal to null from here return happens. Return happens where? From where it was caught.

[00:21:10]Possible rule of recussion.

[00:21:13]Return happens to the same place where it was not.

[00:21:26]It's not about the place but whatever functional call has happened from if the functional call has happened from here it will return to the same functional call without exception without any second guesses.

[00:21:43]All right. So I'm going to write over here just for your understanding that all these functional call have happened from line number two till now. Okay, they were left recursive calls.

[00:21:58]So when return happens, it returns to the same place from where it was thought. It comes right here.

[00:22:06]Now this functional call is complete.

[00:22:10]Whenever a functional call is complete, what happens to the call stack?

[00:22:17]>> It pops.

[00:22:18]>> It pops. It pops. it has popped. That's why I'm putting a placeholder over here that it pops. When it is complete function called pops.

[00:22:33]Now when we are at line number three, first thing that will be printed is all right, let me write the rules of the recussion for now. It returns to the same same place from where it was called.

[00:22:45]P happens and one is to one mapping with parameter.

[00:23:00]Now it's not a rule of recussion. This is just for understanding that the other functional call is out. Now at top of the stack I have the functional call as one.

[00:23:11]What is the root of functional call of one? Where is the root now?

[00:23:17]At one.

[00:23:19]This is my current root.

[00:23:25]So we call it one is to1 mapping just for understanding. But it is essentially what is the function call at the top of the stack and the root over there was one. Whatever has gone inside the stack will be the same thing that will be coming out of the stack.

[00:23:43]So root is equal to 1. Now system.out.print up will be printed.

[00:23:55]Up one will be printed.

[00:23:58]Up one will be printed.

[00:24:02]Once we have printed that in line number three, then what happens?

[00:24:10]>> We go again. It goes to the right side of one.

[00:24:13]>> Yeah. We go to line number four and it goes to the right side of one. That is helper call of functional column null happens.

[00:24:26]And it was called from which line? Line number four.

[00:24:31]Helper of null happens. We hit helper of null. Is my root equal to null? Yes, my root is equal to null. Return happens.

[00:24:45]This is for the current function call that return has happened. Doesn't mean the whole recursive call will be complete.

[00:24:55]Recussion will not stop till all these function calls are there inside the recursive stack.

[00:25:01]Till that time recussion will not stop.

[00:25:08]Now function call null is equal to null return happens returns returns to this to which place from where it was stored line number four it returns to this place what happens now >> down one is printed >> down one >> all right stackpop again because this function call is complete so stackpop happens what is the root Now again one function column one.

[00:25:53]All right. Root is equal to what that is down one printed.

[00:26:04]>> Now we are going down over here. There is nothing. The function has finished over here or you can think of it as a return statement.

[00:26:19]Left of one is done, right of one is done. Left recursive call is done. Right recursive call is done.

[00:26:27]Functional call on one is complete.

[00:26:31]Means return happen.

[00:26:33]Return with return to which place?

[00:26:39]>> Route two?

[00:26:42]>> Return to the previous call.

[00:26:44]>> Tell me the line where where the where the >> line two.

[00:26:48]>> Line two.

[00:26:49]>> It was called from line two. It will return to line two.

[00:26:53]All right. It returns to line two.

[00:26:56]Stack. Has happened.

[00:27:02]At the top of the stack I have function call two. So my root is two now.

[00:27:08]We are right here.

[00:27:10]What will be printed now?

[00:27:14]Up two.

[00:27:20]We print in line number three up two and then write recursive column two happen that is we go to three that is functional column three has happened from which line it has happened four >> line number this I am maintaining for your understanding. Okay. So when the function call is out you know that at which line I have to return the control.

[00:27:51]This doesn't go inside the recursive stack. Only these go all right up to then function call on three happens from line number four.

[00:28:03]Functional call on three happens. Line number four. Function control comes over here.

[00:28:08]Is my root equal to null? No it is not equal to null. We come to line number two. Functional caller roots left that is functional caller null happens and it happened from line number two helper of null. We go over here is my root equal to null.

[00:28:32]Yes, it is equal to n. Return happens.

[00:28:36]Return returns to the same place from where it was found. Line number two. It comes right here. Pop has happened.

[00:28:44]Because this function call is complete.

[00:28:46]It will be going out of the call stack.

[00:28:48]What will be printed now?

[00:28:53]>> Up three.

[00:28:54]>> Up three.

[00:28:55]>> Up three.

[00:28:57]We come to line number four.

[00:29:02]Three is right. Call is done. That is three is right is null. Helper of null is done. Is my root equal to null?

[00:29:10]Function caller null is done from line number four. Remember function caller null. We come over here.

[00:29:18]What is equal equal to null? Return.

[00:29:19]Return return happens to the same place from where it was.

[00:29:23]Line number four. Tag. Happens. This is out.

[00:29:30]What will be printed now?

[00:29:33]Down three. Down three. Down three. Why?

[00:29:36]Because this is a root now.

[00:29:40]return happens. Now that is in English left recursive call of three is done.

[00:29:46]Right recursive call of three is done.

[00:29:47]Functional call of three is done.

[00:29:55]When functional call of three is done, it means the return happens. Return happens to the which play?

[00:30:01]>> Two.

[00:30:03]>> Uh four.

[00:30:04]>> Line number four.

[00:30:06]>> Four.

[00:30:07]It was called from line number four. It will return to line number four only.

[00:30:12]All right. So it returns to line number four. Stack.pop has happened. This function call is complete. Stack.pop has happened. What will be printed now?

[00:30:22]>> Down one.

[00:30:22]>> Down two.

[00:30:24]>> Down two.

[00:30:25]>> Down two.

[00:30:30]>> All right. Down two will be printed.

[00:30:33]And we hit the return statement again.

[00:30:36]That is function call on two is done.

[00:30:38]That is left recursive call is of two is done. Right recursive call of two is done. Currently here is the control of the recussion. Left recursive call is done. Right cursive call is done. We hit the return statement.

[00:30:50]Now where where is the control of recussion will go?

[00:30:58]>> The previous tell me the previous. Tell me the line over here in the code please. uh line number two.

[00:31:06]>> Line number two, it return it returns to the same place from where it was called.

[00:31:10]It was called from line number two. The the control of the recussion will be going to line number two. Start out pop has happened. It means this function call is complete.

[00:31:26]This function call is complete.

[00:31:30]All right. What will be printed now?

[00:31:36]Up what?

[00:31:37]Up four. Four. Four.

[00:31:41]The root is four. Here is the control of the recussion. Now then root.right function caller six is done. And that is now called from line number four.

[00:32:07]Helper of six. Helper of six. Is my root equal to null? Is my six equal to null?

[00:32:13]No, it is not equal to null. Helper of root dot left. That is functional column five is null.

[00:32:20]From line number two.

[00:32:24]All right. Function column five. Is my five equal to null? No, it is not equal to null. The control comes over here.

[00:32:31]The code comes over here. Helper of root dot root dot left that is five left is null called from line number two that is helper of null. Is my root equal to null? Yes. Return returns to the same place from array was called.

[00:32:56]Line number two. This function call is complete.

[00:33:00]What will be printed now?

[00:33:03]Up five will be printed. The code comes over here. Root. That is call on five right functional call on null part from line number four.

[00:33:22]Helper of null. The code comes over here. Is my root equal to null? Yes.

[00:33:27]return return happens to the same place from where it was called.

[00:33:31]Line number four, it returns over here stack.pop. This function call is complete.

[00:33:37]What will be printed now?

[00:33:41]Down five. That is my current route.

[00:33:49]All right.

[00:33:52]And now we hit the return or the function has completed.

[00:33:59]When we hit the return over here, we return to the same place from where the function caller five is complete. Five has called. Remember five happened. Left of five, right of five. Left of five is done. Right of five is done. Function call of five is complete. We return to the same place from where it was called.

[00:34:16]It was called from line number two. We return right to line number two. This will be out.

[00:34:23]Somebody's not not mute. Kindly mute yourself.

[00:34:26]We return to the same place. Start. Has happened. What will be printed? Up six.

[00:34:39]Up six gets printed.

[00:34:42]Then root dot. Current root is six. Six.

[00:34:46]Right.

[00:34:47]That is it goes right here.

[00:34:51]For the sake of time, I am deleting some of the nodes. Okay, let's take nine over here. But 11 I can delete. Okay, so I'm going to seven.

[00:35:07]Function call on 7 called from line number four.

[00:35:15]Function column 7. Is my seven equal to null? Nope. Helper of root. Happens.

[00:35:23]Function call null happens. It has happened from which line? Line number two.

[00:35:30]Helper of null. Root is equal to null.

[00:35:32]Return return happens to the same place from where it was? Line number two.

[00:35:35]Stack. Pop has happened. This is how.

[00:35:38]Now at top of my stack function call of seven that is root is equal to 7. What will be printed? Up seven.

[00:35:59]Now seventh right function call of null has happened from line number four.

[00:36:10]Function call of helper of null. Is my root equal to null? Yes. return returns to the same place from where it was called stack.puff Top of top of the stack I have seven that is my root. Now seven will be printed.

[00:36:29]Return happens. It means the function call of left is done right is done for seven. This function call is complete.

[00:36:35]Return happens. Return happens to the same place from where it was called.

[00:36:38]Line number four. This pops out.

[00:36:50]Six will be printed.

[00:36:58]All right. Down six gets printed.

[00:37:01]Return.

[00:37:02]Return return. It happens to the same place from where it was called. Line number four.

[00:37:08]This is the current control function column six is done. Complete return happens. Return happens to the same place from where it was called. We have already noted down so that we don't get confused. It comes to the line number four down four gets printed and the control of the recussion is the four. Right here the left recursive call and the right recursive call of four is done the function call of four is complete in English.

[00:37:47]If you want to see the code level control now four is printed.

[00:37:54]This is complete. Return happens. Return happens to the same place from where it was called. Line number two.

[00:38:02]Stack drop of apples.

[00:38:07]What gets printed?

[00:38:11]>> Okay.

[00:38:18]And here is the control of the recussion. Right now up 8 minutes code comes over here. Root.

[00:38:26]function columns 12 is done and that is called from line number four I'm going to delete this option then root dot left function call of tell is done from line number four sorry function call of 12 is 12 equal to null no code comes over here root dot left 12's left function Fun caller 10 has happened from line number two.

[00:39:04]Function call of 10. Is my 10 equal to null? Nope. Left recursive call happens.

[00:39:11]Function call of null happens. Has happened from line number two.

[00:39:16]Function call of null. Is my root equal to null? Yes. Return happens. It happens. Takes us to the same place from where it was caught. It was called from line number two. will return to Nile number two. This is all start path happen. This function call is complete.

[00:39:32]Control of the recussion is right here.

[00:39:36]Up 10 gets printed.

[00:39:41]Up 10 gets printed.

[00:39:47]Then we come over here roots right function call of null has happened.

[00:39:58]from line number four helper of null. Is my root equal to null? Yes, root is equal to null. The return happens. Return happens to the same place from where it was called.

[00:40:08]Line number four.

[00:40:11]This is out. Stack. Has happened because this function call is complete. Return has down 10 prints.

[00:40:24]down 10 prints. Return happens. Return happens to the same place from where it was for. Line number two comes over here.

[00:40:33]This is complete.

[00:40:36]St. up.

[00:40:44]Well, get printed.

[00:40:53]up 12 gets printed root dot write function column 12's right that is 14 has happened from line number four helper of 14 is my root equal to null is my 14 equal to null no it is not equal to null we come right here helper of root dot left that is function call of null has happened from Line number two is my helper of null. Is my root equal to null? Yes, return happens.

[00:41:27]We do hit the return statement. Return happens to the same place from where it was called. Line number two.

[00:41:34]Track down pop has happened and up 14 gets printed.

[00:41:43]We come over here.

[00:41:45]Function call of null has happened.

[00:41:51]From line number four helper of null is my root equal to null.

[00:41:57]Yes, it returns to the same place from where it was called. L number four stack. Pop has happened down 14 gets printed.

[00:42:11]The control of the recussion is right here.

[00:42:14]Down 14 gets printed. Return happens.

[00:42:18]Return happens to the same place from where it was. Line number four.

[00:42:23]Track pop has happened.

[00:42:26]Down 12 get three.

[00:42:31]Return happens. The return happens to the same place from where it was called.

[00:42:35]Line number four. This has popped out.

[00:42:42]And now down close recussion is right here.

[00:42:48]Down 8 root is right here.

[00:42:52]Down 8 gets printed.

[00:42:57]Return happens.

[00:43:00]Return happens to the same place from where it was called. It was called from line number two. The call stack is empty. All the function call is complete.

[00:43:10]This is the print statements that we will print.

[00:43:16]Recussion returns to the same place from where it was called. One is to one mapping of the parameter happens. And recussion doesn't stop till the time the call stack is not empty.

[00:43:26]And this was the flow of the recussion till now. Anybody any questions till now?

[00:43:34]All right. If you were observing it carefully, can you tell me what was the maximum number of calls inside the call stack or the recussion stack right here?

[00:43:44]What were the maximum number of calls inside the recussion call stack over here?

[00:43:49]>> Five at any point.

[00:43:51]>> Five.

[00:43:52]>> Five.

[00:43:53]>> All right. Five. So can you tell me in terms of this trees parameters or trees input variables what is five over here for example for this >> yeah height of the tree of h so number of maximum calls inside the recursive stack at any point was h that is we had five one was fun that's why height of the tree is the maximum space inside the recussion stack that we took.

[00:44:32]All right. Before moving forward, let's validate whether our understanding of flow of recussion is complete is completely correct or not.

[00:44:45]Uh in this case, isn't the height of tree?

[00:44:49]cuz uh we are going left >> 1 2 3 >> 4 2 3. So >> 1 2 3 4 depends what how we are defining the height.

[00:45:07]You want to define height as height minus one you can um do that also. So if the interviewer says that okay the depth of the tree over here just if you separate question if they say tell me what is the height of this tree >> three or um somebody can say four it's a fourle bs >> all right it's the way that you you are defining your Thanks.

[00:45:59]Let's order a list.

[00:46:03]Now I'm not going to use this array list. I'm going to return a wrong answer over here for the in order reversal.

[00:46:10]Don't worry about that.

[00:46:13]But let's make the tree over here. And if you see how I am defining the tree over here or how I'm I'm writing the tree over here then this is the way that you can do on lead code or this is the way that you know going forward you'll be learning about uh a concept of serialization and deserialization but for now just observe how we are defining the tree eight on the left of eight we have four on the right of eight we have 12.

[00:46:47]Now the next node is four. On the left of four we have two.

[00:46:52]On the right of four we have six.

[00:46:56]On the left of 12 we have 10.

[00:47:00]On the right of 12 we have 14.

[00:47:04]On the left of two. Now we have one. On the right of two we have three.

[00:47:14]And it will keep showing you the tree that you have built till now. On the right of six, on the left of six, we have five. On the right of six, we have seven.

[00:47:27]And that's it.

[00:47:29]All right. This is the tree that we have. Let's write helper root.

[00:47:40]or function call.

[00:47:46]Just replace our helper on the whiteboard with this in order traversal and system.out.t print up system.out out. Print row dot value and in order traversal or root dot write and below that print down statements and for your sake of understanding stat.puff pop over here the way that we have written on the whiteboard and start right so you should not be giving us the because here they want the in order reversal we are just using this problem for printing statements all right for understanding the flow of recussion okay I forgot to do Let me do one thing.

[00:49:10]Private void helper call on preload node root so that it matches with the whiteboard option and I'll take these If the root is equal equal to null helper helper and we'll do the initial helper call root just to print the flow of recussion.

[00:50:02]All right, it gives us a result is empty. But let's look at the print statements. Print lite.

[00:50:20]Let's try it.

[00:50:33]All right. Let's try it with the whiteboard to see if the if our understanding of flow of recussion regressive stack is correct. Up one, down one. Good. Up two. Good. Up three.

[00:50:46]Same thing. Down three.

[00:50:50]Perfect. Down two. Perfect.

[00:50:53]Up four. Perfect. Up five. Perfect.

[00:51:00]Down five. Perfect. Up six. Perfect. Up seven. Perfect.

[00:51:07]Down seven. Perfect.

[00:51:11]Down six.

[00:51:13]Perfect.

[00:51:14]Down four.

[00:51:16]Perfect. Up. Eight. Perfect.

[00:51:20]Up 10, perfect. Down 10, perfect.

[00:51:24]Up 12.

[00:51:26]That is there on the whiteboard also. Up 14. Correct. Down 14. Correct.

[00:51:33]Down 12. Correct. Down 8. Correct.

[00:51:38]That is the flow of the recussion that we have. All right.

[00:51:43]Without understanding the flow of recussion, we will not be able to do normal recussion.

[00:51:52]We will not be able to do the backtracking. We will not be able to do TFS. All right. So, understanding flow of the recussion. This is one of the most important lectures in the whole cohort. Understanding the flow of the recussion. Lot of students think that okay, at the code level, we'll be able to understand the recussion. They uh they are in for surprises later on. All right. Always if I remove this then this becomes an inorder traversal left processing of root right and if I print surprise surprise everything will be in a sorted manner 1 2 3 4 5 6 7 8 9 9 is not there 10 12 14 and remember why because our tree was the tree that we had built over here or on the whiteboard is a BST.

[00:52:46]So this is nothing but if I remove this this is nothing but the in order reversal.

[00:52:53]Quick question if I remove this and I print this what will be what will be your comments post.

[00:53:03]>> It is a post order reversal. So if I print this this is nothing but the post order reversal that we have. All right.

[00:53:10]In which left right root left right three roo<unk>2.

[00:53:20]This is nothing but the post order traversal.

[00:53:24]Make sense? So kindly understand the flow of the regression. It is very very important. Anybody any questions till now?

[00:53:38]Add value this result just completing the in order to problem over here. Okay, this result is error. If I run this, this should be working fine. This if I submit it, this should be working fine.

[00:54:07]This Huh?

[00:54:10]This is the in order traversal. In order traversal is the one that we used for understanding the flow of the regression.

[00:54:19]But let's come back to the parent problem of validating the BST. Right?

[00:54:24]One of the ways that I can validate the BST is that I just take this from here. Whatever we did over here, we put in inside the result.

[00:54:38]I create a resultant list over here. Just the way that I created over here pirate.

[00:55:05]Video helper of tree node root system.out print the result over here.

[00:55:25]All right. So if I do this in the helper call I can take it from here.

[00:55:31]Remember this is the in order traversal. Now that we have basically in order traversal and we print the result it will be in a ascending order right for any of the trees for this tree that is 5 1 4 3 6 1 left root then 1 5 3 4 6 which is not in a sorted manner so it's not a BST but if we take this tree over Here this is a BST. It will be printed in a sorted manner.

[00:56:29]It'll be sort printed in a sorted manner and that's what should have happened.

[00:56:34]But we are using an extra result list over here and that result will be containing all the element out of BST.

[00:56:42]We are using extra space even though that extra space is not required. So how do we do it without using a resultant list? How do we do it without storing all the elements inside the result and still do the inord reversal only to validate whether it is a BST or not?

[00:57:02]Anybody any suggestions?

[00:57:14]>> We we check uh if uh the root value uh is greater than the left uh and the right and then we recursively call is valid BST.

[00:57:28]>> So um means in order traversal will not work.

[00:57:35]So you're suggesting a new algorithm over here, right?

[00:57:38]>> No. Uh so you can do that in in order like we check uh if left is smaller than the uh root.

[00:57:45]>> Okay.

[00:57:45]>> And is uh BST on the left.

[00:57:54]>> What is in order reversal? In that we print the left and then the root then the right. So we we go on uh to the leftmost node.

[00:58:02]>> Okay. Let let me modify my question. Uh can I do the in order traversal without using the list without storing the elements inside the list?

[00:58:13]>> Can we uh do in order traversal without storing in the list?

[00:58:17]>> Yeah, >> we want to print everything, right?

[00:58:28]Do I need to print?

[00:58:31]>> So, uh, just you want is valid BST, right? Uh, or >> do I need to print or do I need to store all these elements in a list?

[00:58:45]>> Is there any way?

[00:58:47]>> Huh?

[00:58:49]When I'm saying that can we do something, it means we can Yeah, man. What were you saying? Go ahead. Go ahead. I might >> Yeah.

[00:59:03]>> So, uh uh for uh is valid BST uh can we do this without storing it in a list?

[00:59:11]Right.

[00:59:12]>> Yeah. Can we do it without storing it in list? Without storing without storing the in order traversal in a list?

[00:59:18]>> Yes. uh like what I'm suggesting is uh like we compare the root >> with the left value and the right value of the root.

[00:59:26]>> We process the root.

[00:59:29]>> Okay. Then >> and then we call on the uh left should be also a valid BST and right should also right should also be a valid BST.

[00:59:39]>> Root. We call a function call on root.

[00:59:42]And then we call a function call on root.right. Correct.

[00:59:46]>> Yes. Yeah. Is this in order traversal then?

[00:59:50]>> Uh no uh it's pre pre-order traversal.

[00:59:53]>> So we can do it with pre-order traversal. What you want to say over here is uh that with in order what I'm asking over here with in in order it is not possible because we were on a discussion of in order reverse right we can store the elements in a resultant list. So should we come to a conclusion that if we are doing in order traversal we will have to store the elements inside the list only neither we'll have to abandon in order traversal and we'll have to go to pre-order traversal is will that be a correct statement if I make make that >> yeah so far I'm not able to find a use case where we can do it within order so >> okay anybody Anybody else?

[01:00:46]>> Okay. If I have the in order over here, if I have the in order to vessel and I'm storing it in a list, then it is 1 2 3 5 4 5 6 7 8 10 12 14. Correct? If I do an end order traversal, I store the elements in a list like this. How do I check whether this list is ascending in nature or not?

[01:01:13]Whether this list is sorted how do I check that?

[01:01:19]>> I just iterate through it.

[01:01:21]>> Just iterate through it and iterate through it. What? Like I'll go over here. Now what? Then I'll go check >> at two. What should I do?

[01:01:29]>> No.

[01:01:31]>> Check its next element. If uh if it if it is greater than just one if it is not then >> lift if it's next element three should be greater than one >> greater than two like greater than one unit >> yeah I missed the part that we we I missed the part that we might have missing numbers I missed that part >> forget about that I am giving you a list a simple list this The list universal tell me whether it is sorted or not. How would you check it?

[01:02:09]>> The first and the last most element. The first >> the first first and the last last most element. If first one is smaller, last one is greater than the whole list is sorted.

[01:02:19]>> We have to check the next element is less than the previous element then it's not sorted.

[01:02:24]>> Yeah. Let's have current element and the previous element. If two is greater than one then we move forward.

[01:02:35]If the current element is greater than the previous one just that thing it's there is no rocket science over here. You want to check whether the whole list is sorted or not in a brute force manner. If you want to check whether the whole list is sorted or not, just take three is greater than 2, 4 is greater than 3, 5 is greater than 4, 6 is greater than 5, 7 is greater than 6, 8 is greater than 7.

[01:02:59]This is the way that we can check now or I can say I can have two pointers and this middle pointer over here, if this is current pointer and this one is previous pointer, current is greater than previous. Then move both the pointers.

[01:03:16]Check four is greater than three. Move both the pointers.

[01:03:21]Five is greater than four. Move both the pointers.

[01:03:24]Six is greater than five. This is a way that we can check whether the complete list is sorted or not.

[01:03:32]One current pointer, one previous pointer. Now why do I need to store all these elements inside the list? I can just move the pointers on the list on the BST on the tree itself. Huh? I have the root which is the my current and one previous pointer to it. That is what what is the previous element.

[01:03:50]Why do I need to store all the elements over here?

[01:03:54]I just run two pointers on the whole tree only. The tree is giving me this list now.

[01:04:01]So if I am able to mim that before one there is nothing. When we are at two just compare it with the previous element.

[01:04:08]I'm saying previous I'm not saying left.

[01:04:12]Don't start making assumptions. I'm just trying to mine. But I will do it on list. If I had stored all the elements in the list, how would I check whether the list is sorted or not?

[01:04:24]Just keep checking two elements.

[01:04:26]2 is greater than three. 2 is greater than one. 3 is greater than two. Four is greater than three. So for I don't need to store all these elements inside the list. I can these these elements are coming from BST only.

[01:04:40]I can do the previous and the current on the PSC itself.

[01:04:47]So initially remember this will be printed. This was a print of the in order traversal.

[01:04:56]At that time I can have a previous at the null and current at initial root which will be printed or which will be processed was one at that time. I don't need to check one with the previous because there is no previous to the one.

[01:05:19]I don't need to check whether it is greater than there is no previous yet.

[01:05:24]But once one is done, I'll move the previous pointer to the current position and current goes to the next position.

[01:05:33]What was the next position in the in reversal? What was the next route which was printed? It was two current when two comes out of the stack or two is get about to be printed at that time and just check it with the previous If everything is fine that is two is greater than one then I'll move the previous to the current position and what was the next note which was which was printed in in order traversal was three my root will be here my current will be coming right here I check the current with the previous is three greater than two it is greater than I'll move the previous to the current position and current will be then at four.

[01:06:34]Just check four is greater than three.

[01:06:36]Yes, it is greater than three.

[01:06:41]Then move the previous to the current position.

[01:06:45]Next position of current is what? Five.

[01:06:53]Just check current with the previous. Is five greater than four? When it is fine.

[01:06:58]Move the previous to the current location.

[01:07:01]Current to next location.

[01:07:09]If at any point during the tree there is a breach, we'll say that we have found a breach.

[01:07:16]It's not a valid BSD.

[01:07:19]we can store it in a flag.

[01:07:25]All right. So let's try to do it without storing inside the list.

[01:07:30]We can this list was coming from the tree only now. And how do we check this is current? This is previous.

[01:07:40]Current sorry previous current. Exactly.

[01:07:44]This is the movement that I am miming on the tree. Move the previous to the current location. Current to next location. Move the previous to current location. Current to next location. Keep checking whether they are breaching or not. Move the previous to current location. Current to next location. Move the previous to current location.

[01:08:00]Current to next location. All right.

[01:08:03]This is what we will be mining.

[01:08:06]If I try to run this, if I try to write code over here, I just need a previous pointer to validate a BST. I don't need to store it in a result.

[01:08:21]So let's have a private tree node previous.

[01:08:44]All right. add a boolean flag and I'll do a helper call or you can call it in order to call in order.

[01:09:02]What kind of call I should be doing?

[01:09:05]Will it be a boolean based recussion?

[01:09:07]Will it be a void based recussion?

[01:09:13]>> Boolean. boolean based recussion.

[01:09:18]Let's do that. Private void in order reversal on tree node rule.

[01:09:29]All right. Base case logic in the logic in the in order traversal what do we do? Left in order of root do.

[01:09:50]in order of fruit.

[01:09:55]And we have to process the root in between. Now process root here.

[01:10:00]How do we process the root?

[01:10:02]If my root dot value which is current also root dot value is greater >> lesser than lesser than or equal to previous dot value in English it means what the root is smaller than the left child.

[01:10:31]So I just said that okay current previous current previous there is no left there's no right is this is seven over here and six over here is six the left child of seven.

[01:10:49]This is in order reversal. You are still stuck onto one of an algorithms which is which we are not even doing which we are even not attempting. We are just reversing over this list and we are checking whether the current is greater than the previous or not. If current is not greater than the previous. If rather than seven if we have two over here then what?

[01:11:15]>> Return false.

[01:11:16]>> Return false. This is not a valid BST.

[01:11:19]That is what we are trying over here.

[01:11:24]If my root dot value is lesser than or equal to previous dot value, root is current. If current value is lesser than or equal to previous dot value.

[01:11:34]All right. At that scenario, we have a breach of BST.

[01:11:42]All right.

[01:11:46]And we'll make the flag equal to pause.

[01:11:50]I cannot compare the initial one. If previous is equal equal to null means we are right here current was equal to one previous was null then previous came over here current went over here. All right. So one should not be compared to anything because there is no previous value to it.

[01:12:15]And remember by default the previous is getting initiated over here in the global with null.

[01:12:28]>> Previous is not equal to previous is not equal to it. flag zero to false and the base case if my root is equal to equal to if at any place we have a breach the flag will become false I'll make the initial flag as true if at any place it is has breached the valid it's not a valid BST we'll be catching it with flag is equal to false and root return true not true return the flag if I try to run this code now let's see what I'm saying that I'm doing need to change the previous value >> yeah we need to change the previous value my bad previous to current position move the previous to the current position before doing the right recursive call once we have compared remember this is what we have to mine current previous once we have done the comparison move the previous to the current position this is what is pointing out and he's absolutely correct then move the current to the next position a current in this scenario I don't need a current separate current uh pointer because root is my current root is my current node that we are working with all right if I run this this this should be working fine oh current routter working fine. If I submit it, this should be perfectly accepted.

[01:14:15]>> Here like we are making the flag as false, right? So the recussion will still keep on going. I mean it won't stop at the fall. We >> we'll we'll come to that. That's a good question. Good great question. All right. Anybody any questions till now?

[01:14:38]I want to bring the first this as the first test case.

[01:14:48]Okay.

[01:14:51]And the second test case is 1 2 3.

[01:14:56]All right. What Bulkit is asking is a great question. If I do system dot out dot print root dot value over here apparently we are processing each and every node. So in the pre-order manner all the roots will be printed and they will be printed in pre-order manner. Right?

[01:15:21]If I'm printing it right here they will be printed in the in order manner. This is pre before the left now. So all the nodes will be printed 8 4 2 1 3 6 5 7 whatever is there on the whiteboard everything is printed all right or let me print it over here in order so that it is in sorted manner okay 1 2 3 4 5 6 7 8 All right so I'm printing it over so that there is no confusion. Okay. So all the nodes will be printed.

[01:16:04]Imagine imagine if we have a breach over here rather than one if we have seven over here. Uh like 100 over here rather than one if we have 100 over here or 10 over here.

[01:16:27]And rather than 10 we have in. Okay.

[01:16:32]Is this a BST now?

[01:16:37]Anybody?

[01:16:39]It's not a BST. So we should be getting a breach and correctly we are getting a breach.

[01:16:48]Where is the breach happening over here?

[01:16:52]10 is uh like >> greater than >> 10 is greater than two or two is smaller than 10 now. So it will be getting caught over here when the root value will be equal to two and the previous value is equal to 10. At that time we'll catch it that there is a breach.

[01:17:08]So the breach has happened over here.

[01:17:10]But if I print the elements over here what pulkit is saying all the nodes will still be printed.

[01:17:20]Recussion will go to all the nodes and not surprisingly why because whatever has gone inside the recursive stack has to be completed. Function call on 8. First function call was function colon 8. In the recursive stack we had at the bottom function colon 8 then function column four then function column two then function column 10. So and so forth.

[01:17:50]The breach has happened at this place still. Why are we recursing on 10 and 14ths and 12ths? 11 now. Okay. Why are we going to 11th and the 14th and 12th?

[01:18:04]And why are we checking the fives and the seventh?

[01:18:08]If the breach has happened here only, why do I need to go to the sixth and the fives and the seventh and the 11th and the 12th and the 14th?

[01:18:17]Can we do something that we can save some of the recursive call? Save some of the recursive.

[01:18:26]How do I modify?

[01:18:29]>> Check the flag in the first condition.

[01:18:32]>> Check the flag in the first condition that is line 26 right here. If the flag is equal equal to false, then what?

[01:18:42]return for uh like do nothing just return >> just return all it now this what we have done till now is the dump brute force recussion it's non conditional recussion over here as soon as I bring that check if the flag is false already or not then that is conditional recussion if the flag is false now you don't need to further recuss is what Imran is saying in English.

[01:19:16]I don't need to do the further recursive calls if my flag is equal to false or I can do it like this.

[01:19:27]Flag is equal to true then only do the right recursive call.

[01:19:37]Then only do the right recursive call.

[01:19:41]Or I can write write it like this. If the flag is true then only conditional recussion. Now if the flag is true then only do the left recursive call. If the flag is then only do the right recursive call. If I do and run it now then I will be able to save surely able to save some of the nodes. All right. Now which are printed is 8 4 2 and 10 only. That's it. 8 4 2 and 10.

[01:20:13]Earlier one was non conditional recussion. This is conditional recussion that if the flag is true then only go towards left. If the flag is true then only go towards right. If the flag is already false why should I go towards the right?

[01:20:29]I don't need logically.

[01:20:32]And this is the same as what Immran was suggesting that if my I can put this condition in the base case of or flag is equal to if the flag is equal to false already return don't go further don't do the further recursive calls no need to do the check for the checks if breach has happened I don't need to go to the further nodes if I do that I'll be printing same.

[01:21:05]Now I have moved that condition inside the base case.

[01:21:10]This is called conditional recussion.

[01:21:13]We will be doing it at many places where we will be doing non-conditional recussion then we'll be doing the conditional recussion.

[01:21:23]Is there any other way than checking the flag?

[01:21:29]Can I do this?

[01:21:36]The inter says oh it's working perfectly working code what if I put put the return statement over here how many nodes will be printed over here remember in the earlier case 8 4 2 and 10 were printed now the breach is still happening at 10 only and I put the return statement over here if flag is going to pause false If I put the return statement over here, what will happen?

[01:22:10]Just take a while guys.

[01:22:14]Although you should not be taking guess because it is bas based upon the recussion rules that we had learned.

[01:22:20]>> After 10 nothing gets printed like till 10.

[01:22:23]>> Till then 10 only 8 for 210.

[01:22:26]And why why do you think so?

[01:22:35]>> Not going to the right tree. After 10 >> not be going to the right tree. Anybody else?

[01:22:44]How many nodes will be printed over here?

[01:22:48]>> Only three.

[01:22:51]>> Only three. Three nodes. 842.

[01:22:53]>> 842. Yeah. Okay. Anybody else?

[01:22:59]>> So, um we we will go uh we will start.

[01:23:04]>> No, don't worry. Just tell me how many nodes will be printed.

[01:23:07]>> I think all of them would be printed.

[01:23:11]>> All of them will print. That's a very revolutionary.

[01:23:16]All of them will be printed. And the reason >> uh because in in the function call we we still have all the like drivers basically the function.

[01:23:27]>> Good good. Let's run it.

[01:23:34]All right. It should have given us a correct answer. It has given us a correct answer. But the good thing is that we should be looking at how many nodes are printed up.

[01:23:44]10 only. Four only.

[01:23:54]If I print the return statement over H but is may I incorrect over here.

[01:24:02]Let's try to make this as one now and this as 13.

[01:24:10]The breach has happened over here.

[01:24:14]Correct.

[01:24:19]At this place the breach has happened.

[01:24:21]If I try to print how many nodes will be printed over here.

[01:24:31]Okay. Let me think about a test case.

[01:24:36]Not is too much. Okay. That's the difference.

[01:25:16]Is this a BST?

[01:25:20]If I run this, should it be giving you BST?

[01:25:25]Should be giving us a false. It's not a BST, right? And where is the breach happening over here?

[01:25:32]And this D F2. All right. Or let me make this as three only. And make this as rather than one.

[01:25:42]Let's make it three.

[01:25:52]Where is the breach which has Oh no.

[01:25:55]Yeah. The breach has happened right here. No. At this two and three.

[01:26:01]Right here.

[01:26:05]So if I take that it was the other one was really big that it was you know printing four of the nodes only. But if this happens the breach has happened right here two and three but still it is printing what the 12th and the 11th and the 14th also.

[01:26:29]This side of the tree also even this side of the tree it is printed.

[01:26:37]If I make it five just for sake of simplicity if I make it rather than three if I make it five the line 31 less than or equal to pre it has to be less than right. Just a moment. If I rather than five, let's have four on it.

[01:27:09]All right. But what will be printed over here? All the nodes still.

[01:27:15]Still the 12th and 11th and 14th are getting printed.

[01:27:20]Why is the 12th and 11th and 14th are getting printed even though I have the return statement over it?

[01:27:32]So what I'm trying to say over here is in some of the cases if I have the breach right here only at this place why are we going to the six and the fives and the sevens and the 11s and 12s and 14s with this return statement in the function >> in the function call when we were calling four >> uh there was left of four was two but that's not where the breach happened. So we went to in order for left right and so this this is still in the function call like all right let's see it on the whiteboard let's not have 10 over here let's have three only over here recussion call stack it started from here on it functional column 8 functional column four functional column two functional column three functional column null right so firstly null is out the first node is three which comes out or the recussion stack in the in order manner we compare it with the previous previous is equal to null move the previous to the this location then we do the function call on the right that is out none null Both are out. Function column 3 is out. Now at top of the stack at the in order level we will be printing two. Right? So two is the load that will be compared with this is the root that will be compared with the previous.

[01:29:18]We have the breach. We make the flag equal to false.

[01:29:25]And after that we have return.

[01:29:31]It's a myth that the return will be completing completely stopping the recussion.

[01:29:44]PE students who think that only 8 42 3 will be printed they are thinking that this return will complete the functional calls. it will stop the recussion.

[01:29:57]It doesn't. It is against the two basic rules of recussion that we we did.

[01:30:05]One, whatever has gone inside the stack will come out of the stack. Surely the call stack does have functional calls still left. That is what Mang was pointing out towards that I still have the functional calls left inside the recursive stack.

[01:30:22]The second thing that we made assumption is that return will be not taking the further will not be taking us further.

[01:30:31]Recussion will stop over here is again a breach in the rules. The first rule of recussion was returns to the same place from where it was called. That's it.

[01:30:44]Doesn't mean that it completes all the functional calls. It just completes that functional call only.

[01:30:51]It was the it will be returning it will be returning to the function call of two. That's it.

[01:30:57]Functional call of two is out then the functional call of four will start.

[01:31:04]So the purpose of this return statement is returning to the same place from it was called. That's it. It was not stopping the further recursive calls.

[01:31:15]the further recursive calls will still happen.

[01:31:19]If you are assuming because of this return the whole recursive function will be complete then you should have said the same thing for this return also that we hit the return and we are done. No, just like the way that this return behaved that it returns to the same place from where it was called. This return will also be doing the same thing. It will be returning to the same place from where we called it.

[01:31:47]It will go back to the function call of two that will be popped out and still four will be further running ahead.

[01:31:56]The further once four is complete four will be out. Function call 8 will be done and then we are doing the right recursive call without any condition.

[01:32:04]Without any condition we are doing the right recursive calls. It will do the right reccast really because at the further ones there is no breach.

[01:32:18]Thinking that this return statement will be able to do the condition recussion is a wrong basic that you might have assumed.

[01:32:29]It's the if you have to do the condition recussion then you have to do lag equal to false you'll have to do the condition recussion like that now I'll be having 84 23 that's Oh no.

[01:33:01]I want to do the last basic of recussion today and then we'll be stopping.

[01:33:12]Firstly uh uh it's a myth that if I have a boolean over here I have to do the white function also as I have to do the recursive call as boolean also. All right. I can do boolean based recussion.

[01:33:23]I can do void based recussion also. In all the problems that you have done uh int based recussion or boolean based recussion where you have integer you thought that wide will not work. Wide will surely work. In all the problems where you have seen wide based recussion there the boolean or the inbased recussion will also work for it. So if I don't want to do this way I can do a boolean based regression over here.

[01:33:52]return true.

[01:33:59]Thus converting into a boolean based recussion. A boolean towards left.

[01:34:06]Left recursive call and right call is a boolean right.

[01:34:25]Then return left and right.

[01:34:35]All right.

[01:34:44]If I want to convert it into a boolean based recussion, I didn't do anything. I just put the from the left recursive call we are getting a boolean. From the right recursive call, we are getting a boolean. Rest of the things were kept absolutely same. If the root is equal to null, return true. If the breach has happened, return forge that the breach has happened. It's not a valid BST. I don't need a flag now.

[01:35:08]Works. If I submit it, this should be working perfectly fine. All right. If I do system.out.print root dot value, how many elements will be printed over here? All the nodes.

[01:35:22]Remember there is a breach right here.

[01:35:25]Still all the nodes will be printed.

[01:35:29]So this is equivalent to nonitional void based recussion.

[01:35:36]Non-conditional voidbased recussion.

[01:35:41]If I want to convert into conditional then I can say that if my left is equal to false then don't do the right return false if I submit it this should be accepted but what what's cute will be to see how many nodes will be printed over it all right if I do this how many nodes get printed four so this is conditional recussion conditional boolean based recussion similar to conditional void based recussions.

[01:36:19]All right. Now I can clean this code a little bit. I say that if my left is equal equal to false that is if this is equal equal to false return false right here.

[01:36:34]Don't go further. Don't do the right write right recursive calls.

[01:36:39]Same thing.

[01:36:47]All right.

[01:36:50]Still four only committed. This should be accepted as well.

[01:36:54]All right. Since this is then I can return.

[01:37:00]A lot of times you have seen this code for valid APS but it is nothing but where we started with the white basic questions. Slowly slowly just updating the code right still four nodes will be printed over this is conditional recussion only why if the left is equal to false return false don't do the right recussive part so we can do wide based recussion we can do boolean based recussion we can do wide based non-conditional recussion we can do widebased condition recussion or but now let's see we are going to cover one of the basics of the recussion again let's go to the white base recussion again Let's go to the white base.

[01:38:21]Okay, done.

[01:38:24]Hey, quick question. Okay.

[01:38:28]Why do I need to have the if I put the three node previous over here?

[01:38:37]Is there any issue or the concept that we are trying to learn over here is that what all parameters I should be having in the recursive calls.

[01:38:49]Why do I need to put it in the global?

[01:38:51]Can I put it in the scope of recussion as a parameter of recussion? Can I put the previous as a parameter of recussion?

[01:39:02]If I run this, I it doesn't work. Maybe I'm making some mistakes. Tell me what are the mistakes that I'm making.

[01:39:12]>> You need to pass a value pre like initial value for null.

[01:39:18]All right. and previous over here.

[01:39:22]Probably the previous over here still doesn't work.

[01:39:32]Am I making some mistake?

[01:39:42]>> Anybody?

[01:39:43]>> Yes. What is >> flag passed by value and not by reference?

[01:39:51]>> Pass by value passed by reference. Good.

[01:39:53]Okay. Yes.

[01:39:56]>> Isn't previous root >> previous is equal to root. Okay.

[01:40:02]>> No. In the line 28 uh >> previous is equal to root.

[01:40:11]Okay.

[01:40:12]M okay. Yeah, >> you won't need line 34 anyway.

[01:40:20]Okay, still doesn't work.

[01:40:31]Okay, if you are saying this then you are missing one of the things. Was I doing this that when I went to four? I'm making the previous of four is equal to 8.

[01:40:44]Or when I'm going to two, the previous of two is should be four.

[01:40:49]>> No, we are not doing that.

[01:40:51]>> We are not doing that.

[01:40:57]So if I say that okay, the previous is previous itself. Still doesn't work.

[01:41:05]You can do this.

[01:41:11]You do anything it will not work.

[01:41:15]What is the basic mistake that we are making?

[01:41:25]We make it root. Okay.

[01:41:29]>> Yes. Tanya, go ahead. What were you saying?

[01:41:32]>> We're passing flag by value.

[01:41:36]>> We're passing flag by value. flag isn't is not passed over here. I didn't change anything about flag. I changed previous.

[01:41:44]>> You're passing previous by value >> by pre previous by value. And what what does it lead to?

[01:41:52]>> We don't retain the value of previous.

[01:41:56]>> Correct. That's a great all right by value and by reference concept and it is very imperative.

[01:42:03]All right. You might be giving a working test working code in your recussion. You can be giving when any of the recussion if the interviewer catches you at the by reference and by value concept. Now the game is done over here.

[01:42:18]All right. You might be even optimizing that with with repeated sub problems and you have implemented DP till the time you will not be able to get the by value and by reference concept you will be out and if you are an interviewer in the normal recussion in the in order traversal or validate BST only just please do check that by by value and by reference concept it is in too many production systems in lot of libraries for example react everywhere by value by reference concept.

[01:42:56]What is actually happening over here is 1 2 3. If I have the remember one is to one mapping a helper of three node root and three node previous.

[01:43:19]We have this code. Now let me take this example right here. 1 2 3. And what are we doing? If my root is equal equal to n return and then helper of root dot left you take the previous as previous over here you take the previous as root over here doesn't matter the problem is not what you are taking over here the problem is by reference by by valance helper of root.right and previous. Here what you are doing is previous is equal to root.

[01:44:06]Here you are checking if my previous dot value is greater than or equal to root dot value is equal to false in the code. Let's run it along with the coder.

[01:44:44]test case is 1 2 3. See if I submit it, it gives me the test case 1 2 3 is correct.

[01:44:52]Means I should be expecting a false.

[01:44:58]But it is telling me that it is true that this is a valid BST.

[01:45:05]this code right here that we have written let's call it root this code that we have written over here is telling this is a valid BST it's not a valid BST what is happening over here remember draw the recursive star functional column one and the previous is none.

[01:45:40]All right.

[01:45:42]This is the very first call. Is my root equal to null? Is my root equal one equal to null? No, it is not equal to null. Then we go over here.

[01:45:52]All right. Function corner. We come over here. roots left that is ones left two and we made the previous as one it's fine we should not be making we should not be comparing two with one we should be comparing one with two two should be compared with so let's change it to previous Let's keep it null only.

[01:46:34]Is my root equal to null? No. We come over here. Roots left function call on null.

[01:46:40]And what is my previous null?

[01:46:49]Is my root equal to null? Yes. Returns to the same place from where we called it. This is how.

[01:46:55]So two gets compared to null and we don't compare it. Why? Because we were checking it right here that previous should not be equal to null.

[01:47:03]Doesn't matter. You made the previous is equal to root. You the previous right here and then you did the right recursive call function call nulls. Null out.

[01:47:19]Both left and right recursive calls of two are done. Your preface is still at two.

[01:47:28]Then you took this.

[01:47:30]This is out. Return happens. Return. We return to the same place from where it was. Right here.

[01:47:38]When the stack pop has happened.

[01:47:45]What is your root now?

[01:47:48]One.

[01:47:51]What is your previous now? One is to one mapping root is one previous is what?

[01:48:00]Now your whole jing bang of making the previous is equal to two over here it the previous was made equal to two.

[01:48:10]There is nothing wrong.

[01:48:14]The problem is whatever goes inside the stacks with will exactly unfold the same way.

[01:48:23]Now when it unfolds over here stack pop has happened one is one mapping has to happen root is equal to one but it's previous null over here the previous is null one is never compared to to one is compared to null and that is not compared why because in the if statement I have if previous is equal to none don't compare so I don't catch the breach over here I should have caught A breach over here at 1 2 now one is getting a pair to null.

[01:48:56]You do anything make it previous make it root make it null. So what one has gone inside the recursive stack. Whatever you you came with nothing you go with nothing. Similarly inside the recursive stack whatever you came with you will be unfolding the recursive stack as it is.

[01:49:15]Now one is getting compared to null.

[01:49:17]doesn't get compared and you don't get the breach only then you go to three three is already greater than one done you never catch the breach so if I print over here in the this test case over here in the second test case if I see over here system dot out dot print root value and system.out.tprint print len ln the previous you'll see that one is getting compared with null over here.

[01:50:18]If one is getting compared with null over here then the whole game is over.

[01:50:22]You can make it root, you make it previous. Two will get compared with null, one will also get compared with null. Because whatever has gone inside the stack will come out of the stack as it is. One will get compared with this was not happening in the earlier scenario. If I put the reload previous in the global, it doesn't doesn't go as a parameter of recussion.

[01:50:46]Then let's see this.

[01:50:53]Now let's see that one is getting compared to what? One is getting compared to three node this which is actually equal to two.

[01:51:10]If previous is not equal to null then write the value of previous. If it is equal to null then print two will be compared with none. One will be compared with two. If I have the previous in the global because in the parameter the previous is going by value and when the recussion stack unfolds it unfolds the same make sense. Hence the bridge. So this is the parameter of recussion versus global variable.

[01:52:10]Good. We are done with the class.

[01:52:11]Anybody has question can say we'll carry on with the lecture from here only we'll be doing more recussion we'll be going into the nitty-g gritties of recussion and we'll be doing a lot of what test scenarios all anybody any questions can you uh just summarize in like a single sentence maybe the last issue was we were passing uh like value and we are not able to retain um >> it is 420 then it is 8 it is 840 It is 1220 node 420 840 1220. It is going by value. So it unfolds by value that is null has gone. It will be null only then it will be whatever the next node 840. All right. Whatever that node is or it is 1220 whatever that node is. If you are putting one as null, functional call of two as null, functional call of three as another node that is eight, it is this three node, this null, this null. All right.

[01:53:21]But if you put it by reference if you put it a pointer on it that is you put it in global tree node a pointer on it previous all right I'm using the syntax of C++ over here just to show you then it doesn't need this we don't need to do this >> this is bas this is basically globalizing the variable then I'm having a single reference all right if I have a single reference that is actually equal to single reference then 1 2 3 it will be made as this will be made as that reference 420 will be made as two then one will be compared to all we'll further see it uh just leave this concept for now for tomorrow also right we'll even >> if you're passing parameters value we do something in the code, right? To make that work. I mean, >> what what can you what can you do?

[01:54:27]>> No, I mean like just >> Yeah, probably it's a very dangerous work.

[01:54:33]Probably is a very dangerous work.

[01:54:36]All right, you can do in some of the scenarios but not in all the scenarios.

[01:54:40]All right, Pulkit, what you are trying to say is I don't I want to go wrong on the basics but I want to still find a way out, find a hack out. All right. My question is why do you want to go wrong on the basic?

[01:54:57]You can.

[01:54:57]>> Okay.

[01:54:58]>> In some of the scenarios, all right, but don't get into that habit because somewhere you'll be burnt. Make sense?

[01:55:07]Yeah. We're done with with the class.

[01:55:08]Bye, guys. Have fun.