Binary Tree Introduction: Types, Terms & Fundamentals

so before starting the video i'd love to thank relevel for sponsoring this entire tree series so if you're tired of

waiting for companies to respond to your applications through different job portals the next few seconds are very

very important for you because reliable by an academy is india's first hiring platform that can get you a job within a

week itself yes all you have to do is to register for the relevant test and within a week your interview will be

scheduled with india's top companies and the top budding unicorns so what are you waiting for

make sure you check out the links in the description and apply for the relevant test because it is free

hey everyone welcome to the first lecture of the free cut tv series so today's lecture will be about

introduction to binary trees now what is binary tree so as of now you would be knowing arrays

stacks queues linked list those are linear data structure whenever i talk about trees they are hierarchical data

structures they follow in hierarchy now what is in hierarchy if you have seen in computers you have folders right let's

say this is the initial folder that you have and inside that you have one more folder inside that you might have one

more folder inside that you might have one more folder inside that another folder or these kind of things can be

represented using trees whenever i associate a term binary

that's basically zero and one so a binary tree basically says inside a guy that can be at facts two

guys okay at max two guys so at max like over here there are two guys over here there's only one over here there's one

over here there's one over there here there's no so whenever i say that in an hierarchy

structure i can have at max 2 guys that is when i can call it as a binary trees okay so that's the simple

definition of a binaries now why is binary important because there are a lot of questions related to binary trees

that are asked in interviews yes a lot of times you will find a question related to binary so that is why we will

be having this entire series on binary trees so before moving on uh

let's discuss about some terms whichever is the head or starting whatever you can call it that that is known as the root

of the tree root the starting point and if this is the node and it has couple of guys

these guys are called the children yes these guys um this is the children this is the children okay uh for example this

guy is the children of this guy this guy is a children of this guy okay i hope you understood the children concept if

there's one guy beneath it beneath it whatever we have those are children's cool

now there's one more concept leaf this is known as the leaf node what's the leaf node a node which does

not have children's okay that's known as the leaf notes there's another concept as sub tree now let's assume you're

standing here okay and this entire portion okay this entire portion will be the sub tree this

portion will be the sub tree for this node cool let's say you're standing here this entire portion will be the sub tree

let's say standing here this entire portion will be the sub tree let's say standing here this entire portion will

be the sub tree okay the node and the beneath guys beneath guys are the subtree of a node now there's one

more concept which is known as ancestors what does ancestors

so if you stand over here for this guy this is the parent this is the grandparent this is the grand

grandparent this is the grand grandparent so basically all the grand grand grand grand whatever parents you

have these guys are called ancestors for this guy this this is an ancestor this is an ancestor this is an ancestor this

is an ancestor okay for this guy only this guy is an ancestor for this guy this and this is an ancestor for this

guy this this this is an ancestor so i hope you have understood the concept of ancestors root children leaf node now

there is something there are a couple of other terms but that are not important uh you will you're just requiring these

terms in order to understand the tree series so now let's talk about the types of binary trees so one two three four

five there are five types of binary trees and the first one is full binary tree what is the full binary tree

every node will either have zero or two children now for an example i can say this

is a full binary tree because this node has two children this node has zero children this node

has two children this node has zero children this node has zero children i can say this

also has a full binary because this node has two children this node has two children this node has two children this

node has zero this node has zero this node has zero this node has zero so this can also be called as a full binary

trees whereas you cannot call something uh like this

as a full binary tree why because this guy has two children but this guy only has a single children so it either can

have zero or eight either can have a couple of children's okay i hope you've understood full binary tree

now let's talk about complete barrier trees now the next type is complete barrier trees it states all levels are

completely filled all levels should be completely filled except the last level okay and the last

level has all the nodes as left as possible so if i draw one of the binary trees

i can say that this is a complete binary trees because if you check the levels this is what you

call levels okay level zero or one level one or two level like one two three you can call it if you refer it as one based

indexing this level has all the notes this level has all the roots this level has all the nodes so all levels are

completely filled again i can call this as i can call this as a complete manner

tree this level is filled this level is filled this level has this guys missing this level has

these guys missing but again that's allowed if you carefully read it it says accept the last level the last level

cannot have everything filled now can you have something like this no

because it clearly states the last level has all nodes in left this is on right

so this is not possible whereas this is possible the last level is not completely filled

but the guy is as left as possible okay so this is again a complete binary tree so just need to make sure all the levels

are filled and the last level if not completely filled everything should be on the left every understood complete

binary tree the next type of binary is a perfect binary tree basically states all leaf nodes are at the same level so this

is a perfect binary tree because you can see these are the leaf nodes and all of them are at the same

level again this is not a perfect binary tree because this is a leaf node this is a leaf node and this is the leaf node so

they're not at the same level it has to be on the same level like this is a binary because they are at the same

level so that's the definition of perfect binary tree now the next one is a balanced binary it states height can

be at a maximum of log n when log n n is number of nodes for an example if i give you n equal to let's say 8 okay so

log base 2 n is around

3 so you cannot have a greater height than 3 that means you cannot have a tree like this at maximum the height of

the tree should be 3 like the height

and this is generally done to efficiently search or inc like improve the time complexity uh we will be doing

the other variant of binary trees that is binary search trees where we will be understanding this that's why i'm not

going deep into balance binaries as of now what's the next one degenerate trees what is the degenerate

tree whenever it's a skew tree for example if n is four this is something like this

degenerate skew trees if it is going like this it's essentially a linked list only right whether that's straight line

so that's the definition of linked list whenever every node every node has a single

children that's the definition of degenerate trees so i hope you've understood the terms related to binary

trees and the types of binary trees in this video so i hope you've understood the entire explanation as well as the

code just in case you did please please please make sure you like this video because it took a lot of efforts to make

this entire tree series also if you wish you can definitely drop in a comment that will keep motivating me to make

such further series also if you're new to the channel please do consider subscribing because i'm going to bring

in such more cds in the upcoming future as well with this uh let's wrap up this video let's read in the next lecture bye

bye [Music]