Write a program which, given the root pointer of a binary tree returns the height of the tree (height = number of levels).

Source Code

Brief explanation is provided after the source code.

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

struct tnode{
    int number;
    struct tnode *left; /* left Child */
    struct tnode *right; /* right Child */
};

int height(struct tnode*); /* Compute height of tree */
struct tnode *addtree(struct tnode*, int);
void treeprint(struct tnode*);
struct tnode *root;
struct tnode *talloc(void);
int *dupnum(int *);

int main(int argc, char **argv){
    FILE *in;
    const char * fn = "integer_file";
    char buff[0x200];
    root = NULL;  /* empty tree */

    if((in = fopen(fn,"rb")) == NULL){
        printf("Cannot open input file.\n");
        exit(1);
    }

     // Read integers from a file and add to a tree node
    while (fgets(buff, sizeof buff, in)) {
        root = addtree(root, atoi(buff));
    }

    printf("Tree is traversed in-order\n");
    treeprint(root);
    printf("\nTree Height: %d\n", height(root)); // Function height is given the root pointer of a binary tree
    fclose(in);
    return 0;
}

/* Compute the height of tree */
int height(struct tnode* p) {
    int u, v;
    if (p == NULL)
        return -1;
    u = height(p -> left);
    v = height(p -> right);
    if (u > v)
        return u + 1;
    else
        return v + 1;
}

/* addtree: add a node with n, at or below p */
struct tnode *addtree(struct tnode *p, int n){
    int cond;
    if (p == NULL){
        p = talloc();
        p -> number = dupnum(n);
        p -> left = p -> right = NULL;
    }else if (n <= p->number)
        p -> left = addtree(p -> left , n);
    else
        p -> right = addtree(p -> right , n);

    return p;
}

/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p){

    if (p != NULL) {
        treeprint(p -> left);    /* Begin with left sub tree */
        fprintf(stdout,"%d\n" ,p -> number);     /* Output number */
        treeprint(p -> right);   /* then move to right sub tree */
    }
}

/* talloc: make a tnode */
struct tnode *talloc(void) {
    return (struct tnode *) malloc(sizeof(struct tnode)); 
}

/* duplicate a number */
int *dupnum(int *n){
    char *p;
    /* make a duplicate of n */
    p = (int *) malloc(sizeof(int));
    if(p != NULL)
        p = n;
    return p;
    free(p);
}

When you compile and execute the above program it produces the following result on Linux:

Tree is traversed in-order
-7
-6
-1
10
10
12
23
100

Tree Height: 4

Brief Explanation

  • The height of a tree is the maximum of the levels of the tree's nodes.
  • The function height, computes the height of a binary tree given the root pointer of the tree.
  • The function returns -1, if the root pointer is NULL otherwise it calls itself recursively assigning return values to integer variables u and v.
  • If u is greater than v, u + 1 is return as the height of the tree otherwise v + 1.

Add comment


Security code
Refresh