#include <stdio.h>
#include <stdlib.h>

typedef struct treeNode {
    int key;
    struct treeNode* left;
    struct treeNode* right;
} treeNode;


int count = 0;

treeNode* insertNode(treeNode** t1, int x) {
    if (*t1 == NULL) {
        *t1 = malloc(sizeof(treeNode));
        (*t1)->key = x;
        (*t1)->left = NULL;
        (*t1)->right = NULL;
    }
    else if (x < (*t1)->key) {  //left
        (*t1)->left = insertNode(&(*t1)->left, x);
    }
    else if (x > (*t1)->key) { //right
        (*t1)->right = insertNode(&(*t1)->right, x);
    }
    else {
        printf("SameValue exist.\n");
    }
    return *t1;
}

int getIPL(treeNode* n1) {
    int rightcount;
    int leftcount;
    int rootcount = 1;

    if (n1 != NULL) {
        if (n1->left == NULL && n1->right == NULL) {
            count = rootcount;
        }
        else if (n1->left != NULL && n1->right == NULL) {
            leftcount = 1   getIPL(n1->left);
            count  = leftcount;
        }
        else if (n1->left == NULL && n1->right != NULL) {
            rightcount = 1   getIPL(n1->right);
            count  = rightcount;
        }
        else {
            leftcount = 1   getIPL(n1->left);
            rightcount = 1   getIPL(n1->right);
            count  = leftcount   rightcount;
        }
    }
    return count;
}


int main() {
    treeNode* T1 = NULL;

    insertNode(&T1, 10);
    insertNode(&T1, 20);
    insertNode(&T1, 3);
    insertNode(&T1, 25);

    printf("IPL : %d", getIPL(T1));
}

This code is to get an internal path length (IPL) from BST. It works normally up to level 2, but it doesn't work above that.

When put on tree 10 5 15, IPL value of 5 comes out.

After, put on 30, you will get 9, not the normal value 8.

I want the IPL value of 8.

Please tell me where the problem is.

CodePudding user response：

The depth of each node needs to be taken into account. For example:

static int getIPL_helper(treeNode *n1, int depth) {
    if (n1) {
        return getIPL_helper(n1->left, depth   1)  
               getIPL_helper(n1->right, depth   1)   depth;
    } else {
        return 0;
    }
}

int getIPL(treeNode *n1) {
    return getIPL_helper(n1, 1);
}