Question

What does the following function f do? The parameter r is the root of a
Binary Search Tree? DO NOT JUST EXPLAIN THE CODE. DO NOT JUST EXPLAIN THE SYNTAX OF THE CODE.
int f(Node* r)
{
if (r.left == NULL && r.right==NULL)
return 0;
else
return 1+f(r.left)+f(r.right);
}

Answer 1

What does Function do

The given recursive code returns the Count of Non -Leaf Node of a binary Tree.

It receives the root of the tree as input . if it is a leaf node it returns 0 else it adds 1 and calls the left and right subtree.

EXAMPLE

Lets consider the above given tree

EXPLAINATION

Current Root value	Value of function
1	1+(1.left)+(1.right)
2	1+1+(2.left)+(2.right)+(1.right)
4	1+1+0+(2.right)+(1.right)
5	1+1+0+0+(1.right)
3	1+1+0+0+1+(3.left)+(3.right)
6	1+1+0+0+1+0+(3.right)
7	1+1+0+0+1+0+0

FINAL VALUE = 1+1+0+0+1+0+0 = 3

when Node 1 is root it has left and right child so we add 1 and call its left child and then right child.

when Node is 2 it has left and right child so we add 1 and call its left and right child

when Node is 4 it does not have any child so we return 0 .

when Node is 5 it does not have any child so we return 0 .

when Node is 3 it has left and right child so we add 1 and call its left and right child

when Node is 6 it does not have any child so we return 0 .

when Node is 7 it does not have any child so we return 0 .