Binary tree struct in C

Question

Its been done to death, but the particular prompt (see Assignment 4) guiding me has strict+simple requirements that lead to a nice reduced environment to critique poor form. The project implements a heap-based binary tree structure with insert, find, and remove functions.

Both the binary tree nodes' IDs as well as data are int. Children are called left and right.

The project is split into 3 files, user.c, bintree.c, and bintree.h. The header file is #include'd in both the C scripts. user.c is where all the interaction is done - see bintree.h for the available functions as well as the binary tree node struct's definition.

I will leave the original instructor comments in for clarity (the boilerplate can be obtained from the link above).

---

user.c

   #include <stdio.h>
   #include "bintree.h"
   #include <stdlib.h>
   
   int main() {
      /*
      Insert your test code here. Try inserting nodes then searching for them.
   
      When we grade, we will overwrite your main function with our own sequence of
      insertions and deletions to test your implementation. If you change the
      argument or return types of the binary tree functions, our grading code
      won't work!
      */
   
      return 0;
   }

bintree.h

#ifndef BINTREE_H
#define BINTREE_H

// Node structure should have an int node_id, an int data, and pointers to left and right child nodes
typedef struct node {
    int node_id;
    int data;
    struct node *left;
    struct node *right; 
} node;

///*** DO NOT CHANGE ANY FUNCTION DEFINITIONS ***///
// Declare the tree modification functions below...

void insert_node(int node_id, int data);

int find_node_data(int node_id);

void remove_node(int node_id);

void delete_tree(); 

#endif

bintree.c

// bintree.c interfaces with the node struct defined in bintree.h
// to create and manipulate a heap-based binary tree. All functions
// meant for interfacing by the user are defined in the header file.
// 
// There is only ONE root (ie one tree), so there is only
// one node of the tree with no parents.
//
// bintree.c assumes binary tree was built USING THE INSERT_NODE ALGORITHM!
// It is *theoretically* possible to construct binary trees obeying
// the (left,right)~(<,>)node_id equivalence (ie left-child has smaller node id than node_id, 
// right-child has larger node id than node_id) that lose the 'useful' property
// of these trees: the extremely fast find_node_data algorithm,
// relying on all nodes to the right of the root having
// a larger node_id, and all nodes to the left having a smaller node_id.
// That is, a binary tree could theoretically locally preserve the 
// equivalence property without it globally holding. Therefore, bintree.c
// cannot be handed a root pointer from another heap-based binary tree interface
// and be expected to work, unless the tree also globally preserves the equivalence.

#include <stddef.h> // NULL def
#include <stdlib.h> // malloc
#include <stdio.h>  // printf/scanf
#include "bintree.h"

#define ERROR_VAL -999999 // junk data value for find_node_data

///*** DO NOT CHANGE ANY FUNCTION DEFINITIONS ***///

// Initialize tree
node *root = NULL;

// Insert a new node into the binary tree with node_id and data
void insert_node(int node_id, int data) {
    // reserve memory for node
    node *newNode = (node *)malloc(sizeof(node));
    // initialize node values
    newNode->node_id = node_id;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    // if tree empty, use as root 
    if (root == NULL) { 
        root = newNode;
        return;
    } 
    // if tree not empty, traverse tree
    // find parent and attach child
    node *tmp = root;
    while (1) {
        // go to right-child if higher id
        if (node_id > tmp->node_id) {
            // if no right-child, attach child
            if (tmp->right == NULL) {
                tmp->right = newNode;
                return;
            } else { tmp = tmp->right; }
        // go to left-child if lower id
        } else if (node_id < tmp->node_id) {
            // if no left-child, attach child
            if (tmp->left == NULL) {
                tmp->left = newNode;
                return;
            } else { tmp = tmp->left; }
        // if ids are equal, ask to replace data (keeps children)
        } else if (node_id == tmp->node_id) {
            char ans;
            while(1) {
                printf("node id occupied. replace data? (y)/(n): ");
                scanf("%c", &ans);
                if ( ans == 'y') {
                    tmp->data = data;
                    return;
                } else if ( ans != 'n') {
                    printf("invalid answer.\n");
                    continue;
                }
            }
        }
    }
}

// Returns pointer to node's parent given node id
node *find_parent(int node_id) {
    if (root == NULL) { printf("root is NULL\n"); return NULL; }
    else if (root->node_id == node_id) { return NULL; } // root has no parent
    node *tmp = root;
    node *parent = NULL;
    while (1) {
        if (tmp == NULL) {
            printf("no node found with node_id %d\n", node_id);
            return NULL;
        }
        // if node_id higher, go right; if lower, go left; if match, return
        else if ( (node_id > tmp->node_id) && (tmp->right != NULL) ) {
            parent = tmp;
            tmp = tmp->right;
        } else if ( (node_id < tmp->node_id) && (tmp->left != NULL) ) {
            parent = tmp;
            tmp = tmp->left; 
        } else if (node_id == tmp->node_id) {
            // check to ensure is actually parent before return
            if ( (parent->left == tmp) || (parent->right == tmp) ) { return parent; } 
        } else {
            // catch no matches
            tmp = NULL;
        }
    }
}

// Returns pointer to node given node_id
node *find_node(int node_id) {
    if (root == NULL) { return NULL; } // no nodes at all
    else if (root->node_id == node_id) { return root; } // root has no parent
    node *tmp = find_parent(node_id);
    if (tmp == NULL) { return NULL; }
    // parent has node w/ node_id as left- or right-child
    else if ( (tmp->left != NULL) && ((tmp->left)->node_id == node_id) ) { return tmp->left; } 
    else if (tmp->right != NULL) { return tmp->right; }
    // catch no matches
    return NULL;
}

// Find the node with node_id, and return its data
int find_node_data(int node_id) {
    node *tmp = find_node(node_id);
    if (tmp == NULL) { return ERROR_VAL; }
    return tmp->data;
}


/* OPTIONAL: Challenge yourself w/ deletion if you want 
Find and remove a node in the binary tree with node_id. 
Children nodes are fixed appropriately. */
void remove_node(int node_id) {
    node *parent = find_parent(node_id);
    node *tmp = find_node(node_id);
    if (tmp == NULL) { 
        printf("remove_node failed, node DNE\n");
        return; 
    }

    //      •  'left-child' and 'right-child' refer to the 
    //         children of the node being deleted. 
    //      •  'appropriate leg' refers to whichever (left or right) 
    //         side of the parent the node being deleted is attached to.
    //
    // find the right-most descendent of the left-child (hence the highest node id less than node_id).
    //
    // - if no left-child, attach right-child to appropriate leg of tmp's parent.
    //
    // - otherwise, attach right-child to right-most descendent of left-child's right leg.
    //   attach left-child to appropriate leg of tmp's parent.
    // 
    // free tmp and return
    if (tmp->left == NULL) {
        if (tmp->right != NULL) {
            // catch root case
            if (parent == NULL) {
                root = tmp->right;
            }
            // otherwise attach right-child to appropriate leg of parent
            else if (parent->left == tmp) { 
                parent->left = tmp->right;
            } else {
                parent->right = tmp->right;
            }
        }   
    } else {
        // catch root case
        if (parent == NULL) {
            root = tmp->left;
        }
        // otherwise attach left-child to appropriate leg of parent
        else if (parent->left == tmp) {
            parent->left = tmp->left;
        } else {
            parent->right = tmp->left;
        }
        // and attach right-child to right-most descendent of left-child's right leg
        node *next = tmp->left;
        while (next->right != NULL) {
            next=next->right;
        }
        next->right = tmp->right;
    }
    free(tmp);
    return; 
}

// For internal use by delete_tree,
// recursively frees nodes of tree
void delete_node(node *tmp) {
    if (tmp->left != NULL) {
        delete_node(tmp->left);
    }
    if (tmp->right != NULL) {
        delete_node(tmp->right);
    }
    free(tmp);
}

// There is only one tree and it starts where 'root' points,
// delete_tree unallocates all memory for every node connected 
// to root, including root.
void delete_tree() {
    delete_node(root);
}

---

I would have liked to change find_node_data to be cast to a pointer so that NULL could be used to represent no result, but I wanted to stick to the grading scheme.

This is a rudimentary assignment, so any discussion/critique is appreciated! How are my comments? Is the code concise, clear, efficient, and consistent (are there shorter algorithms, are my control structures convoluted, are my logic checks sound, is it readable, correct usage of macros)? Within the bounds of the guidelines, are there any gaps in my implementation?

Answer 1

General Observations

The use of the typedef for the node struct is a good practice.

The fact that all of the loops and if statements contain the code as blocks by using the braces ({ and }) is a good practice.

It would be much easier to do a code review if we had the working test code. The lack of the working test code in the main() function in user.c makes it more difficult to review the code. Some users on this site might close the question as Missing Review Context.

It really isn't clear why there is a node_id element in the node struct. Generally binary trees are ordered by the value of their contents (the data filed or member). Insertion into the tree should be based on the value of the data rather than the node ID.

The code would be more portable if stdlib.h was included in user.c and the code returned either EXIT_FAILURE or EXIT_SUCCESS from main().

Since delete_node() is using recursion, it would probably be better if insert_node() used recursion to find the correct location for the node rather than a while loop.

Convention When Using Memory Allocation in C

When using malloc(), calloc() or realloc() in C a common convention is to sizeof(*PTR) rather sizeof(PTR_TYPE), this make the code easier to maintain and less error prone, since less editing is required if the type of the pointer changes.

    node* newNode = malloc(sizeof(*newNode));

In C there is no reason to cast the return value of malloc().

Test for Possible Memory Allocation Errors

In modern high-level languages such as C++, memory allocation errors throw an exception that the programmer can catch. This is not the case in the C programming language. While it is rare in modern computers because there is so much memory, memory allocation can fail, especially if the code is working in a limited memory application such as embedded control systems. In the C programming language when memory allocation fails, the functions malloc(), calloc() and realloc() return NULL. Referencing any memory address through a NULL pointer results in undefined behavior (UB).

Possible unknown behavior in this case can be a memory page error (in Unix this would be call Segmentation Violation), corrupted data in the program and in very old computers it could even cause the computer to reboot (corruption of the stack pointer).

To prevent this undefined behavior a best practice is to always follow the memory allocation statement with a test that the pointer that was returned is not NULL.

    node* newNode = malloc(sizeof(node));
    if (!newNode)
    {
        fprintf(stderr, "Malloc failed in insert_node()\n"); 
        exit(EXIT_FAILURE);
    }

A better practice would be to have a function that tests the allocation and returns status (NULL pointer in this case).

static node* creat_node(int data)
{
    node* newNode = malloc(sizeof(*newNode));
    if (!newNode)
    {
        fprintf(stderr, "Malloc failed in insert_node()\n");
        return NULL;
    }
    else
    {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

Avoid Global Variables

It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this stackoverflow question provide a fuller explanation.

In this case root is a global variable. You can make it a local variable by using the static keyword.

// Initialize tree
static node* root = NULL;

Any functions that should be local such as delete_node() should be declared static as well. I am assuming delete_node() is local since it isn't included in bintree.h. This is also true for the find_parent() function.

Answer 2

I like
• not adding a parent field to node
• not re-implementing "conditional descent" in find_node_data()

Wanting to change behaviour of the not found case, I sort of see why to be reluctant to document it, but please do.

I frowned at int find_node_data(int node_id) under the comment tree modification functions - I expect it to be non-mutating.

I don't like else where it is redundant.

In find_node(), the handling of left and right is asymmetrical: a red flag.
It deserves a comment why there is no need to (re-)check tmp->right->node_id.

A pity C does not support returning multiple values from a function, or "out parameters".
Then again, it has pointers; using them in find_node():

// Returns pointer to node given node_id. 
// Assigns *parent_p if parent_p != NULL, even if node_id is not found
static node *find_node(int node_id, node **parent_p) {
    if (root == NULL || root->node_id == node_id) {
        if (NULL != parent_p) { *parent_p = NULL; } // root has no parent
        return root;
    }
    const node *node = root, *parent = NULL;
    for (;;) {
        if (NULL == node) {
            // printf("no node found with node_id %d\n", node_id);
            break;
        }
        if (node_id == node->node_id) {  // if match, return
            //// check to ensure is actually parent before return
            //if (parent->left == node || parent->right == node) { ; }
            break;
        }
        parent = node;
        // if node_id higher, go right; if lower, go left;
        node = node_id > node->node_id ? node->right : node->left;
    }
    if (NULL != parent_p) { *parent_p = (struct node*)parent; }
    return (struct node*)node;
}

You can use this in insert_node(), too.
Which is one of the places where you mix "business logic" with interaction with something outside (tree) business, such is not recommended.

pacmaninbw rightly advised to not have root a global symbol.
While it is given this way in the .c template, in a (C, "without object support") library, you would pass some information about the tree to handle as a parameter to each function - either as the first or last parameter.
A node* allows handling of sub-trees here; library client code would keep one dummy node per tree.