I'm working on this challenge:

Write a function height(n, T) to return the height of node n of tree T. Given is a Tree data structure (using two arrays) to store characters as labels and some operators.

The tree T is encoded as a set of two arrays, where nodes are identified by indices in those two arrays (which have the same length). One array holds the labels of the nodes, and the other has the parent references as indices in the same arrays. A parent reference of -1 means the node is the root.

I tried several things, but can't solve this problem. For some cases the height function returns the correct answer, but for others not

My C code:

int height(Node n, Tree *pT){ 
    // if invalid
    if ( n < 0 || n> pT->maxNode) return -1;
    if ( leftmostChild(n, pT) == NULL_NODE && rightSibling(leftmostChild(n,pT),pT) == NULL_NODE) return 0;
    //find 
    int L = height(leftmostChild(n, pT), pT);
    int R = height(rightSibling(leftmostChild(n, pT),pT), pT);
    if ( L > R) return L   1;
    return R   1;
}

This is the full code:

#include<stdio.h>
#define MAXLENGTH 100
#define NULL_NODE -1
 
typedef int Node;
typedef char LabelType;
 
typedef struct {
    Node      P[MAXLENGTH];
    LabelType L[MAXLENGTH];
    int maxNode;
} Tree;

Node leftmostChild(Node n, Tree *pT){
    if ( n < 0 || n > pT->maxNode) return NULL_NODE;
    for ( Node i = n   1; i <= pT->maxNode; i  ){
        if ( pT->P[i] == n )  return i;
    }
    return NULL_NODE;
}

Node rightSibling(Node n, Tree *pT){
    if ( n < 0 || n > pT->maxNode) return NULL_NODE;
    for ( Node i = n   1; i <= pT->maxNode; i  ){
        if ( pT->P[i] == pT->P[n] )  return i;
    }
    return NULL_NODE;
}
 
int height(Node n, Tree *pT){
    if ( n < 0 || n>pT->maxNode) return -1;
    if ( leftmostChild(n, pT) == NULL_NODE && rightSibling(leftmostChild(n,pT),pT) == NULL_NODE) return 0;
    int L = height(leftmostChild(n,pT), pT);
    int R = height(rightSibling(leftmostChild(n,pT),pT), pT);
    if ( L > R) return L   1;
    return R   1;
}
 
int main(){
    Tree T = { {-1, 0, 0, 0, 0, 0, 3, 6, 2, 5, 1, 10, 9, 4, 7, 5},
    {'S', 'L', 'K', 'J', 'A', 'V', 'R', 'E', 'F', 'T', 'C', 'X', 'U', 'I', 'H', 'D'}, 15};
    for (int i = 0; i <= T.maxNode; i  )
        printf("height(%d) = %d\n", i, height(i, &T));
    }
}

Expected output:

height(0) = 4
height(1) = 2
height(2) = 1
height(3) = 3
height(4) = 1
height(5) = 2
height(6) = 2
height(7) = 1
height(8) = 0
height(9) = 1
height(10) = 1
height(11) = 0
height(12) = 0
height(13) = 0
height(14) = 0
height(15) = 0

Current, wrong output:

height(0) = 3
height(1) = 2
height(2) = 1
height(3) = 3
height(4) = 1
height(5) = 2
height(6) = 2
height(7) = 1
height(8) = 0
height(9) = 1
height(10) = 1
height(11) = 0
height(12) = 0
height(13) = 0
height(14) = 0
height(15) = 0

You can also see it run on ideone.

CodePudding user response：

There are some issues in your height function:

• In the second if statement, if the first condition is true, then you shouldn't need to call rightSibling at all, but return 0 anyhow when that is true. Also, when the first condition is not true, it is irrelevant whether there is a right sibling or not, and the return value should certainly not be 0.

• Your code is expecting the tree to be a binary tree, but this is not guaranteed. A node can have more than two children, and so you need to iterate all siblings. For this you could use a for loop.

Corrected version:

int height(Node n, Tree *pT){
    if ( n < 0 || n>pT->maxNode) return -1;
    int h = -1;
    for (int child = leftmostChild(n, pT); child != NULL_NODE; child = rightSibling(child, pT)) {
        int childHeight = height(child, pT);
        h = h < childHeight ? childHeight : h;
    }
    return h   1;
}