SDP on Ace Coding Interviews: DSA Mastery with Java Day 10

[00:00:12][music] [music] Heat. [music] Heat.

[00:00:31][music] Heat [music] [music] up here.

[00:00:53][music] >> [music] [music] [music] >> I was very much interested in learning digital marketing course for a very long period of time but I don't get a proper platform. So later from my college I get to know about Excel and I enrolled in XLR course. It was really good experience. Um our course has been taken by mayors and he was very good teacher.

[00:01:39]He not only focusing on theory but he's doing how real digital work, digital marketing works and um it was in total very good experience. I get so much of knowledge here. They not only focusing on uh study uh they also conducting different exam to test our knowledge and uh as we are giving the exam so to appreciate our work they uh give certificates uh for the toppers and along with the certificate they give hampers. Thank you XLR. uh recently I was searching for digital marketing courses in online in Google and I came across XLR and I attended uh digital marketing course which was for 15 days.

[00:02:28]My mentor mayor uh helped me for uh attending these uh classes. So he is a very informative and helpful guy. In the course end there is a exam which I topped. So I came to the XLR office in Bengaluru. This digital marketing course has helped my uh career and uh uh my skills to develop and the certificate has helped my uh company to join. Thank you XLR.

[00:02:59]>> I came to know about this course from my college actually for learning platform.

[00:03:05]This is very nice and I learned from year charge GPT and AI from online because he's teaching for me for a generative and charging this technology in more and uh after finishing the courses I came from for collecting the certificate I seeing the classrooms and faculties classroom is very nice after the completion of exam uh they will give uh gift and certificates thank you excella for giving these courses. I learned lot of from this. I gained the more knowledge from here and thank you. Thank you for Excel for teaching us [music] [music] Heat.

[00:04:08][music] [music] Heat.

[00:04:20][music] >> [music] >> Hello guys, I'm Vikram Mahajajan and I'm studying in Swami Veanandanda Institute of Technology College and I came across a training program uh which was uh mobile app development using Flutter which was given to us by XLR solutions.

[00:04:53]questions. I came across this program through my college faculty who told us about this program that it is a very good course and you should enroll in this course. So I enrolled in this course and initially I felt really good about this course because they started everything uh from a very basic point of view that even if someone who doesn't know anything about flutter or anything about mobile app development can also learn the same way the ones who know about it are learning. So no student was left behind and everyone was given equal attention. All the doubts throughout the course were cleared and um if we had any questions also uh we were like the trainer was also ready to stay for a longer time then it was scheduled even for the sake of doubts. So that shows how important the students are to them.

[00:05:47]So it was a really good experience with XLR's program and by the end of the uh training program I was able to develop my own uh my own application and through the development also there was another point. Yeah. So uh our sour taught us about how we can connect our own mobile phone to our laptop and write code in our laptop and you can see the output in your phone which is really creative and interesting for me. I felt really good about that. So in the end I developed my own mobile application. I showed it to my mother. I showed it to my friends. I felt really good about it. So uh I would really suggest XLR. Uh I would recommend it to all my friends who take courses from here as they focus on the children, focus on the students and they focus on what's necessary that is the students doubts gets cleared and everything else.

[00:06:43]So today I came down to the XLR office like to collect my certificate. So I got to know about what other courses XLR is offering. It included data analysis, data analyst, uh social media marketing and fullstack Java and many more courses which were interesting and they gave us an insight of how everything happens and they take you through the course from the starting of the course to the end and what next that is placements as well. uh how you should be going into the interviews and how you should be approaching to companies, your resume building and there were so many things which XLR is going to help you in and they are ready to give you all the knowledge required even if you are a beginner. So I really felt good about this visit and I would really recommend XLR to everyone who's listening to this and also to all my friends that Uh very good evening Amar. Can we start now?

[00:08:02]Hello.

[00:08:04]>> Uh yes sir.

[00:08:05]>> Okay. Great. [clears throat] Okay guys. So very good evening everyone and welcome to the session. Today we are going to talk about the trees. Okay. In that we'll talk about trees, binary tree, tree traversal and BST, binary search tree. Okay. So these are the topics we are going to discuss over here. Uh can you guys once confirm everyone? Am I audible to you all?

[00:08:32]Can you hear me clearly everyone?

[00:08:46]Okay, great. Great. Thank you for the response. Okay, so can anyone elaborate for me what do you mean by tree? Can you define a tree for me?

[00:08:59]Yes. Can you define a tree for me, guys?

[00:10:05]Uh guys, can you please wait for 2 minutes? Hello everyone.

[00:10:10]Can you just give me a 2 minutes out, guys? Hello.

[00:10:15]Please wait for 2 minutes.

[00:13:07]Uh okay guys so very sorry guys for that. So let's start with the tree. Okay so obviously tree is a data structure.

[00:13:14]Okay so tree is a nonlinear hierarchical data structure used to organize data in a parent child relationship. So we are going to organize the data in a parent child relationship guys. Okay. So unlike array or link list which are linear a tree branch into the multiple path that's why it is called as a nonlinear data structure. So you can see the one example over here organizational hierarchy. So C will be the co will be there under that multiple managers will be there under manager multiple employees will be there. Okay. So each employee report to one manager. Okay.

[00:13:50]And then it is going to form the tree.

[00:13:53]Okay. So that is how you we can define the tree over here. Okay.

[00:14:02]For now it's not in. Sorry, can you please uh you have sent the message for whom?

[00:14:11]To me.

[00:14:22]Okay. maybe for someone else. No issues.

[00:14:30]Okay. So, uh guys, uh real world application of the trees are like file system. So, folder and file hierarchy.

[00:14:38]Okay. Company like employee hierarchy and all. Right. Then, uh colleges, so department, classes, student. So, in banking, account categories. Okay. Then HTML, XML, you have a DOM tree. in machine learning decision tree classifier algorithm. So there are many examples of tree are there. Okay. So computer folder is a best example of tree data structure. So every folder can contain multiple subfolder. So there are certain terminologies which we need to understand before going ahead. Okay. So uh like root so two uh topmost node will be there. Okay. So that is called as a root. Then parent node will be there. This A is whichever node is having a children it will become a parent node. So A is also parent, B is also parent and C is also parent. Okay but D, E, F, G are not parent. Then child node node connected below parent.

[00:15:31]So B is child, C child, D child, E child, F child, G is child. Okay. And then the leaf node. So node with no children. So obviously D, FG are not having any children node. So that is a leaf node. Then sibling node having a same parent. Okay. So D and E are sibling because they have a B. B and C also sibling because A is a parent.

[00:15:55]Right? Then A is connection between the nodes. Height longest path from root to leaf node. Okay. So A to G is the height of the tree. Okay. Then level distance from root. So from the distance to root and number of children it is a degree.

[00:16:13]Okay. So all these things are I hope most of you are aware of that okay so you understood that we'll discuss further more but before that we'll see how we can create a uh binary tree representation in a Java okay so if you remember we talked about in link list about the node so in similar pattern we can create it create a uh node uh tree over here so wait a minute three node we will create here I'm sorry I'm sorry I Open tight.

[00:16:59]Okay. So you guys can observe this simple code for representing the node into the tree. Right. So first of all we are creating a class called as a node.

[00:17:08]In that data one variable node left for left side node right for right side and then we'll create a constructor node in data and this dot data will assign the data and left right we'll assign a null because individual node we are going to create is that okay guys this code for creating a individual node in a tree.

[00:17:29]Hello everyone.

[00:17:49]Okay, great.

[00:17:56]Good. Let's move ahead now.

[00:18:06]So, so creating a binary tree. Okay. So, we'll see how we can create a binary tree into the uh Java using Java code and all. Okay. So, wait a minute.

[00:18:26]What do you mean by binary tree guys?

[00:18:28]Can anyone define a binary tree for me?

[00:18:31]What do you mean by binary tree?

[00:18:39]Hello. What do you mean by binary tree guys?

[00:18:47]What do you mean by binary tree guys? Am I audible guys? Can you hear me?

[00:18:56]Hello.

[00:18:59]Yes. So, what do you mean by binary tree?

[00:19:22]having at most two children. Correct? A binary tree is a type of tree which is each node can have at most at most is very important. Two children, a left child and right child. So we are going to create that over here. Very good.

[00:19:36]Okay. So you guys can see here first of all we are creating a class called as a binary tree. In that we'll create a node static class node int data node left right and then we'll only assign the data to this current class variable data. Okay. And then main method will call that node. So node root is equal to new node 10. Then root. 20 root. 30 and then root left. 40 root left dot. 50.

[00:20:04]Okay. So you can see here at most two childrens are there for each tree. So that's why it is called as a binary. Is that okay guys for you all?

[00:20:14]Binary tree. How we can create a binary tree in Java?

[00:20:22]Yes, everyone.

[00:20:27]Correct. Correct. So is that okay? Have you understood the Java code for creating a binary tree?

[00:20:37]Okay, great. So can you please practice this? You have a 10 minutes. Can you practice this everyone?

[00:20:44]Hello please reply. Can you practice this?

[00:20:51]Please practice it.

[00:21:32]Guys, if I made your disconnect then I will contain connect with the another network. Okay, but I'm there only. Wait, please practice this.

[00:28:21]Okay guys, very good. So I hope everyone completed that good. So this is how we can represent the binary tree. So there are types of binary, full binary tree and all. Okay, so complete binary tree, perfect binary tree. Okay, so I will request you you can revise those things over here. Right. So we are going to see how we can insert into the binary search tree over here. Okay. So for that we'll see the okay good so we'll see this law program over here. Okay. Should I explain these types of binary tree guys before the going ahead?

[00:29:06]Full binary tree and all.

[00:29:17]Okay, see here. So full binary tree every node has either zero children or two children. Okay, so you can see here A has two, B has two, but C has zero. So that's is that is called as a full binary tree. Okay.

[00:29:32]And then complete binary tree. So all level are completely filled. Expect possibly the last one. Okay. So all layer are completely filled. So you can say which is filled from left to right.

[00:29:45]So one is filled, two is filled, three but last one is not. But still we can say completely filled. So that is called as a completely filled. Perfect binary tree. Every internal node has two children and all leaves are the at the same level. Okay. So everyone is having a two children all same level. So that is called as a perfect binary tree.

[00:30:06]Okay. Skew tree only one child exist for every node that is called as a skew. So this is a left skew tree. This is a right skew tree. Is that okay guys?

[00:30:17]Types of tree.

[00:30:20]Hello everyone.

[00:30:24]types of binary tree.

[00:30:28]Okay, great. Now we'll talk about the BST. So obviously we'll go in more detail but still binary search tree follow these rules. So left sub tree contain smaller values. So this is first rule. Left side will contain the smaller values. Right sub tree will contain the larger value.

[00:31:11]Yes, guys. Am I audible to you all?

[00:31:15]Hello everyone. Can you hear me? Can you hear me? Please reply.

[00:31:23]Okay, great.

[00:31:26]Okay. So I was talking about the binary search tree over here guys. So binary search tree follow these rules. Left sub tree contain smaller value right sub tree contain larger value and both left and right sub tree are also binary search tree. Okay. So you can see here 50. So here 30 this left tree 20 smaller right 40 bigger. Similar way on this side 70 is bigger compared to the 30. Then all 60 smaller 80 larger. Is that okay guys?

[00:31:56]Binary search tree for everyone.

[00:32:00]Hello.

[00:32:06]Now we'll see that insertion.

[00:32:09]Obviously we'll discuss more detail about the binary search tree also. So we'll see this example. So you can see here we are creating a tree node in data node left right. Okay. And then we can create a constructor and pass the data to the current class variable. Then public class BST is there. So node insert. So node root and int value we are passing here. So if root is equal to null then directly return the new node value assigned to the root. If value is less than root dot data then root. We'll call the insert on the left side. If value is else means greater then we'll call on the right side. Can anyone tell me what what what concept is this calling function inside function?

[00:32:57]Calling function inside function what it is called as recursion. Very good guys. Very good.

[00:33:06]Okay. So this is how and at last it is going to return the root. Okay. So this is just for inserting that. Okay. So what I want you have to do this but this is not complete program. You have to write a main method for this. Can you do that? Can you try to do that guys?

[00:33:36]Hello.

[00:33:40]Okay. Please complete that and then share it in chat box if you please do it.

[00:36:49]See I want to create the BST. Now so for that insert method has created to insert it value at left or right okay node on right or left. So you have to complete that code using the main method is you just need to add the main method and create a note. Is that okay?

[00:37:13]Ratamesh, please do it.

[00:40:40]Nina, I'm expecting the main method from you. You have to write down the main method, call these methods, insert method, and complete the code.

[00:40:51]I'm expecting the code from you guys.

[00:40:57]Just complete the code and share it in chat Yes guys, please complete that code and share.

[00:42:53]Okay, you can do that later. No issue.

[00:42:55]Even though we'll also do it. Okay. So now let's go ahead. So we'll talk about the obviously we are going to in detail little more detail about this. So binary tree we'll talk first.

[00:43:10]So already we have discussed what is binary tree and all right.

[00:43:16]So there are two childrens are called left and right children. Okay. So nonlinear data structure each node can contain at most two children. Okay. So company hierarchy and all examples are there. We already discussed that. So we directly go for the uh code. Okay. So we are going to create here. We already created binary tree. Have we created a binary tree? I think yes. Right.

[00:43:45]Binary tree we created. Right guys?

[00:43:50]Hello. Are you there guys? Am I audible to you all?

[00:43:56]So full binary and all we have done right. Okay.

[00:44:01]Okay. So guys uh order traversal also we'll talk so in order listen in order first we'll visit a left root right so please remember this left root right okay and uh for code we'll see later on first try to understand pre-order so root left right okay so in order is a left root right LR pre-order is a ref uh root light uh root left right Okay, this sequence please remember or make a note post order left, right, then root. Okay, so we are going to see uh we'll see that bed first search and all. Okay, 1 minute.

[00:44:46]So we are going to see the binary tree example working example over here. Okay, let me explain this first so you guys will get a good idea about that. One minute. So with insertion and all we'll see.

[00:45:06]So program is going to be a bit lengy but I will explain each and everything.

[00:45:09]Okay. So we'll start from the main method. So in main method if you see we'll call the node. So we are creating a root node passing the value 10. Then on root. We'll call add the 20. Root dot uh root. We'll add the 30. Then again root. left dot left 40 root.

[00:45:29]50 then again root root.right dot left 60 root do.right write dot write 70 okay and then we are calling a method in order pre-order post order so we'll see how we have created all these method till here is it okay main method for everyone guys then I will explain the methods which we have created in order okay now guys see here first of all we'll create a node so I I think everyone familiar with this so in node we'll declare the three variable data left right okay and then we'll assign the data to the current class instance okay now we are going to create a First method called as in order. So can anyone tell me the sequence of in order?

[00:46:10]Sequence of in order left root right. Right. Okay. So you can see here we'll we'll create a function in order where we'll first check root equal equal to null. If it is null then return. There is no need to do the in order. So we then we'll call a in order and in that insert the root. And then we'll go for root element. And then we'll go for again in order call go for root do.right. So we are using a recursion. So every time it will call that in order. So left then root and then right. Is that okay guys? In order.

[00:46:49]Hello.

[00:46:52]Is that okay? This function in order for everyone.

[00:46:59]Please reply guys. Is this function okay for you all? Am I audible to you all?

[00:47:04]First of all, tell me am I audible to you all clearly?

[00:47:11]Okay, great. Now pre-order only sequence is going to change. So in if root equal equal to null then it will return or else first we'll go for root then left then right.

[00:47:23]Okay, it will call the pre-order one.

[00:47:25]Very simple. Post order also again we'll check root equal to equal to null and then post order left will go right will go and then root will go. Okay, this is how we are going to perform the tree traversal in order pre-order post order.

[00:47:41]So guys can you complete this? Can you practice this code everyone?

[00:47:46]Yes.

[00:47:48]Yes. Others can you practice this one?

[00:47:51]Please reply.

[00:47:55]Please practice this and then we will go ahead.

[00:52:46]Guys, if you are done with this, let me know. Then I will scroll. Just let me know in a message to scroll scroll up and down.

[01:05:39]Okay, I hope everyone does this. Great.

[01:05:42]Let's move ahead now.

[01:05:48]Okay, fine.

[01:05:51]Now guys we go for so tree travel cell we already discussed over here right okay 1 minute okay so uh three type are there pre-order uh in order post order that we have seen okay then breakfast okay it is also called as a level order visit node level by level. Okay. And the another depth first search imagine exploring the building instead of visiting every floor. Okay. So we'll see that. So your first explore one room completely then return. This is DFS. Okay. So we'll talk about DFS and BFS first. Wait a minute.

[01:06:38]In order to order already done.

[01:06:47]So you can see here breakfast search is also called as the level order traversal. Instead of going deep visit one level at a time. Okay. So we'll visit level one. So 10 then level two 20 30 then level three 40 50 60 70 like that. Okay. So we'll see the [clears throat] level order program first over here and then we will go ahead. Okay. Is that okay guys? Can we see the level order over here?

[01:07:26]So, oh, wait a minute.

[01:07:30]One minute.

[01:07:37]Wait. In order pre-order, we already done. Post order. Okay. So, in order pre-order, we already done. So we'll just uh use the uh pre-order post orderer part. Okay. So if you want you can skip or you can do that also. That's not a problem. Okay. It is up to you.

[01:08:06]So you can see here first we are creating a node. Okay. We are importing the java.util package for link list and Q. Then we are creating a node data left right then constructor pre-order already explained to you all guys right? Is there any need to explain now pre-order in order and post order guys please reply.

[01:08:26]Hello.

[01:08:31]Hello guys. Am I audible? Am I audible?

[01:08:34]Can you hear me? Can you hear me guys?

[01:08:37]Please reply.

[01:08:41]Not audible guys. Okay. Or no need to explain that.

[01:08:50]Okay. So you can see level order is there. So in level order what we are going to first if we'll check root equal to equal to null. So if it is null then we'll stop it there itself. But in case if it is not then we'll create a Q.

[01:09:03]We'll implement the link list. Okay. Q is a interface. Link list is a class. So we'll offer the Q dot offer root will offer and then while Q is empty means not mean if it is not empty we'll simply create a object uh node current and Q dotpool method will call. Do you remember guys what is the use of pull method?

[01:09:27]What is the use of pull method?

[01:09:32]Yes, everyone.

[01:09:34]What is the use of pool method?

[01:10:13]Okay, the pool method is used to remove and return the first element, right? So that's what we are doing and we are assigning to the current. So we then we'll print that current data. Okay, and then if current.left is not equal to null, then we'll say Q do.offer current.ft. Okay.

[01:10:34]If not equal to null and similar way if current dot write is not equal to null then go for right one. Current will be assigned to the right one. So we are going level by level. So first level will complete. So this will be complete.

[01:10:49]This will run till the time our Q is not empty. Okay. So like that. So then we will create a node object and then we'll add the element and call the method. Is it okay guys? Can you try this one also?

[01:11:04]I know that in order and all so just let me know to scroll down because you know you don't need a pre-order in order but please follow the sequence can you do this okay explain again sorry so you can see here in order post order we have done so level order we are just checking first if root equal to equal to null then it will return or else we'll create a link list okay in that we'll first offer the root and while Q is not empty till that time this loop is going so every time We are going to pull the element and put it to the current and then we'll print that current data and we'll check current do left not equal to null then inside of offer to the current to the left. If current dot write not equal to null then offer current to the right. Is that okay? Now hello everyone.

[01:11:52]Can you try this one? You already have half of the code. You can quickly complete that and then we will go ahead.

[01:11:58]So you just let me know while scrolling down. Just write a message. Scroll down.

[01:12:02]I'll I'll do that.

[01:26:54]Okay. 1 minute. Wait a minute guys.

[01:26:56]Others please wait. Let them complete.

[01:27:02]So once you are done let me know then I will scroll down. Okay.

[01:31:16]Yes guys, everyone here. Hello.

[01:31:24]Hello guys, please reply.

[01:31:30]Okay, I'll wait. No issue.

[01:35:51]Yes, guys. Dia.

[01:36:05]Okay, great guys.

[01:36:08]Uh, one minute.

[01:36:11]What is the Okay, we'll talk about binary search tree.

[01:36:27]Okay, so what is binary search tree? So, binary search tree is a special type of binary tree that follow the following rules. So, every node has the at most two childrens. All values left sub three are smaller. We already discussed but we are just discussing an all value right to sub tree.

[01:37:07]If word comes before it, search it on left or else search it on right.

[01:37:15]Is it okay guys? Binary search tree definition.

[01:37:20]Hello everyone.

[01:37:24]Okay fine.

[01:37:26]So we'll see the program for this also.

[01:37:28]We already discussed the rules.

[01:37:37]1 minute. So I told you to complete that program. So that complete program I'm going to show over here now.

[01:37:47]1 minute.

[01:37:51]Okay. So BST program I told you to complete but no one has shared that with me. So I'm going to do it over here and show you. I'll explain you.

[01:38:08]So guys you can observe here first of all we are going to create a node in that data left right and we'll pass the data to the current class variable okay then we are creating a insert function this function I initially also I explained you so static node insert we'll pass the node root and value so if root root is equal to equal to null we'll directly return the new node value if root if value is less than root dot data then it will go for left side. We call the insert. If it is greater than value then it will go on right side. Is that okay guys? This function I already explained to you all. Hello.

[01:38:45]Insert function for BST binary search tree. Okay. After that in order. So in in order the same code which we have discussed. So first left then root then right. Okay. And then we are going to discuss the search one. So if root equal to equal to null it will return false otherwise we'll check if root dot data is equal to key then return the root itself. If key is less than root dot data then it will go for left side key.

[01:39:14]Okay or else it will search on right side key. Okay. This is how we are going to search. If root key is less than root dot data then obviously lesser side lesser amounts are on left side and greater amount on right side. Is that okay guys? search search function.

[01:39:32]Hello.

[01:39:36]Yes, guys. Is that find the search function?

[01:39:48]Okay. After that guys, public main. So we are going to node node root null. We are assigning int values. we are assigning to that values and we are using a for loop so values into values and we are calling the insert method. So one by one we are inserting all these values. Okay. And then we'll call in order and then we'll print the search the 60 and 90.

[01:40:12]Is it okay guys? Main function also.

[01:40:16]Hello.

[01:40:19]Hello everyone. Please reply.

[01:40:24]Can you do this one? Please do this. If you have any question also feel free to ask.

[01:40:31]Great.

[01:42:26]Once you're done, let me know. Then guys, I will scroll down. Okay.

[01:49:44]Yes, guys, if you're done till here, let me know then I will scroll down. Okay.

[01:53:56]Yes, guys. Have you done till here?

[01:53:59]Can I scroll down?

[01:54:01]If you want, you can take a photos and you can try that after the session also.

[01:54:07]Can I scroll down, guys?

[01:54:13]Please take the photo of that and then you can complete that. Okay.

[01:54:56]Okay, great guys. If you have any question query, please feel free to ask.

[01:55:00]If not, let me know. Then we will wind up the session.

[01:55:04]Anyone? If any question query, please feel free to ask. Please practice the tree related question also. And if not, let me know. Then we will wind out the session.

[01:56:32]Yes guys if no more question please let me know then we will wind up the session.

[01:56:37]Hello those who are listening me.

[01:56:43]Okay amar I think there is no questions.

[01:56:56]Yes, summer. Can we wind up a session now?

[01:57:07]Hello Yes, guys. Can we wind up a session then?

[01:57:36]Hello.

[01:57:39]Okay, the Amar, are you there? Uh, >> yes sir.

[01:57:45]>> Okay. Thank you, Amar. Good night. Thank you. Good night, everyone.