Binary Trees - Implementation, Traversals, max, min, sum, size, levels

Key Takeaways

this session this fun session in English sort of uh language so it won't happen key you will not understand the terminology and the code part which I'm writing and the conceptual part you will understand it okay I can do full English as well but there are a lot of students who are who will be unable to understand everything in full English. I think so. English is perfect. Okay. Fun way. Okay. All right. Just a second. Hello hello hello hello hello hello hello yes I'm starting the lecture so I am at my home that is my Wi-Fi router I'm sharing a screen just let me know in the chat the screen is visible to you or not actually I'm a street photographer when photos Can you please stop taking [Music] photos? Good evening, sir. Good evening everyone. Please give me one minute. I'm really sorry for all the uh behavior of these students. It is not possible for uh just give me one second if I can mute everyone. Okay. So, everyone is now muted. Good to go. Take just give me one second. I'm attaching the writing screen just I will teach you everything. Uh, all right. Now, please let me know in the chat section. Can you see this entire binary trees? Perfect. All right. All right. All right. Okay, I will teach in English to actually all the concepts from me are going to be in English only. So do not worry about any sort of conceptual thing. Oh, what is this actually? Because anyways, can you see this orange line or something? It is disturbing. It's very disturbing. Yeah. Let me just get it. Whoever is doing this, please do not Sunil and uh whoever is, please let me teach. Just give me one second. [Music] mute. Aba, thank you. Thank you very much. Sorry guys, am I audible? Please tell me. I'm really sorry. I don't know what kind of platform is Zoom. It's very bad. But anyways, let me start the lecture. If you do not know me who I am, I am an ex software engineer at [Music] PTM. Oh, PTM spelling. All right. So I know about data structures and algorithms and I have been teaching DSA for the past two and a half to three years now. All right. So can you help DS and Python language? I will use first of all Java language today. But even if you are coding in C++ or Python you will be able to understand all the things. SN you won't be able to understand because the concept of the node class and the recursion will be exactly same. Okay. And anyways you guys are smart enough to use chat GPT uh for your own convenience as well. Right. So first start before starting I would say key prerequisites may you should know a thing or two about link list. So if you do not know what a link list is, if you are uh uncomfortable to just traverse on a link list, binary trees today will be very very difficult. So please go and study link list first very basics of link list not advanced link list okay if you know that it's very easy first start let us start with basics terminology and imple implementation but first link list or is comparison okay so what happens in link list C++ is also same there is no difference in Java and C++ there is a difference of this arrow thing I'll tell you not a big deal so In link list we all know that we have a head node right we have a head node. Head node we have a node basically it is a collection of nodes. Now see it very very carefully. Basically what happens is in a single node it contains value of kudka value its own value which is for example 10 20 30 40 50 or whatever it is it can be anything and it contains the address of the next node in the link list. So please understand what are these arrows? These arrows actually represent 10 to 10 20. So 10 has its own value which is 10 and address of this 20 node so that we can traverse to 20. So technically this 10 for example this node is a b c d e. So I will say that a dot value is equal to 10. A's own value is 10 but A's next is equal to B. Similarly, B's next is C and all. Binary trees make difference. Let's talk about the difference in binary trees. So, binary trees is very very simple. I will talk about the entire terminology but please make sure of some things. A few things to make sure. If you are one of those kids who just study binary tree for the terminology the let's say for example we all know that this is a tree if you don't know I will tell but a lot of students know that this kind of a structure is in computers it is a tree structure okay now this is a binary tree because of something that I will tell but in general in a tree structure I see that most of the students are concerned about okay This is the root node. This is the root node. These are the leaf nodes. Right? It is the parent of this node and this node. These two are child nodes of these two nodes. These two are child nodes of these two nodes. And all of these things. Now this terminology is important but it is very simple and it can be learned in 5 minutes which I'm going to eventually tell you. But the thing is you have to make sure students I've seen a lot of college students who never study data sector algorithm who just cry when their placements come and they say that okay this teacher did not teach us well or you know something uh things like these which are absolute So you have to please understand you have to you do not have to cry. You have to learn how to implement a node of tree in your language C++ Java or Python or whatever and then solve questions on trees questions on trees and it only happens when you are able to traverse the tree when you know basic recursion. If you don't know what recursion is, if you are unfamiliar with recursion, uncomfortable with even the basics of recursion, recursion may we have a lot of things [Music] like If I'm calling a function from a function and the function is something like this function and then I call it again. So whatever I do over here work one and I can do something after the call. So this is work before call this is work after call. So you have to understand if you are calling any sort of recursive function like this. What happens if I have written a statement over here? What happens if I have written a statement over here? When will this statement get executed? These all things are in very very basics of recursion that can be understood in less than an hour. So you have to understand these things first then only you will truly able to understand trees. So chat who are there to learn about root nodes, sibling nodes, child nodes, leaf nodes, right? So please tell me in the chat. A lot of students are saying English only. So speaker please kind of understand that everything that I'm teaching is in English only right if you hate Hindi language it's not a good thing first of all but for all the Hindi- based audience at least I'm trying to communicate with them and I'm also uh translating it in English at the same time so please be patient a lot of students are here who can only understand Hindi some students can only understand English. I'm talking in both of the languages. Yes. Time duration will be our the current time is 8:18. So I'll take till 1000 p.m. or even more. It totally depends on your dedication. If you want I'll stretch it. Okay. Okay. Yeah. I am I will focus on learning the topics. Thank you. Thank you. All right. So, first of all, let's talk about again the basics compared to link list and trees. So, what happens in in trees? In link list, if you have a node value, it has its own value and it is connected to some other node, right? It is only connected to one node. It is only connected to one node. One node is only connected to one node. It has it has one next. The node is next. Right? So in trees in binary trees in trees in general I would say it can have like it for example this is a node again it has a value let's say 10. So it has multiple next that it has multiple next node. So a single node can actually be connected to a lot of nodes. One common thing in link list and trees is that technically there isn't there is uh no no such two-way connection but there is in doubly link list doubly link list if this is connected to this node this node is also connected to this node via previous link but in regular link list it is not the case similar to that in trees it is not the case like for example 10 is connected to this node which is called uh its children also right it is a parent so a parent has multiple children so also these nodes are known as it's you do not have to mug it up just feel this thing that if there is a parent node it has two or more or even one or zero amount of child nodes. So these nodes are absolutely similar to link list. Now the difference in code is something like this. What we will study today is binary trees. What binary trees? What happens in binary trees is that a single node can have at most two children. At max at max what is the meaning of atmost? It means that a child a node can have zero child nodes, one child node or maybe two child nodes. So technically it is written as something like this. So for example, this is a node. It has some value I will say 20 or maybe 21. Right? So this node is known as the left of this node. Okay? For example, the values are 30 and 40. What I'm trying to say is this node is the left of this node. So left child node. Now this is right child node. Right? Left child node. Right child node also I know. Please trust me. There are a lot of students who do not know a thing about it. That's why I'm teaching from the very basics. So be patient. So this is binary tree. Now we will focus on link list and binary trees for a moment. The code is something like this. We know that in link list when we make class node you have to know what a link list is only then you will truly understand the things and binary binaries. So class node first of all it has its own value. It can be val or it can be uh data also in geeks for geeks practice platform it is data. So it can be val and this has a next pointer as well. In C++ there's a star. In Java there is not a star there. There are no pointers. So the this is what this is a node. We can make constructors as well. But this is a node in link list. Similar to this a node in binary tree is very very similar. It has its own value and it has two nexts. Two nexts. So the names of the next are left and right. They are left and right. So the code of both these things are very very similar to each other. That is why I said key learning basics of link lists gives a huge boost in terms of learning binary trees. Also in interviews, binary trees is uh technically generally the most famous and the most uh usually interview for example in Amazon and big companies. So they love binary trees and there can be a lot of questions that can be framed from binary trees that is the reason and it is very very easy think it is much easier than learning dynamic programming and things like that. Right? So some students are saying it's binary search tree. In binary tree left child is smaller and right child is bigger. No it is not like that. In a normal binary tree there can be any value. Okay. In binary search trees there is a particular property that I will tell you later on tomorrow or maybe day after tomorrow. Today it will be totally based on binary trees only. Yes, the recording will be available uh on YouTube but I am not sure key they will keep the recording because uh it is supposed to be a live class. So you if you have to be disciplined to attend this live class completely class disciplines we should understand the let me make some trees first let me make some trees. So you know binary trees are something like this. A child has two children. But you can ask me that sir in these four nodes in char nodes may they do not have any children of their own. Yes. So just like in link list whenever the last or tail node came tails next was null node it was null. Null is nothing. Right? Similarly, technically the child left and right child nodes of these four nodes are null and null has no left, no right, no next nothing. It does not have its own value. In short, null has no it has a lot of but still discuss this is a binary tree. Now this can also be a binary tree wherein for example this has one left node. It has one right node as well. Now this only has a right node and uh now this has a left node and a right node. So as you can see there is no left node of this node. So it is a null node. There is no left and right of this. So technically there is it will be null. There is no left and right for this and this. So if we just ignore the null node we can clearly see this particular shape is also a binary tree. This is also a binary tree. Right? In this binary tree binary trees in binary trees it is not mandatory for every node to have two child nodes. like it has zero, it has one, it has two again. So this can happen zero or one or two. Now let's talk about some terminologies on trees will be important here. So the topmost thing of a tree basically aa a lot of students must be thinking why this kind of data structure is known as a tree. So the shape is like a tree. The roots of a tree in fact I would say roots are like this. And uh if you just invert it in opposite sense so it kind of becomes like a tree with a root node and the branches right. So this is known as the root node and all of these nodes are known as leaf nodes. Basically leaf node is not like key it has to be the node on the lowest level. I'll talk about levels also but the lowest level. No this is also a leaf node. A leaf node is basically that node which has no left and no right. And now let's talk about the children and the parent nodes. So this concept is relative. It means that okay if we are talking about this node then these two nodes are the child nodes of this node. Now this can also be a child node to this node. This node is parent of these two nodes. This is parent of these two nodes. This is parent of these two nodes. There is also a concept of ancestors. Now ancestors Hindi may it means pur right? So for example, my grandfather is my ancestor. My greatgrandfather is also my ancestor. Technically speaking, my father also comes in my ancestor line. Right? So all the ancestors for example this is the node. So for this particular node, I'm highlighting this node. This and this these both are ancestors of this. Now keep in mind this is not the ancestor of this node. So for example if you are this Aush if he is Aush and he Aush's father now obviously he is Aush's grandfather let's say and he is Aayush's Tawoji so Toji is not under his ancestors please understand this thing technically he is a part of your family but that is a complete tree but I would say He's not your ancestor. Keep in mind to these are the terminologies involved in trees nothing else. Now let's code please write code. Let's code and let's make some nodes and then connect them and make a tree and then we will try to traverse in the tree and try to print the tree. Okay. So Kana what are the main difference between binary search and binary tree? I would just suggest you to be patient and wait for the next lecture which is going to happen tomorrow or maybe even the next lecture which is going to after happen uh on Monday. Okay. So I will talk about BST the binary search tree in very detailed manner. Okay. And again the concern of you guys should never be what is the difference between this tree and that tree. It does not matter in interview. No one is going to ask you what are the differences between the trees. the interviewer will straight away ask you a question of binary search tree not even telling you that it is a question of binary search tree that also you have to identify okay so I will talk about all these things and what are the applications of binary tree so technically it is a hierarchical based data structures gorov but I will tell the applications in binary search tree right technically speaking it has its applications which are very interesting I will tell you all about it Okay. Can you code with diagram base? What is diagram base? Okay. I'm opening up intellig idea for you guys to understand a lot of things. And uh let me just tell you what I'm going to uh just a second Java programming. All right. So in code first of all I'll show you how to create a node. Second of all, I'll show you how to print uh I'll show you the connections how to connect the nodes with diagram. I'll make a diagram and then connect it. Okay. Third, I'll tell you how to print it via recursion. Now, this is the most important step because this step you guys will understand what is recursion and what is a binary tree in reality. can know I can't code in every single language. Okay. So, please do not move away from the class. It is your choice. But again, I have to code in one language only. It is physically not possible for me. You will get the codes for all the languages. Uh I'll make sure that the GFG team uploads every single code that I'm writing in Java and then they will convert this code into CPB and Python and send the codes to you. Okay? Please tell me in the chats uh if you are unable to understand English for some reason. Some students are. Okay. So I'll just close this thing. I'll I'll share a screen. Please tell me if you are able to see my screen in just one two and three. Okay. Intelligj IDE open. This is IntelliJ IDE. IntelligJ IDE. Okay. Intell J idea. This uh is a ID for Java. All right. So I'll open up trees. I have already opened up trees. Let me make a folder for you guys. Okay. Let me make a folder for you guys. This my only uh trees geeks for geeks. And I'll make a file basics nodes dot java. Okay. So the C++ code is very much similar. There is not not much difference. So in C++ this psvm public static void main is actually int main. Okay. So C++ we write int main and there is no uh like this. Anyways, so we make the class outside here or maybe we can make it here. But I'll make the class here. So I'll make a class node like a capital N. So the uh the node can be accessed to every single file of this thing. Anyways, you do not have to worry about it. So what happens in link list? I said it has a value and a node next. Here there is left and right. take second bus left and right and you have a data type. So what happens is if you do not know object- oriented programming then do not watch this lecture. It will be very difficult for you to understand anything. But in short if I tell if we write int or float or care so these are data types. Now node is also a data type that we personally personally created data. So what I'll make is first of all I'll share a screen. Share a screen again and I'll make a tree. Draw a tree and then we will make it. Then we will make it. Cool. I'll make a tree. I'll make a tree. The tree is something like this. The tree is something like this. And the values are 10, 20, 30, 40, 50, 60 and 70. Let's say co you can give any value. You can give any value. Okay. So I have to make this tree. Uh I'm also naming the nodes as a b c for your convenience. Please. So this is the entire tree. So as we can see this is the root node. So let us make seven nodes first of all and let's put the values at 10 20 30 40 50 60 70. Yeah. So let's go to the code part again. Uh let me share the screen. I know it is hectic. Again and again I'm sharing the screen. The screen will be visible. So what I'm trying to say is I'll create seven nodes. Node A B C D E F it there were seven G seven nodes. So node A I created node A. Now I will also give the value. I give the value here only. A value A dot value we use the dot operator and in the in C++ we will use something like this. Okay. So a dot value we will give as 10. Now what is happening? What is the problem? Uh we have to initialize in Java also. I have not taught constructors to you anyways. So what we will do is take we'll make some constructors as well. Okay, this is known as a constructor. Okay, this is a default constructor. This is a default constructor. I don't think we have to initialize this as well. Okay, we have to. So let me teach you constructors as well because it is very important to just understand the concept. So in link list I hope you guys have already studied link list and in link list there are constructors. So it makes our work 10 times easier. So for example we have to create a node a with value 10. If you if we want a variable int a is equal to 10. We can clearly give it 10. Right? It is very simple. So constructor is very similar. What we will do is we will give a value. we will give a value and this val is equal to val. So just mug this thing up constructor I would say please constructor what happens is if I give node a is equal to please is equal to new node and if I give the value 10. So what happens is a node is created a ball is created circle a with value equal to 10. Now we will create six more nodes. So in coding we never type again and again. We just copy and paste. So this is node B. This is node C. This is node D. And this is node E. So Intellig Idea is a very bad software sometimes. Anyways, it gives auto suggestions and all that all those things. This is 20. This is 30. It has value 40. It has value 50. It has value 60. It has value 70. Okay. So I have seven nodes in total. I have seven nodes in total. Now comes the connecting part. A bar. Let's go again to the diagram. Please note these things or at least have a clear picture in your head. Okay. Let's come on to the screen. The screen might be visible to you now. Okay. Now this was the tree. This was the tree. Hattona. This was the tree. This is A B C D E F G H. What I have done connect uh currently is something like this. Let me remove these connections. These are known as connections. So what I did what I did is I created seven nodes but they are randomly hovering. I don't know where. Okay. Now I have to connect them in such a way that A is the B of every node. It is the root node. So A's left should be B. A's right should be C. I would say A dot left is equal to B. A dot right is equal to C. Okay, I am writing it here also. A left equal to B. A dot right equal to C. After writing these two statements, this happens. I will write B dot left is equal to D. B dot right is E. C dot left is F. C do. right is G. These are the connections. Now let me actually connect in code. It is very very simple. It is very very simple. Very straightforward. We created all the nodes. Now we will we will what? Comment. Oh sorry connect. So this is known as a comment. I think everyone knows anyways. So we will connect the nodes now. So a do.ft left was what? A B C. So A dot left is B. A dot right is equal to C. Okay. Similarly, now B dot left was A B C D E. So B dot left was D and B dot right was E and then C dot left was F. C dot C dot right was G. Now you might be wondering that okay A has left and right, B has left and right, C has left and right. What about D, E, F and G? What are the left and right? So by default every nodes for example I never made these connections. So actually what was the scene that in all these nodes in all these nodes the left and right are initially null. They are initially null. Okay. Now let me connect also I have connected these nodes. So this is the tree. So after doing all these seven things, all these statements, the tree is finally formed. Take it. Tell me in the chat if you are able to understand and for all the Hindi users uh I am really really sorry because tasa uh there is a lack of energy from my side because I am actually uh translating every single thing inside my head first then communicating with you guys and talking in English. So it is a load for me. Okay. So pointer next node. So Arjun what happens is in Java there is no system of pointers but in C++ if you want to understand what actually happens is that in A's left the B uh the node B is not stored. In Java it is stored. In C++ what happens is in A's left only the address of B is stored. So from there we can fetch the value and the next node and the left and right of that. Okay. So all of you can just understand it understand it in this way. Then then in uh that in A's left uh the exact B node is not stored in C++ the node's address is being stored. Okay. Doubt. What happens if you put G children of two parents mistake? Oh, okay. Very very nice question. Very nice question. So, OB is asking a question. Yeah, it is very difficult to draw do trees in C language. Never do data structure algorithms in C. There is absolute no support. Okay. So, it is a very bad language for it is a good language. But the thing is key uh never do data structures in C. Okay. it is only feasible in your college studies where the professors are uh doing everything in gapeta manner. So what what a guy is asking me I forgot his name an intelligent student asked me for example G was children G is now children of C. Uh what happens if I make G children of B as well or for example I make G children of A. Now obviously uh a particular node can only have one left and one right. So for example if I say a dot left after writing a dot left b if I write a dot left is now g. So what happens is this connection actually may breaks and a left will become g. Okay first of all first out. Second doubt is now for example there was there was for example no right of B. Okay. So the tree was something like this and this is also a binary tree. There is absolutely no problem. This is a binary tree. So what happened happened is B has only a left child. C has left and right both and we have six nodes in the tree. It is fine. Now if I just make the right of B as F as well. So technically can you do it do this? Yes. The answer is yes. We can do this. Okay. We can do this. B's right is F. B's left is D. C's left is F and C right is G. But is this data structure known as tree? The answer is no. Okay. This is no more a tree. This is not a tree. This is a graph. Okay, we will study graphs much later. Yes, this is a valid data structure. But tree is this a tree? No, because in trees there can be no loops or something like that. This forms this is kind of a loop or there it is a very clear thing that a particular node can never be a children of two given nodes. Okay. Now in reality in family we are obviously children of our mother and father both. But in binary trees it is not the case. Okay, it is not the case. So it cannot be done but it it is no longer a tree. Okay sir a quick revision but I'm already very slow currently a lot of students might be disappointed but uh revision end I'll do okay sir instead of binary tree if we need to connect the tree it can have multiple child. So how can we connect that? So the thing is this is known as a binary tree beta. This is a binary tree. There is a another thing known as a generic tree. Generic tree. So what happens in generic tree is that if you have a node, it can have any number of ch child nodes. For example, it has immediate three child nodes. Now this one has two child nodes. Okay? This one has only one child node. This has zero child nodes. Now this particular man has four children. So this particular data structure is known as a generic tree where any node can have any number of children. But again in a tree you can sleep janistan. Anyways uh whatever your name is the thing is in a tree a single child node can be only connected via one node. system there is a child node and it was actually children of two or more nodes. Okay, this is generic tree and we are going to study binary trees which is a simpler form to understand like doubly link list. Would it be possible for child to keep the pointer of their respective parents? I'm wondering if there would be any benefit of it. Yes, kulbush and chopla there are benefits of doing that. Technically speaking, yes, it is no longer considered as a tree. But we will do some particular problems where actually for a child node, we have to store the data of its parent so that we can go back as well. So in some particular questions we do that in some particular questions or questions. Okay, that is the thing in case of generic tree how many container we have to declare inside the node class. So very nice question although it will not come in your interview. Uh it is highly unlikely but uh as you can see in a binary tree the node was something like this right it has its own value left and right. Now in generic tree we do not know we do not know that in a generic tree how many child nodes will be there of a single node. So it is very simple what we do is we keep a array or a array list. For example this is class node. Okay. So it has its own value. Any node has its own value and it has a connection. It has an array list of nodes. So in Java it has an array list or maybe array of this node. Right? In C++ there will be a vector of nodes because I don't know how many children are there. Okay. So we use array. Which language should be preferred to for DSA to crack interviews? You can use CPP or Java. Anything even Python will work. Okay. Yes. C++ and Java technically speaking are kind of uh better than Python in the sense that whenever you are going to give uh whenever you are going for an interview. So the thing is uh the one who is taking the interview in most of the cases he has done his data structures and algorithms in C++ Java. But the situation can change. I don't know if you are in first year or second year. Uh so maybe when you give your interview, Python is a very popular language. But anyways, at the end of day, it does not matter. What matters is your concepts, right? If you are able to communicate the problem even without doing the code, you will be given full marks. Okay. Yes, you can learn uh DSA from Java. But please tell me in the chats if we can move ahead move forward. This was generic tree. This was binary tree. We actually coded the binary tree. Now we have uh we have made sure key how to make the node. We know how to connect the nodes and we are going to study printing of the nodes via recursion. Now what happens is what happens is technically speaking this is the root node. This is the root node. So the root node actually is the entire tree node nodes before printing which a lot of teachers never tell you. So please make sure your entire attention is in this screen right now. Please understand. Please understand. What happens if I want to print all the values of all the nodes? I can simply print it. In C++ it is see out. In Java it is system.out. In Python it is print. Okay. I can simply print A dot value and it will give me the value of A. I can say B dot value of B. Right? Very very very simple. Now what I'm trying to say is something like this. For example, I want to print the value of node E. take node B first of all. So I will do B.VA val and I will actually run the this file and check B value 20. Let's check here they go. You can see the answer is coming out to be 20. It's perfect. Now what if I ask you that without using B you have to print value of B. Without using B you have to print the value of B. Yes, we can do it with A. Now if we use A, what is B? B was A left. B was A dot left. So when A dot left is B. What if I do something like this? A do. And let's check what what happens. You can see 20 is happening. What if I do a right. Tell me in the chats first. Tell me in the chat. The Vnavi is saying C. Perfect. is also everyone is perfect. Very good. Very nice. Very nice. 30 is coming out. Now tell me in the chats please how can we print the value of G node without only using with only using A. We have to print node G's value which is 70 without using the parent of G which is C without using G itself using A. Yes, Vanesh is absolutely perfect and Arjun Arjun is also Ni is also perfect. Arushi is also perfect. Everyone is perfect. Adita is perfect. Okay. So not next. Yeah, Adita is not perfect. Basically what we will do is some students might be anyways. So for example this was the tree node. So what I'm trying to say is I want the node G from A. So A dot write is C. C dot right is G. A dot right dot right is G. F value print. So I will do A dot right dot left. Please make this diagram in your copy right now and then you can have a feel of what I'm actually coding over here. AR left value saying I think you guys are now having an idea what I'm trying to say. So this was a very important thing what I wash trying to tell you this is a very very important thing okay because uh now you will be able to print the entire tree the entire tree with only having the access of the root node. This is known as the root node root b of the tree father of the tree. Right? Could you please show the diagram? Yes I can show you the diagram. This is the diagram. Okay, it's very simple. You do not have to mug up this diagram. It is very simple. They could 10 20 30 40 50 60 70. Every node has two children except the four nodes. A very very simple diagram. 10 20 30 40 50 60 70. You can use any values. I have you chosen these values. Okay. Yes. Uh Ankun Ankunuru Ishika is asking me what if the tree is very lengthy. Huh? I'm going there eventually. Okay, I'm going there. Can we print the value of any node using its child node? No, we cannot. We cannot because please see the arrow, right? Please see the arrow. Please see the arrow. From A actually we can go here. We can go here as well. Now from B we can go here and here. And from C we can go here and here. So eventually from A we can go everywhere. But if we are at B then we can only go to D and E. We can never visit A, C, F and G if we are on B. So from a particular value we can only just go down and we can never go up unless and until we make some kind of connections but we are not doing it right now. We I am going to take three days a lecture. 3 days lecture. I'm going to take these lectures for 3 days. Okay. Yes. It is a directed pre. You can also say this thing. Very nice. I hope you understood. Now what uh what if uh something like this was the case that uh you cannot see the tree. You do not know about these child nodes. You do not know about these connections. You do not know anything except the root node. You have the access for with the root node. Can you print the entire tree? Yes, we can. We can print. We can absolutely print using recursion and in a binary tree it is very much feasible because there are only vesto in any tree but in binary tree if we have a left and a right. So please tell me if I want to go from a node to its left and right I can use recursion. Why recursion? So so that when I am going to left it solves its problem. like I'm printing the node then I'm saying recursion by please print the left part and please print the right part that is your job it is not my job okay so what is the kind of code that we are looking for example I want to print the entire tree I want to print all the values of the tree uh in any order I'm not concerned about the order what I will do is I will do I will make a function known as print and I will pass the node I know I hope you guys know about functions and methods. I hope now I will make oh not here you the problem. Yes, this is the note. I will make a function public static or private static or whatever in Java in that you have to we will provide the the public static void print I will make I will make something like this void print void print void print in this print I will receive a root node I can name it A I can name it B I can name it Z I can name it Aush but the thing is root node is kind of a convention for this. Okay. So I have passed a the root node over this and now this function has the responsibility to print all these seven nodes. So what I do is I I use recursion I use the faith of recursion. So what happens in recursion? If you don't know recursion you can also study right now right here only. Recursion says that okay right now what what are all the things I'm having I'm having this root node can I print the value yes I can so print the value okay print the value I will print the value root dot value okay I printed the value perfect now what happens in recursion is I have to print the left node and the right node and then the left and right of the left and right node diagram for greater understanding. Please do not skip. Okay. Uh can you not see the uh coding screen like right now I am showing this particular screen but I was showing the coding screen. We can see. So what is happening is this was the root. I printed the value. Now, now I wanted to print 20, 30, 40, 50, 60, 70. How can we do all these things? Using faith, using vishwas, using barosa. So what we will do is we know that if we have a then a has some left, a has some right and that left has some left and right, left and right. So we will not actually print keep on printing like keep on printing like print a. Then print a do.val a do.val a do.tright.val a do.val a do. Right. That is because we don't know left right. So we use recursion and we say is bar function we passed a the next time we will make two calls. Why two calls? Because this is connected to two people. So we will make two calls for every node. At max it is connected to two nodes. This can also happen that it is connected to one node. Does not matter. Every node is connected to two nodes. Please understand if this is not uh a node it will be a null. It is also a node. Please consider okay. So every node is connected to two nodes. Please understand. And null is the exit point. Very important. Very important. Very important. Intentionally I'm trying to tell you again and again. It fits inside your head. So why we use public and started? Yeah. Please this is not the right time to ask about this. Whenever we will study methods in Java, we will understand just please forget about this thing because then you your mind will be diverted in the oops part which which it should not right now. Okay. So I said key I'm printing this then I'm calling left and right. How to call again? Print call the left pass the left node. Oh sorry sorry. left node and then I am I'm calling the right node. That's it. This is the code ethnasa bus three lines. Yes. Now we have to make sure about one thing because if I call the if I print this, if I call left, if I call right, then left will come here. Left will print its value. Uh left will call its left and it it right. Now for example what happens is if I am at a level where the node which is passed is null. Yes exactly base case. Very nice. Very nice. B are saying B case. The base case is something like this. So what if what if if if the root is null. If the root is null then I I just told you that uh in null null has no value. Null has no left. Null has no right. Null has nothing. So we will return. What return does is return means kam tata bye-bye goodbye ga. Have you seen that meme of Rahul Gandhi? Kam tata bye-bye goodbye ga. So return means finish from this particular call. We will see the diagram. Please wait for 2 minutes. Please wait for 2 minutes. Let's run this code. Yes. Can you see this thing? Tell me in the chats. All the nodes are printed. All the nodes are printed. Okay. OB just to make uh you guys feel comfortable. I'm doing two things. Two things. The first thing is key. The first thing is just to make you comfortable in the sense tree 10 beta 20 either we had 30 we had 40 over here in left we have 50 we had 60 we had 70 very bad handwriting anyways and it's go A B C D A B C D E F G we had these seven notes now what we will do is what we will do is just to make sure key my print code is actually in reality it is working. I don't know it is working or not. I don't know if I the print node the print function that I made is working or not. Maybe it is working only for these seven nodes. What happens if for example I remove this node? So B has no right B has no right node. Right? And now f has two left nodes of value 80 one left and one right and 90 named h and i. Uh let's make this code. Let's make these nodes two nodes first and let them get them connected to f left and right each and let's remove b is right and let us see that 10 20 30 40 60 70 80 90 is printed or not uh without changing the code of the print function. This was the code. This was the code. I will not change. I said that B's left was D. I am removing the connection B right E. It is not necessary to remove this node. It is lying in space but let's comment this code. This is no longer a line. Now what I'm doing over here is I'm creating two more nodes. I'm creating two more nodes. I'm creating two more nodes and we create nodes like this. The nodes were h I can see them. You cannot see them. M screen I can see them. Node H with the value new node into value. Its value was a C 80. And I was creating one more node uh I and the value of I was 90. It was 90. And I actually connected them as well. Actually connected them as well. I was connected connecting them at F. So F dot left is for example H. F.Right is for example I. Okay they please S. I created these two nodes and I did these connections. I removed this left wall connection. In fact, I should actually write this B's right is equal to E. I am actually commenting this. Okay. So, I removed this and this I created these things. Let me run the code again. Again, the print function is being run. Okay, the print function is being let's check. As you can see 10 20 30 20 40 30. Now you might be thinking why 301st and why 41st and 30 after that. We will talk about that in a moment. Even before this uh it was not the exact order of 10 20 30 I don't think anyone noticed that before. Did you guys notice I'm talking about this for example these are commented and let's talk about the old tree. This is our old tree puranala tree and then run it. So as you can see it is 10 20 40 50 30 60 70 it is not 10 20 30 40 like this this this that is level order traversal we will study in 5 10 minutes but the all the nodes are printed that was the scene. Okay now let's uh and do it again. So you can see you can see 10 20 40 30 60 80 90 70 are there only 50 is missing. Was 50 missing in my diagram? It was it was let me confirm it. Let me 10 20 40 30 60 80 90 70. It was uh as you can see 10 20 30 40 there is no 50. So these new nodes are being printed. So no matter now whatever I do I make these two child nodes then these two child nodes and child nodes and child nodes and a very very big tree every node will be printed if I use recursion. Why? Why? Now before doing the dry run of the recursive part I want to uh I want you guys to understand what recursion is. If you understand the rec understand recursion and you understand the trust okay trust recursion I would say trust the process trust recursion if you start trusting recursion now you can solve any question because what I did was what recursion did is it printed nodes value then it said key okay call the left it will print all these nodes call the right it will print all these nodes I have to do nothing about it I have only I I have to mention a base case only where wherein when null comes I will say that okay it is nothing just go back return okay so you have to trust recursion okay also a very very important factor let me tell you in a tree there are three parts in a tree parts in every tree please remember in every binary tree we have three parts you might be thinking okay there are 1 2 3 4 5 There are a lot of nodes. How how can these be divided in three parts? Every single tree can be divided in three parts like this. So this is the left subree color. This is the right subree. This is the right subree. Please guys understand this thing. And this is the node. So we have root left sub tree right sub tree left right s u b sub tree the concept sub tree okay so can you not say that this in itself is a binary tree yes it is it is can you not say that like even in a generic tree if I pick up this node and uh forget about this This thing in itself is a tree. Now again if I move to this tree if I just forget about this this part this in itself is a tree node and child nodes. So every sub tree of a tree is a tree. Right? What I'm trying to say is this in itself is a tree. This is a tree. This is a node. So any tree is represented like root left sub tree and right sub tree. Please write this thing in your notebooks or whatever because this is a extremely this is an extremely important concept. Using this concept we will solve all questions. Okay. You have to understand this and you have to trust recursion. So what recursion was doing is because whenever we called the function print initially we passed the root for example this root. So we actually did not just pass the root, we passed the entire tree. Whenever we pass this, we pass the entire tree associated with this. Whenever we pass this node, we pass the entire tree associated with this node, right? Because we can access it. Of course, if we are passing this node, we can never access these values. But if we are passing this node, we can access all values. Okay? So what what we are doing is what recursion is doing is in the let's come to the code again and let me make you trust let me make you trust recursion that we know the structure of a tree it has a root it has a left sub tree it has a right subree the value of root is printed then I am calling the function again I'm saying recursion recursion is is printing all the values Recursion is printing all the values in the right sub. I'm just making a base case. Please tell me in the chat if it [Music] is sir what is the time complexity? I will tell you about the time complexity when we reach DFS and BFS. It is big of n the number of nodes. If n are the number of nodes sir can you please draw recursion tree once? Yes. Wignesh please wait. You were not defined root. So how to call root? I did not get you Priya. Actually we did define. Oh ho ho. Okay. I got you. I got you. If you students are thinking that uh here it is mentioned as root, right? And uh in this main function there is no root. I am actually calling a. So why the hell this is not a? I think doubt. But uh I think you should know basic concepts of coding. Uh even if we pass a particular array or if we pass a variable, we can change the name of the variable and it will still hold the same value. Right? In case of arrays and technically what this node is, this node is an object. It is a data type kind of a data type but it is an object. So whenever we pass objects into functions, we pass objects into functions, we can change their name. This root, the name will be root, but technically it is pointing to a only. This is a right. This is a this is a okay. Yes, I have scrolled. Are you seeing this node? You can write sir how the roots are shifting to their child nodes for further printing. Now let me do the thing so you can understand you are only concerned about a particular person changing his job or not and not about your placements which is very bad. But anyways Let me just dry run the code. Now I am making my original tree for you guys to understand better. Okay, I'm making a tree of less number of nodes like this is not less exactly these are seven nodes which are being printed there. These were seven nodes. I'm making my original tree. The names were the man in the main function. I named them A B C D E F G and I put the values as 10 20 30 40 50 60 70 a remember this thing when I was trying to print this tree or all the values of this uh these uh all the values of the nodes of the tree. So in the output screen in the output screen. So by output screen I mean that whenever I am showing you intellig idea while screen so here I am writing the code and here the output is coming. Okay. So in the output screen you guys must have noticed that the order of the values was a was very weird. Actually I know what the order was. Let me do something. I for sure that it was 10 and it was then 20 right it was 40 and 50 then it was 30 60 and 70 I'm pretty sure in this particular order the values were printed in this particular order I can even show you please mark in uh please write it down in your copies let's do do a exercise 10 20 40 50 30 60 70 right now I will print it and I will tell you guys how did how how in the world did I predict key values and even if I change the tree I can always predict it okay not predict I can actually uh solve it so let me go to the screen again and let's uh move to the to the original tree so our original tree was something like this was the original tree and let's remove these things so this was the tree with seven nodes 10 20 30 40 50 and the connections are also perfect. Let me run the print code and then you can see 10 20 40 50 30 60 70 pre-order patience. A little bit of patience is a very nice thing for you guys. Okay, now let me go to my iPad screen and let me show you the magic how the magic is happening. Okay, let me write the code as well. Actually the code was this. It was void print and then then a node was received. Okay. And then I was doing the base case. If uh root is null I am doing return. Okay. Then I was what I was doing something like this. I was printing system.out.print.l or see out in C++ or print in Python. I was printing the value and then I was calling its left sorry print function I was calling its left then I was calling it right child. Please see this thing very carefully. Just kidding. I will tell you five six times also if you do not understand. This was the code. This was the code, right? This was the print function. So I passed root. What happened is technically initially I said that okay root was this. I'm making a variable R. Please understand that R means root in this case just to make it short. Okay. So initially R is R means this node. A also means this node. Got it? Take care. So let's move on to the code. What is happening? Uh if root is equal to null return. So is this root null? Please tell me in the chat. Is R equal to null? Is R equal to null? It is