Just call a function

Computer Science Level 3

/* Basic structure of the node of a BST */
struct node{
    int data;
    node* left; 
    node* right;
};
/* A function to print all the data of a BST    */
void print(node* Tree){
    if(Tree){
        print(Tree->left);
        cout<<Tree->data<<" ";
        print(Tree->right);
    }
}

What is the number of function calls for the recursive function print(node* Tree) to print the data of the BST in the picture above ?

Bonus: How can you generalize your solution for any BST ?

The answer is 15.

1 solution

Kristian Takvam Staff
Mar 14, 2016

#include <iostream>

using namespace std;

class node {
public:
    node *left;
    node *right;
    int data;

    node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

static int callCount = 0;

void print(node *Tree) {
    callCount += 1;
    if (Tree) {
        print(Tree->left);
        cout << Tree->data << " ";
        print(Tree->right);
    }
}

int main(int argc, const char * argv[]) {
    node oneNode(1);
    node fourNode(4);
    node sixNode(6);
    node nineNode(9);

    node threeNode(3);
    threeNode.left = &oneNode;
    threeNode.right = &fourNode;

    node eightNode(8);
    eightNode.left = &sixNode;
    eightNode.right = &nineNode;

    node fiveNode(5);
    fiveNode.left = &threeNode;
    fiveNode.right = &eightNode;

    print(&fiveNode);

    cout << endl;
    cout << "Call count=" << callCount << endl;

    return 0;
}

Output:

1 2	`1 3 4 5 6 8 9 Call count=15`

Just call a function

The answer is 15.

1 solution

0 pending reports