Code

Explanations

1) Original FindMin with parameter node of data 10 gets pushed onto the call stack.

2) is the node NULL? nope

3) does the node have a left ? Yes! Hence…

4) Let’s recursively call and go down the left side of the tree by using node->left as its parameter. We will return whatever we find down there.

5) Therefore, we push another FindMin function with parameter node->left onto the stack.
The node->left evaluates to node with data 5.

1) for function FindMin with parameter node of data 5, we evaluate if the node is NULL. nope

2) does the node have a left? yes! Hence…

3) Let’s recursively call another FindMin and go down the left side of the tree by using node->left as the parameter. We will return whatever we find down there. node->left evaluates to node with data 1.

4) We push FindMin function onto the call stack with node with 1.

1) In FindMin function with node data 1, node is not NULL.

2) FindMin with node data 1 block node data 1’s node->left points to NULL, hence we need to return this node of data 1.

This means that we’ve reached the far end of the left side of the balanced sorted binary tree. A sorted binary tree just means that it keeps its smallest items at the left most, and largest item on its rightmost. It does this by comparing its current node, and shifting all larger nodes to the right, and shifting all smaller nodes to its left.

3) FindMin with node data 1 block returns node with data 1’s address.

4) FindMin with node data 1 block pop this FindMin with parameter NULL

5) FindMin with node data 5 block return node with data 1.

6) FindMin with node data 5 block pop FindMin with node data 5.

7) FindMin with node data 10 block return node data 1. See 5)

8) FindMin with node data 10 block pop FindMin with node data 10.

First we are given the tree at node 5

1) We push function insert onto the stack with the parameter of a node with data 5.

2) We check to see if the node with data 5 is NULL or not. It is not, so we move on.

3) the data we want to insert is less than 5

4) thus we go down the left side of the tree because the data we want to insert, 2, is less than the current node’s data of 5. We travel left down the node tree by pushing another insert function with the parameter of the left side of our node, which is node->left.

The call^r means we call the insert function recursively. The insert function returns the node that it represents, which is also a node tree. Hence we need to point our node->left to whatever node tree the recursion function returns.

5) node->left evaluates to node with data 1. Hence, we push function insert onto the stack with the parameter of a node with data 1.

1) Once function insert with node data 1 gets pushed onto the stack, we then evaluate to see if that node is NULL. Obviously, it is not.

2) The data we want to insert, 2, is bigger than current node data of 1.

3) Thus, we want to travel towards right. We go down the right side of the tree by pushing another insert function with the parameter of the right side of our current node, which is node->right.

The call^r means we call the insert function recursively. The insert function returns the node that it represents, which is also a node tree. Hence we need to point our node->right to whatever node tree the recursion function returns.

We need to assign node->right to whatever node tree the recursion function returns.

4) node->right evaluates to NULL. We push function insert with parameter NULL onto the stack.

5) We see that the parameter is NULL, which means we reached to the end and is ready to place our insertion data 2 here. We create a new node of data 2.

6) We return this newly created node.

1) Then we pop the insert function with parameter NULL.

2) We now continue where we left off from insert function with parameter node of data 1. We had its right point to whatever the recursive insert returns. The recursive insert function returned newly created node of data 2. Thus, we assign the parameter node of data 1’s right to the newly created node of data 2.

3) We then continue execution and return the current node of data 1.

4) We pop insert function with node of data 1.

1) We now continue where we left off at insert function with parameter node of data 5. We had our left point to whatever the recursive insert returns. The recursive insert function returned node of data 1’s address and we have our current node 5’s left point to it.

2) Then we reach the end of the function definition by returning the current node with data 5.

3) Finally the original insert function starting with node of data 5 gets popped off the call stack.

Code

a) function doll(10) gets pushed onto the stack.
b) evaluates that 10 != 0
c) outputs 10
d) calls recursive function doll(10-1). Thus doll(9) gets pushed onto the stack.

WE keep going in the same manner until we hit to doll(1)
a) we push doll(1)
b) evaluates that 1!=0
c) prints 1
d) calls recursive function doll(1-1)
e) doll(0) gets pushed onto the stack
f) evaluates that 0==0
g) thus prints “reached 0”
h) execution runs to end, pops doll(0)

a) doll(0) pops from the return. Remember, a function pops whenever we hit the end of code, or returns.
b) We then arrive at where we left off at the recursive call in doll(1).
c) we come to end of function in doll(1), so we pop doll(1).

We continue popping in the same manner until we get to doll(8-1)…

a) execution runs to end of doll(8), we pop doll(8)
b) we continue where we left off at doll(9-1)
c) we run to end of function for doll(9), we pop doll(9)
d) we continue where we left off at doll (10-1)
e) we run to end of function at doll(10), we pop doll(10)

The Function

a) the first printnum with a parameter of 1, printnum(1), gets pushed onto the stack.
b) prints 1
c) evaluates the if statement that 1 < 9 d) calls recursion method printnum(1+1)

a) printnum(2) gets pushed onto the stack
b) method prints 2
c) evaluates the if statement that 2 < 9 d) calls recursion method printnum(2+1)

we continue in this manner until printnum(1) to printnum(8) gets pushed onto the stack…and their corresponding couts get printed in the console.

a) printnum(9) gets pushed onto the stack.
b) print start 9
c) the if statement evaluates to false.
d) Then the next statement is to print ‘end: 9’

a) After the printing of ‘end: 9’, our execution arrow hits the end of the function. Thus, printnum(9) gets popped off the stack.
b) We then resume execution at the recursive call that happened at printnum(8)
c) execution arrow moves down and prints ‘end: 8’
d) execution arrow hits end of function at printnum(8). printnum(8) gets popped off the stack

a) printnum(8) gets popped off stack
b) resume execution at recursion call inside of printnum(7)
c) execution arrow moves down and prints ‘end: 7’.
d) execution arrow hits end of function at printnum(7). printnum(7) gets popped off stack

So we keep going until…

a) we come to the recursive call in printnum(2) function.
b) execution arrow moves down and prints ‘end:2’
c) execution arrow hits end of function printnum(2). Thus, printnum(2) gets popped off the stack.
d) resumes execution at recursive call inside of printnum(1)
e) execution arrow move down and prints ‘end: 1’.