In our previous lesson, we wrote some code
for binary search tree we wrote functions to insert and search
data in BST .Now in this lesson we will go a
little deeper and try to understand how things move in
various sections of applications memory. When these functions get executed and
this will give you a lot of clarity and this will give you some general insight
into how memory is managed for execution of a
program and how recursion which is so
frequently used in case of trees works. The concepts that I’m going to
talk about in this lesson have been discussed earlier in some of
our previous lessons, but it will be good to go through these
concepts again when we are implementing trees. So, here’s
the code that he had written. We have this function GetNewNode() to
create a new node in dynamic memory and then we have this function Insert() to insert a new node in
the tree and then we have this function to search
some data in the tree and finally this is the main function. You can check the description of this
video for link to the source code. Now in main function here we have this
pointer to BSTnode named root to store the address of the
root note of my tree and am initially setting it as NULL to create an empty tree and then I’m making
some calls to insert function to insert some data in the tree and
finally I’m asking user to input a number and I’m making call to
search function to find this number in the tree if the
search function is returning me true I’m printing found, else I’am printing not found. Let’s see
what will happen in memory when this program will execute. The
memory that is allocated to a program or application for its execution in a
typical architecture can be divided into these four segments, there is one segment called text segment to store all the instructions in the
program. The instructions would be compiled instructions in machine language. There is another segment to store all the
global variables. A variable that is declared outside all
the functions is called global variable. It is accessible to all
the functions. The next segment stack is basically
scratch space for function call execution, all the
local variables the variables that are declared within
functions live in stack. and finally the fourth section heap
which we also called the free store, is the dynamic memory that can grow
or shrink as per our need. the size of all other segments is fixed
the size of all other segments is decided at compile-time but heap
can grow during runtime and we cannot control allocation or
de-allocation of memory in any other segment during runtime but we can control allocation and de-allocation
in heap we have discussed all of this in detail
in our lesson on dynamic memory allocation you can check the description for a link.
Now what I’m going to do here is am going to draw stack and heap sections as these two
rectangular containers. I’m kind of zooming into these two
sections. Now I will show you how things will move in these two sections of
application’s memory when this program will execute. When this
program will start execution first the main function will be called.
Now whenever a function is called some amount of memory from the stack is
allocated for its execution. The allocated memory is called stack
frame of the function call. All the local variables and the state of
execution of the function call would be stored in the stack frame of
the function call. In the main function we have this local
variable root which is pointer to BSTnode so I’m showing root here in this stack frame.
We will execute instructions sequentially. In the first line in main function, we
have declared root and we are initializing it and setting it
as NULL. NULL is only a map macro for
address Zero. So here in in this figure am setting
address in root as 0. Now in the next line we are making a call
to insert function so what will happen is execution of main
will pause at this stage and a new stack frame will
be allocated for execution of insert.
Main will wait for this insert above to finish and return. Once this insert call finishes, main
will resume at line 2. We have these two local variables root
and data in insert function, in which we are
collecting the arguments. Now for this call to insert function, we will
go inside the first if condition here because root is NULL, at this line we will make call to GetNewNode
function so once again execution of this insert call will pause and a new stack frame will be
allocated for execution of GetNewNode function we have two local
variables in GetNewNode data in which we are collecting argument and this
pointer to BSTnode named newnode. Now in this function we are using
new operator to create a BSTnode in heap. Now let’s
say we got a new node at address 200
new operator will return us this address 200 so this address will be set
here in new node so we have this link here and now using this pointer newNode, we are setting value in these three
fields of Node. Let’s say the first field to store data
so we are setting value 15 here and let’s say this
second cell is to store address of left child this is being set as NULL and address of
right child is also being set as NULL and now GetNewNode() will return the
address of new node and finish its execution. Whenever a
function call finishes, the stack frame allocated to it is reclaimed. Call to insert function will resume at
this line and the return of GetNewNode() address 200, will be set in this the root which is local variable for
insert call and now insert function, this particular
call to insert function return the address of root.The address stored in this variable root which is
200 now and finish and now main will resume
at this line and root of main will be set as
200. The return of this insert call, insert(root, 15) will be set here. Now in the execution of main, control will go to the
next line and we have this call to insert function to insert number 10. Once again
execution of main will be paused and a stack frame will be allocated for
execution of insert. Now this time for insert call root
is not NULL. So we will not go inside to first if,
now we will access the data field of this node at address 200 by using this pointer named root in insert function and we
will compare it with this value 10. 10 is lesser than 15 so we will go to
this line and now we’re making a recursive call
here because recursion is a function calling itself. and a function calling itself is not any
different from a function A calling another function B
so what will happen here is that execution of this particular
insert call will be paused and a new stack frame
will be allocated for the execution of this another insert call to which the
arguments passed are address 0, in this local variable
root, left child of Node at address 200 is NULL. so we are passing 0 and root and in data
we are passing 10. Now for this particular insert call
control will go inside first if and we will make a
call to get new node function at this line so execution of this
insert will pause and we’ll go to GetNewNode()
function here, we are creating a new node in heap. Let’s say we got this new node at address 150.
Now GetNewNode() will return 150 and finish execution of this call
to insert will resume at this line, return of GetNewNode() will be set here and now this call to insert will return address
150 and finish. insert below will resume at
this line and now in this insert call left child of this node at address 200 will
be set as return of the previous insert call
which is 150 so.. now these two node are linked and finally
this insert call will finish. Control will return back to main at
this line, root will be rewritten as 200 but earlier also it is
was 200, it’s not changing. Next in the main function may have
caused to insert number 20. I’m not going to show the
simulation for this one once again allocated memory in stack
will grow and shrink and finally when the
control will return back to main function after this insert call is over, we’ll
have a node in heap with value 20 set as right child of
this node at 200. Let’s say we got this
new node with value 20 at address 300 so as you
can see the address of right child in node at address 200 is set as 300. Now next one is to insert number 25 this one is interesting let’s see what
will happen for this one. Main will be paused and we will go to this call to insert, in the root which is
local to this call address passed is 200 and we have passed number 25 In data.Now here 25 is greater than the value in this node
at address 200 so we will go inside this last else condition we need to insert in the right subtree so another card insert will be made we
will pass address 300 as root and data passed will be 25
only. Now for this call once again the value in node at 300 for this call which is 300 is lesser than 25. 25 is greater than 20 so once again we will come to this last
else and make a recursive call to insert in
the right subtree the right subtree is empty this time so
for this insert call at top the address in root here will be 0 so for this call we will go to the first if and make a call to GetNewNode(). Let’s
say this new node returns us node at address 100. I’m short of space so I’m not showing
everything in GetNewNode() stack frame here. we will return back
to this insert call at top and now this root is set as 100 address of the newly created node and
now this call to insert will finish. We will come back to this insert below
and this insert will resume at this line
inside the last else and the right child of node address
300 will be set as 100, and now this insert will return back to
address 300, whatever is set in it’s root and this insert below will resume at this
line inside the last else right child of node at address 200 will
be set as 300. It was 300 previously also so even after overwriting we will not
change and this insert will finish now. Finally main will resume at this line,
root of main will be set as return of this insert
call. It will only be overwritten with same
value. It’s really important that this root in main and other links in
nodes not properly updated quite often because
of bugs in our code, will loose some links or some unwanted
links are created. Now as you can see, we are creating all the
notes in heap here. heap gives us this flexibility that we
can decide the creation of node during runtime and we can control
the lifetime of anything in heap any memory claimed in heap has to be
explicitly de-allocated using free in C or delete operator in C++ else the memory in heap remains allocated
till the program is running. The memory in stack as you can see gets
De-allocated when function call finishes. The rest of the function calls here in
Main function will execute in similar manner I’ll leave it for you to see and think
about. Right now we have this tree in the heap, logically memory itself is a linear
structure and this is how tree which is a
non-linear structure which is logically a non-linear
structure will fit in it. The way I’m showing the nodes at random
locations linked to each other in this heap. I hope this explanation
gave you some clarity. In coming lessons we will solve some
problems on trees. This is it for this lesson thanks for
watching.


76 Comments

Nitin Kapoor · February 11, 2014 at 1:25 pm

thanks @mycodeschool 

yashaswi ponnur · February 13, 2014 at 4:33 am

i am thanking u making data structure easy…

minal agarwal · February 20, 2014 at 11:52 pm

Can you provide the iterative implementation of this insert function?

Sandeep Kumar · March 2, 2014 at 6:27 am

thanks… to show bst implementation with the help of stack and heap.really it is  easy to understand .thanks once again..

Vandana Singh · May 2, 2014 at 12:33 am

great videos..thanx a lot 🙂

Balakrishnan B · November 1, 2014 at 1:51 am

Please don't use raw new in c++. You should be using std:: unique_ptr. Better change the tutorial to C syntax.

praslisa · November 10, 2014 at 1:22 am

the best recursion and tree explanation !!! thank you 🙂

Sudharsan Chakravarthi · November 24, 2014 at 9:44 pm

Very nice explanation on Binary Tree . I liked all your videos on data structures. You made my learning very easy. It moved my understanding to the next level. Thank You very much.

Balan Bogdan · January 14, 2015 at 7:54 pm

Hello. I made the code run for a huge number of variables and I got a crash "Stack overflowing". I made a nonrecursive version of the Tree and the Stack doesnt crash anymore but I wonder if I should change the parameters of my programs to use additional memory for stack or should I use the nonrecursive method for big depth ?

Al Maruf · April 26, 2015 at 4:11 pm

Awesome!! Very nice video. Thanks 🙂

Moping Dou · April 30, 2015 at 3:06 am

This video is great! It helped me realized the bug I was trying to find about dangling pointer you mentioned and improved my understanding of binary search tree! Thank you so much!

Sidath Gajanayaka · May 21, 2015 at 6:46 pm

Superb lectures! Simply amazing! Keep it going… Without wasting hours (like in most other YouTube videos), you explain everything in a few minutes. Well done indeed… 🙂

Vasile Tonofa · August 3, 2015 at 6:00 am

Thank you Sir, you make our life easier and better ! very good explanations .

Kevin Mackey · August 11, 2015 at 5:23 pm

I'm a little bit confused. From the practices described in previous lessons, I would expect that the dynamically allocated memory in heap should be freed after each iteration. But here it looks like you are just leaving them there until the program finishes running. Under what conditions should the variables in allocated memory be cleared?

Prashant Bisht · September 3, 2015 at 5:27 pm

at 7:12 why 2nd stack frame is also pointing to node to which root is pointing?Can anyone explain that?

Shubhangani Tayal · November 23, 2015 at 8:03 pm

how to search for description link or how to access source code?

Aswin Pranav · December 29, 2015 at 5:27 am

This is a great service. I salute you!

Pulak Sahu · February 14, 2016 at 3:28 am

Really appreciate the hard work that you have undertaken to create a video series like this. This video is perhaps the best example of your dedication. Never have I seen/heard some one explain heap, stack states and program execution in such an elaborate methodology the way you have explained. It's beautiful. Hats off!!!

Chansothea Bo · February 16, 2016 at 2:10 am

Hey man!!! My lecturer spent almost a week on this lesson but it take me just a few of your video!!!! Thank man!!! Keep up good work!!! 🙂

Ssonline 66 · April 11, 2016 at 10:56 am

commendable efforts…great

Sean O'donnell · May 5, 2016 at 4:19 am

why am I even in college, I should just be following you around

Arpit Maheshwari · June 17, 2016 at 11:06 am

Thank you mycodeschool for these great videos.! Complete description to Data Structures with such good explanation is what one needs.
Sir may i know if i can download all these videos from a single link or a drive location. I very much need them.

aziz as · June 20, 2016 at 2:39 am

The best thx

মহাজাগতিক আলো · July 25, 2016 at 2:59 pm

Ur lecture just awesome…….

JosefuGaming · July 28, 2016 at 1:31 pm

THANK YOU for these videos. Your description of the philosophy and the code are very informative. It has helped me dozens of times to realize and understand more deeply about what is going on in a program.

D. Refaeli · July 29, 2016 at 1:07 pm

You need a lot of patience to explain this – well done! 🙂

Nguai al · August 6, 2016 at 9:36 pm

wow. this clarified my understanding how recursive works. thank you …
there must be better way to avoid this same pattern: root = Insert(root, number);
i suppose if root is a global, there is no need for this repetitive pattern.

Rohit Singh · August 20, 2016 at 2:29 pm

nice explanation …….

Rohit Singh · August 20, 2016 at 2:36 pm

i want to suggest you one thing that mostly amateur learner watches your videos so it will be better to explain in c rather than c++. if you like this you can implement or else ignore it. thankyou

Ripal Thakkar · October 12, 2016 at 9:00 am

Thanks for teaching !

Mohammed Rafeeq · October 27, 2016 at 3:15 pm

thank you very much!! i like your videos very much as you explain in terms of application memory

Sourav · November 3, 2016 at 12:16 am

Why are we taking two arguments in 'Insert' when we could have declared the root pointer as global? It would have been much simpler, won't it?

yanling yang · February 5, 2017 at 7:50 pm

thanks a lot!!!!very clear!!!! i am going through all the videos, cannot express how fabulous you are!

Aman Chaudhary · March 23, 2017 at 9:46 pm

Sir You Are the Best CPP/C teacher as far as I know.
PLEASE make more VIDEOS.
I love the way you teach.

Ali Asgar · May 15, 2017 at 7:38 am

Excellent explanation !!

Theduff Richie · June 17, 2017 at 7:08 am

What if we make root as global variable?

Mihir Trivedi · August 17, 2017 at 8:25 am

Wow. Just wow. So clearly explained. I am a Masters' student in California who has never studied data structures and this is very helpful. Thanks.

Ankit Singh · August 18, 2017 at 10:53 am

the way you are teaching is really awesome….learning concepts with coding makes me easy to understand data structure.
Thank you

johnnywu9 · August 29, 2017 at 5:22 pm

Very nice tutorial. one question, What do actually the 200, 250,300 mean?

chodisetty lakshmi · October 11, 2017 at 1:35 pm

thanks a lot ! great explanation

Johnny Batafljeska · October 27, 2017 at 12:12 pm

10:08 where can we see in code that we are passing 300 as root? How does the root change from 200 to 150 or 300 (I know those are subrees, but I cant understand that in code)

Mitul Tyagi · June 1, 2018 at 2:34 pm

One of the best thing I learned…thanks man…

Yash Shrivastava · June 18, 2018 at 6:34 pm

please turn off your adblocker while watching these videos

Patrick Ren · July 15, 2018 at 3:04 am

I found that in the case of Binary Search Tree, insertion will always generate a leaf, since at the end of the recursion, a node without left and right pointers will be generated.

Amar Mishra · August 5, 2018 at 6:30 am

I want to see the faces of those 10 people who disliked the video. I mean what more do you need?

Usama Iftikhar Butt · August 6, 2018 at 4:41 am

thank u bro your explanation is amazing. Are u a teacher?

spicytuna08 · August 7, 2018 at 9:16 pm

great video. the understanding of the persistence of the memory in stack and heap is so important. even with this understanding, it gets very messy with code. e.g. function creates stack but within the function heap memory was allocated. so after the function terminates the heap memory is still persistence. it is kind of confusing. so when heap memory is created, i don't see the usage of declaring local variables. it is global since the the variable lives on after the function terminates.

Manish kumar · August 25, 2018 at 6:59 am

simply #grt…

HIT THE ENTERTAINMENT · September 2, 2018 at 8:58 am

Sit, at every call to insert you are assigning new value to node through return….is it not updating node address…every time thus we lost the top most node..

prabhat sharma · September 23, 2018 at 10:22 am

SIR,PLZ GIVE ME CLARITY ON THIS TOPIC

Rajesh · October 11, 2018 at 6:13 am

Succinctly explained. Thanks !

Shiva Bansfore · November 8, 2018 at 1:59 pm

finally i got the best lecture on data structure in youtube..thank you so much the way you explain is of next level…i hope that i will get more of videos from you…

Deval Jain · November 14, 2018 at 1:17 pm

Thanks a lot, sir. Really nice and best explanation one could find online. I was frustrated about learning trees for a very long time, but this cleared all my doubts and I think I have understood and grasped everything you taught. You are doing really nice work, sir. Thanks Again!

harish panwar · November 23, 2018 at 6:09 am

very good explanation talented guy.

zillBoy · December 6, 2018 at 3:35 pm

Wow! I need to watch this video again!
Thanks though!👍

Romy Ilano · February 20, 2019 at 4:31 am

Thanks your series is so good!!!

Hypnosis · March 17, 2019 at 7:21 pm

Amazing explanation!!

Jorge López · April 21, 2019 at 6:20 pm

Love this explanation. Architecture of programming is fascinating.

Anirudh Dua · April 22, 2019 at 8:10 am

awsome

chaitanya sonagara · June 13, 2019 at 4:26 am

Thanks

Chetan Rawat · August 5, 2019 at 12:06 pm

I wish I had seen your video lectures in my first 3 yrs of college. coding would have been so fun
u took 13 mins to make me understand something that my clg professors could not do in 3 yrs

Ayushi Sharma · August 14, 2019 at 5:13 am

Thank u so much sir for such good explanations 🤟

Manish Thakur · September 19, 2019 at 12:59 pm

Bhai upar itna accha padha rahein hai aur tumhe comments padhni hai?

Nick Gundobin · October 8, 2019 at 3:32 pm

Perfect video. Ur the best teacher

黎銘 · October 23, 2019 at 4:16 am

Once more I see beauty in C++.

Vulligadla Rohith · November 6, 2019 at 8:59 am

One stop solution for all the learners out there!! 👏Very crisp and Clear. Kudos for your efforts 🙏

Aayush Sharma · November 9, 2019 at 4:39 pm

great explanation

ajay arora · November 20, 2019 at 11:00 am

Brilliant.Couldn't have explained better. Thanks.

Mandeep singh · December 2, 2019 at 12:55 pm

u have great understanding of algorithms

Mandeep singh · December 2, 2019 at 12:56 pm

thanx for sharing

Vivek Gr · December 14, 2019 at 8:04 pm

really appreciate the effort in explaining in so detail. Good Job

Varun Vishwakarma · December 15, 2019 at 7:09 am

I feel like touching your feet. I was scared of Data Structure. You made it super easy. Please make videos on maths(For computer science) if you could

MURHAF AL-MSRI · December 23, 2019 at 6:06 pm

that was truly amazing

Jagadish G Naik · January 4, 2020 at 3:26 pm

Awesome Sir, you made it crystal clear. Thank you🙏

priya ravindran · January 22, 2020 at 9:44 pm

Great …

Ali El-Sayed · January 28, 2020 at 3:51 pm

Really Great and helpful!!
Love you sooo much brother <3

Leave a Reply

Your email address will not be published. Required fields are marked *