Skip to main content
Loading Explore guides…
Introduction to trees · Acedra
Home
Explore
Computer Science
Introduction to trees
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
61 segments
Copy
Hide video
0:00
Hello ji, how are you all This is love babbar ,welcome to codehelp we reached at lecture number 62 Earlier we did queues and many questions on queues And we have come to our new data structure which is tree What is tree? we are going to learn this first This is a very easy thing we will learn it in no time We will go step by step and then we will talk about binay tree And we will create binary tree and implement And then we will traverse it with different types like inorder traversal
0:40
Preorder traversal, postorder traversal Level order traversal, reverse level order traversal And also how you can create treeby level order traversal And some extra questions So inshort you will learn how to plat with tree after watching this video That how we create and traverse tree And the next video will be dedicated for question solving so basically a tree is like your family tree So like this is your grandfather,then your father and then your this is your uncle
1:15
After your father you will be thereand there could be any daughter of you father We named her as Pinki There could be any son and daughter of your uncle So basically a family is running It got started from here and we are coming down like this You got a rough idea about how a tree could be When we talk about programming we got to know what is tree Tree is a type of non linear data structure And in this node can be connected with multiple nodes
2:04
As when we talk about linked list, it is a linear data structure In which one node is connected with another node in this way And in tree i said one node can connect with multiple nodes In this way tree is a non linear data structurewhich holds information As we go ahead we come to know all other terms like root, parent, child, sibling Ancestor, descendent all the things we will learn As we talk about basic terminologies before talking about tree If this a tree and this is a root node
2:46
I will tell about all these shortly, and these are two nodes And again there are two nodes and here is one node Lets say this is a tree So quickly one by one i am writing all the terms here And we will understand it one by one separately Firstly node then root third one is child and then parent fifth one is siblings Ancestors this are the terms we will use while working with tree So we should have some knowledge about them Like leaf node, so this are the terms we are going to talk about
3:32
As we go forward we will solve questions too and know the terms Before talking about them, lets give shoutout to out sponsors and then continue What are coding ninjas? It is the largest coding education platform in which you can check many cources If you are interested in paid courses like development, machine learning, web development, core subjects , dsa In java, python or any language then you can get this cources feom here
3:59
The best thing that one on one doubt resolving support is available here If you have any type of doubt then it will we resolved in 1to2 hours Courses are very much well structured that you get compulsory results Course creators already cracked into many big companies Courses are available in both Hindi and English language At the time of question solving you get hint videos So you are wise enough, if you are wanted to buy any paid course
4:25
Link is in the description by which you will get 20% discount which is maximum go check it out.. Ok , lets talk about first term which is node Each element of this tree in which data is saved Blue print of node is it stores some data in it Lets say we are storing integer like here is 9and hre 3, 7, 11 here 9 and hrere 4then 7 there It storing integer here, In this case i have given you a n example of binary tree What is binary tree? In binary tree there could be only <=2 nodes
5:17
What is child? A node is basically denotes a element, we will come to it later Now what is root? The top node from which the tree starts is called root node, in this case this top one Now about children, here this 9 is children of 3, you got that So by common sense 3 is parent of 9 Similarly 4 is also child of 3,so is parent for both of them So the nodes above are parent and which are below then are children of that Like that this is a parent of the below node
6:00
So you got the child- parent relationship here Sibling are those nodes whose parents are same So here for both 9 and 4 parent is 3, so 9 and 4 are siblings Ancestor are those nodes which linked above a particular node Similarly if you come below the linked nodes are desendent of a particular node What is leaf? In short those nodes which have no children are known as leaf node Here there is no child for 4,so 4 is a leaf node and for 9 also there is no child
6:50
So 9 is a leaf node similarly below 7 is also a leaf node Above 7 is not a leaf node because it have child Talking about 3 that is not a leaf node For 1 node it is having this two children so it is not a leaf node Coming back, I said you that in binary tree every node have <= 2 child That means there should be 0 child or 1 child or 2 child Lets say there is 2 child so this is a example of binary tree Look carefully, firstly inside a node there is a data and two pointer is there
7:34
Which points the left child, and another which points which points the right child And here your node ends. Again if we have any tree, that starts from root node And every node have 3 things its data, left pointer and its right pointer Now there could be a node or there could null too, got it Now if any one ask us what is tree, we say tree is a non linear data structure In which the format of node is like we store a data in it, and if it is a binary tree then it will have two child
8:16
If there is multiple child, we call it as n-array tree In that the structure of node is like it will have a data part and and it will have multiple child So I stored all the child in a list of type node*and name it as child So we have created a tree consisting of multiple child of no limit Getting the logic is important, that if anyone asks me, what is tree? So I should say that it is a non linear data structure and structure of node could be like this
8:59
If it is allowed multiple children of nodes or if it is a binary tree then there could be maximum 2 children for each nodes What is node? A element of tree is called node and top node is root Child is simply the below node of any node which is linked with it The above node is parent of that, sibling are those whose parents are same This two have same parent 3 so they are sibling Ancestor is the linked above nodes and the opposite above to below nodes are known as decendents
9:41
And leaf are those which does not have any child, got it So this concepts should be cleared to you, these are theories Lets discuss quickly about creation, first problem I want to do is creation (build) of binary tree I want to build the binary tree So you will say firstly create the node, so I m creating class for node class node It should consist three things one is data public int data And one left, one right got it Now I want to make a function (constructor) in which there is data
10:47
Data of this =d , left of this= NULL, take starting point NULL And right of this =NULL, you did this So whenever you are creating a new node, then the new node will create like this The dat will be stored and it will be pointing NULL and this will also pointing NULL Now I want to create a function by which I can build this tree So I created a function whose name is node* buildTree In this function I have to write logic so that I can create tree So our tree is like this, let draw a new clear one
11:46
Having data , at root node 1, This is its left child which i s3 , in right child 5 is there Inside the left child of 3 there is 7 and in right child there id 11 Inside 5's left child there is 11 and in right there is NULL If there is nothing then take it as null so this also points to null at left and right as there is nothing below them So what we have to do is we have to create(build) this tree So I am creating a root that is node*root=NULL
12:34
Now I call function root= buildtree(), so I have created tree here Now we should understand the logic in buildtree So i have to build this tree, so I have to pass data basically this 1,3,5... So how I going to solve this I will create this in recursive way So as I go to the function I need the data for the root node cout<<"Enter the data"<< endl; So I created int data variable and take input as cin>>data; And I created node Root =new Node(data), in which you have passed the data
13:48
So it call the constructor and it will initialize it So you have created a root node in which you have stored the input data If your data=-1, then so your data= NULL If data ==-1 , then I will return NULL Now I want to store something in the left of null, remember recursion you have to solve for one and for remaining it will take care cout<<"Enter data for inserting in left <,endl; Now I will call for the left of the root ,recursion will take care Root-->= build Tree(root-->left);
14:57
When I return then cout<<"enter data for inserting in left<,endl; Root-->right=buildTree(root-->right); So you have created you tree with the help of recursion and then you did return root; finished Now if I carefully try to run my code then check what happens It says Enter data so in starting I have to give1 Now Enter data for left of 1,what you want to store in left of 1 we want 3 We write 3, it say what you want to insert in left of 3,we want 7
15:47
It say what you want to insert in left of 7 ,we want Null so we have to give -1 Enter data for inserting data in right of 7, we want again -1 It say what you want to insert in right of 3, we have 11 It asks for the left of 11 we insert -1, it asks about right of it we insert -1 Again it asks for right of 11 we insert Left of 5 we insert 17 Nothing is there in left and right of 17 so there should be -1 on both For right of 5 there is null so we insert -1
16:21
So this way I have created the full tree , if you got the logic Traversal is going like this, you first come to here Then recursive call brings you here Then it bring you here Then it bring you here Then you return here, then you go there Then you go there and go there Then you go there, then you return here Then you go there, then you return here Again you return back there, again return back Then you come here, you go left and again left And you return back and go right and again back
17:02
Again back and go right and back and back again and go out So this way your recursive call are running, if you look carefully Firstly you are inserting something in root node which comes from the input Again you insert something in left and you then call for the right So how recursion is working, I start from this node Then go left and left and follows and when it ends then I return from there Go to the right it ends I return from there Again return back, go to right go to left and return again
17:35
Go to the right return from there and return ,return again Go to right, go to left again left and return Go to right, return, return and go to right and return and return again and out of the tree So first call is for left and second is for right, simple logic and we created it Now I want to do it in a different way So we going to learn about a new concept, which is level order traversal We sent the root, this is our new function
18:16
Basically when you create a tree,like for this tree this is your level 0 This is your level 1and this is your level 2 and this is level 3 Everything is null in that, nothing we will do with with that Firstly we will print all the nodes in level 1 Then we print all the nodes in level 2 and then for level 3 we go like this till we get all null In short our answer will be firstly, 1 will be printed then 3 and 5 And then 7,11,17 will be printed, so we will get an idea that tree is like that
19:00
So we are learning bout level order traversal, so how we are going to solve this If I use a queue then thins will become more easier for me Lets say i have created a queue, whenever you going to solve this type if level order traversal Mainly you are going to solve it by using queue , queue<node*> q; So I have created queue, now I have to include it also
19:48
Now I am inserting a element the root element in the queue So you pushed root in the queue Now present till q got empty, while(!q.empty()) So now you create, node* temp= q.front(); q.pop(); if (temp --> left) q.push( temp -->left), that means you inserted the left child And same thing you did with the right child This way you written the function and you are doing cout<,temp--> data There is many improvements in it, we will do it And we run this level order traversal, this type
21:19
Now I am saving it as I do not have to write the data again and again..1, 3,7,-1,-1,11,-1,-1,5,17,-1,-1,-1 So I have to insert this string in the input to get this tree Now we are running this, I inserted the string and and tree got created Now look carefully your answer has came If I write cout then we get it clearly And again I am running it, so you got level order traversal output as1 2 5 7 11 17 But I want in this format,and i has created in a single line so i connot understand the levels
22:28
It should be clear that this is level 1 and that is level 2 and so on So for that I have to use a separator that will indicate that now level 0 has completed Now level 1 has been completed , Now I know after root level 0 is completed As root node is the single node in the level 0 So we have to insert a separator as one level got completed for that I write q.push(NULL) Main thing is when you press enter, you get the answer when you press enter
23:21
We have the problems of enter , so you press enter here and here and you problem will be solved So you will get enter by the use of separator ,now if(temp= NULL) If temp gets null that means the previous level get completed traversed That simply means I have entered all child in queue, enter the first enter And check the simple thing, if(!q.empty()), that means q still has some child nodes Then q.push(NULL), so this is the logic
24:41
In which if is there then previous level got traversed we did endl And also checked if q is not empty , means some node is there Means it needs another separator, we entered another one Now coming to else condition, we have pushed this logic in it Now when we running it ,we copy the input and cleared that And pasted it, now if I print it, it seems some problem here Checking from start, pushing root then pushing null
25:40
Ok we have to change this, it is possible that you do not take the front element So when you are going to input in null segment error will come I am printing it here I will print it when temp is not null Simply i will print it in here, now if I run this it should run now And I pasted the input, look carefully we got the desired output here So we have solved the problem, which is output is coming like this in single line
26:21
I want enter after 1 and enter after 3 and 5, using a separator after each level As a separator I pushed null in that and when it finds null in front the press enter In short I draw the tree and first push 1 And level ended then i pushed null There after when the while loop started it got 1 in front that is non null Then you come to else condition, you print 1 Then you entered left and right 1, so 1 entered 3 and 5
27:39
Up to her 1 is printed in the output, next element is null and we come to the next line And you removed that , if it is not empty you entered another separator Now 3 got printed by the else condition and you pushed left and right element of 3 which are 7 and 11 Now you pushed the elements for 5 which is 17 only And you press enter and checked is q is empty it is not then put another null Again 7 got printed like 11 got printed, both have no child so there nothing gone in the q
28:49
Now you printed 17 and it also have no child then you go to null and you have enter again And you checked if q is empty, q is empty so you have nothing to do This way you got this output, and you did dry run too that how level order traversal works Now you got how we can create a binary tree, traverse it in a level order way You take a homework quickly, What is reverse level order traversal learn it , and code it yourself If you got the previous code , then you can do it also
29:52
Now will now discuss about three new traversal Inorder traversal, Preorder traversal and post order traversal Lets say I have a tree The structure is like that It having data lets say 1 3 5 7 11 17 and this is null This is your root node So if you understand traversal then you can solve majority questions of tree How recursion takes place in tree if you get this then 99 percent question you can do it easily Some does not read tree how easy is that
31:13
I will give you a code in inorder that you have to keep in mind L N R is for inorder , NLR for preorder and LRN for postorder That means in case of inorder first I print left node then I print the middle node and then the right one For preorder first I print middle node then I print the left node and then the right one For post order first I print left node then I print the right node and then the middle one Now I am going to write the code For inorder traversal, I start first with root node
32:00
Then I go to the left, again I have LNR so I go to left Again I have LNR I go to left there is null is says come to node Print the node by LNR we go to right so we have to return We have to return to N again you go to right null is there you returned To 11 you printed that, again null is there you returned and returned to the root node It becomes N now you go to right and printed 1,and went to right And LNR comes and you went to left and again you went to left
32:59
By returning you come to N and went to right and returned Again you come to N and print 5 And you went to right there is null you returned Simply your answer will come 7 3 11 1 17 5 This way you did inorder traversal Again if I draw the tree here If I say about preorder traversal, it means NLR So you start from the middle node and printed1 Then went to left then it becomes N and you printed 3
34:00
Then you went to left then it becomes NLR then printed 7 and you went to left there is null you returned Went to right there is null you returned, and returned back again Then you went to R then 11 becomes N and you printed that went to left there is null you returned, went to right there is null you returned Then returned from here and again returned to root node Now you go to right then there is NLR you are on N so you print 5 and then Then you go there then that is N print 17
34:38
Went to left there is null you returned, went to right there is null you returned again you returned went to left right there is null you returned and finally returned to the root node So preorder traversal is like this and your output will be 1 2 7 11 5 17 I am talking about the flow , L->go to left part R-> go to left part And N means simply print When I came to 1it said L means go to left I came to 3 again it said go to left When I went to 7 it said LNR I went L I returned from left
35:28
I reached at N and printed 7, then it said R there is null so I returned This way when I return to 3 I print 3 then I went to R There is LNR I went to its left and returned and printed 11 and went to its right and returned And finally returned root node , now root becomes the N so printed it Then went to R then comes LNR, went to left and comes again LNR I went to its left and returned Now N is 17 so printed it then I went to its right and returned
36:02
And returned from there left was done so N becomes 5 so printed it, then went to its right and there is null so returned Now we will do postorder and you will get it more clearly Again we will draw the tree In postorder traversal there is LRN means first go to left then right and then print So i started from this node LRN so first go to left So I came to left there become LRN Again I came to left again there is LRN I went to its left and returned, I went to its right and returned
37:09
Then 7 will be the N so I printed 7, now when I returned from there we have go to R So went to right, I went to its left and returned and I went to its right and returned Now 11 become N and printed it Then from there I returned from there and came to N and printed 3 And returned to the root node it becomes n so printed it Again from there we went to R there it said LRN so I went to its left Again it is LRN I went to its left and returned I went to its right and returned
37:47
Again 17 will be N so printed it and when we returned from there and I went to its right and returned Then 5 becomes N so printed it and returned from there to the root node and printed1 So the output will be 7 11 3 17 5 1 Lets try to print , you will get it So i write a function of inorder in which we pass a root ,and I will do recursion And do it by this codes only ,LNR means go to left print the node and come to right First base case if(root == NULL) and return
38:38
Now for L(left call) indrder(root -->left) now print the node then inorder (root-->right ) So thats the code L N R Lets try to print and run Clear it copy the input and run it and the output is 7 3 11 1 17 5 Lets see right or not , yes it is right Lets try for pre order ,NLR means first print then call left and then right Ok code is done lets run it , coping it Something went wrong its not matching Ok we have called inorder in preorder we have change this
40:32
Now it run correctly , clearing it and running so the answer is 1 3 7 11 5 17 So preorder is running correctly This way I will write for postorder too , the code for post order is LRN means first call left then right and then print So code is done , first called left then right and then printed Now quickly run it Clearing it and coping the input and running it so the answer is coming 7 11 3 17 5 1 Comparing it , and it is running correctly
41:41
So we know 4 types of traversal till now in tree ,you should practice and see how traversals are going in tree We learnt LOT, IOT, Pre O, Pos O If any one asks you what is LRN LNR NLR simply L means go to left R means go to right N means print the current node Lets try with an example, lets say if your tree is of these type I want to do it with inorder traversal means LNR I start from here by LNR we go left, then again by LNR we go with left
43:08
Again with LNR we go left again with LNR went to left and returned When I returned there will be N so I printed 6then I said go to R there is null I returned back When I returned from there it said the node is N so I printed 3 Now went to R then it said LNR means go to left and returned and the node will be N so printed it It sais go to R I went and returned back and again returned and came to 2 and printed it as it is N
43:44
Now for R going to right there LNR I went to left and returned back to N and printed 4 Again it said do R went to right and returned back Again coming to root node that is now N so printed 1 then it said go for R There is null so returned back and went out of tree So output of inorder traversal for this particular tree is like this Now you know inorder preorder and postorder traversal by recursion
44:30
Now your homework is you have to solve this three traversal with the help of iteration without using recursion so build we learnt using recursion , if I say build from level order If you have given level order in input like this , by this you have to build a tree So solving it , so I write a function node*buildfromlevelorder we inserted node *root , so level order means queue So we create a queue of node* type and we do not need any separator here q.push (root);
45:53
now we do while (!q. empty ()) first we create node*temp = q.front Now cout enter the data for root and then we create a variable and take input And I write root =new node and passed the data and I pushed it Now we do q.pop() now I write enter left node for and I printed data of root I say for this data assign the left node Ok I got that If you have taken -1 which means null then i will write If (leftdata != -1 )then I will insert a node at left of temp
47:35
Which will have the data of leftdata and pushed it in q Same thing we will do for the right child , we modify the codes for the right child So you create a root node then extracting it from front you insert the left and right node and your wok is done I do not want to return in this function and I will take reference as root node I write void in front of the function Now I commenting out this part and simply call that function
48:48
Buildfromlevelorder and passed root in that, and lets clear and run it It says enter data for root node, now the data for root node is 1 It says enter data for left node of root which is 3 It says enter data for right node of root which is 5 We have did some mistake here as it says again enter the left data of 1 Ok the data is not for root it is for temp Lets again run this Now after this it asks for left of 3 which is 7, I insert that Now it asks for right of 3 which is 11, I insert that
49:39
Now it asks for left of 5 which is 17, I insert that Now it asks for right of 5 which is -1, I insert that Now it asks for left of 7 which is -1, I insert that Now it asks for right of 7 which is -1, I insert that For 11 it is -1 ,-1 and for 17 also -1 ,-1 This is how we created a tree with level order traversal How you check that just print that Levelordertraversal(root) again I will not write it I will write it from the input
50:29
Lets clear and run it so got the desired output , so you learnt how to build a tree By two ways, by level order traversal and by simple recursion also ,you goy this Now try one two questions then you will more clarity So we have this question in front of us It says you have a tree like this and you have to count the leaf nodes in that So you have to count that nodes which have no child In this example 5 13 30 42 are leaf nodes so total 4 leaf nodes are there
51:25
Because these nodes have no child Lets code it quickly int cnt = 0 , what I want to do is I will traverse the whole tree And where I get leaf node I will increment the count , basically those nodes which have no right and left child is a leaf node So cnt will be incremented in node 5, 13, 30, 42so our answer will come as 4 There are 4 ways to traverse, lets say I copy the inorder one and paste it here nad try to solve it by it First replace this and pass the cnt here
52:26
I am passing it by reference I dont want to print I want to check a condition that is of leaf node , that is if your root --> left got null as well as root-->right got null Then you are an the leaf node and we have to increment the count, simple I call the function inorder passed the root and passed cnt and returned the answer Lets run this, got the correct answer lets submit it And we get correct answer in this case
53:27
We it was a basic question ,when you traversing in the whole tree your time complexity will be O(n) And n is the number of nodes present in the tree , the logic for traversing the tree written here You are checking that current node is a leaf node or not if it is then increment count And you have saved its address as you are taking it as reference and answer you have returned This way you solved a question So thats it for this video, I want to show you how you can create a tree by two ways
54:07
One how to do it by recursion and one by toe concept of level order traversing 4 traversal methods you have learnt level order, inorder ,preorder , postorder One question you did to get some idea how to tackle with tree questions For homework you have to do reverse level order traversal and iterative version of inorder preorder and postorder Thats it for this video we will meet in the next video Tell me in comments what you feel about this video
54:49
Now its 3:36 AM in the morning, it take hardwork it does not come like that And I do not expect that 1% student watch upto here Those who are watching are doing hardwork and who are creating doing hardwork Thats it for this video we will meet in the next video , Bye Bye!!
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat