Linked list- find_node_data

Question

I have previously posted about this same topic. I am self-learning data structures using MIT Open Courseware. I'm doing the 6.S096-Introduction to C/C++ course and attempting the fourth assignment.

It is based on binary search trees and I gave it a try. I wanted to print the values for debugging but kept getting different executions each time.

One time, the cycle doesn't complete and the other time, it goes on to infinity. The debugging block also relates to the other function(find_node_data) I have to complete. So if I can figure what's wrong here, I can easily finish the find_node_data. I have commented a few things to see if it affects anything. What am I doing wrong?

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

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...
node* newNode(int data,int node_id){
    node* new_node = (node*) malloc(sizeof(node)); 
    new_node->data = data; 
    new_node->node_id= node_id; 
    new_node->right= new_node->left=NULL;  
    return new_node;
}

node* insert_node(node* root, int node_id, int data) {
    if(root==NULL)
        return newNode(data,node_id);
    else{
        node* cur;
        if(node_id<root->node_id){
            cur=insert_node(root->left,data,node_id);
            root->left=cur;                
        }
        else if(node_id>root->node_id){
            cur=insert_node(root->right,data,node_id);
            root->right=cur;
        } 
    }
    return root;
}

// Find the node with node_id, and return its data
/*int find_node_data(node* root, int node_id) {
    node* current; 
    for( current = root->; current->next!=NULL; 
        current= current->next){ 
    if(current->data == data) return current; 
} 
return NULL; 
}
*/
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!
    */
    int T,data,node_id;
    printf("Print yo cases");
    scanf("%d", &T);
    node* root = NULL;
    while(T-->0){
        printf("Type yo numnums no. %d:",T);
        scanf("%d %d",&data,&node_id);
        root=insert_node(root,data,node_id);
    }
    node *lol;
    node *king;
    for(lol=root;lol->left!=NULL;lol=lol->left){
        //for(king=root;king->right!=NULL;king=king->right){
        printf("executed!\n");  
        printf("%d ",lol->node_id);//,king->node_id);
        //}
    }       
    return 0;
}

Answer 1

To find the node_data you can use recursion to find the node.

node* find_node_data(node *root, int node_id) {    
    if (root == NULL)
        return NULL;
    else if (root->node_id == node_id)
        return root;
    else {
        node *left = find_node_data(root->left, node_id);
        return left? left: find_node_data(root->right, node_id);
    }
}

And then get the data for the node e.g. get the data for node with node_id 42:

 printf("node data %d", find_node_data(root, 42)->data);

Full program below (I can't guarantee its correctness but maybe you can?)

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

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...
node *newNode(int data, int node_id) {
    node *new_node = (node *) malloc(sizeof(node));
    new_node->data = data;
    new_node->node_id = node_id;
    new_node->right = new_node->left = NULL;
    return new_node;
}

node *insert_node(node *root, int data, int node_id) {
    if (root == NULL)
        return newNode(data, node_id);
    else {
        node *cur;
        if (node_id < root->node_id) {
            cur = insert_node(root->left, data, node_id);
            root->left = cur;
        }
        else if (node_id > root->node_id) {
            cur = insert_node(root->right, data, node_id);
            root->right = cur;
        }
    }
    return root;
}

// Find the node with node_id, and return its data
/*
int find_node_data_old(node *root, int node_id) {
    node *current;
    for (current = root->; current->next != NULL;
         current = current->next) {
        if (current->data == data) return current;
    }
    return NULL;
}*/
node* find_node_data(node *root, int node_id) {

    if (root == NULL)
        return NULL;
    else if (root->node_id == node_id)
        return root;
    else {
        node *left = find_node_data(root->left, node_id);
        return left? left: find_node_data(root->right, node_id);
    }
}
void print(node *np) {
    if (np) {
        print(np->left);
        printf("(%d, %d)", np->node_id, np->data);
        print(np->right);
    }
}

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!
    */
    int T, data, node_id;
    printf("Print yo cases");
    scanf("%d", &T);
    node *root = NULL;
    while (T-- > 0) {
        printf("Type yo numnums no. %d:", T);
        scanf("%d %d", &data, &node_id);
        root = insert_node(root, data, node_id);
    }
    node *lol;
    node *king;
    for (lol = root; lol->left != NULL; lol = lol->left) {
        //for(king=root;king->right!=NULL;king=king->right){
        printf("executed!\n");
        printf("%d ", lol->node_id);//,king->node_id);
        //}
    }
    print(root);
    printf("\n");
    printf("node data %d", find_node_data(root, 42)->data);
    return 0;
}

Test

Print yo cases3
Type yo numnums no. 2:22 42
Type yo numnums no. 1:21 41
Type yo numnums no. 0:20 40
executed!
42 executed!
41 (40, 20)(41, 21)(42, 22)
node data 22

You may also use Jonathan Leffler's improved recursion to find the node:

node *find_node_data2(node *root, int node_id) {
    if (root == NULL)
        return NULL;
    else if (root->node_id == node_id)
         return root;
    else if (root->node_id > node_id)
        return find_node_data(root->left, node_id);
    else
        return find_node_data(root->right, node_id);
}

Both functions return the correct values as seen in the second test.

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!
    */
    int T, data, node_id;
    printf("Print yo cases");
    scanf("%d", &T);
    node *root = NULL;
    while (T-- > 0) {
        printf("Type yo numnums no. %d:", T);
        scanf("%d %d", &data, &node_id);
        root = insert_node(root, data, node_id);
    }
    node *lol;
    node *king;
    for (lol = root; lol->left != NULL; lol = lol->left) {
        //for(king=root;king->right!=NULL;king=king->right){
        printf("executed!\n");
        printf("%d ", lol->node_id);//,king->node_id);
        //}
    }
    print(root);
    printf("\n");
    printf("node data %d\n", find_node_data(root, 42)->data);
    printf("node data find_node_data2 %d", find_node_data2(root, 42)->data);
    return 0;
}

Test 2

Print yo cases3
Type yo numnums no. 2:11 12
Type yo numnums no. 1:13 14
Type yo numnums no. 0:20 42
(12, 11)(14, 13)(42, 20)
node data 20
node data find_node_data2 20