Inserting node in binary tree in C

It passes in a double pointer because it needs to change pointers in the process. All elements of a tree can be thought of as pointers which need to be changed when insert is called. If you don't pass in a double pointer, what you're essentially doing is copying pointer as a local variable to the function and changes have no effect when the insert function exits. Ignore me if I'm wrong.

If you want to only read what is pointed by a pointer, your argument is of type foo*. If you want to change what is pointed by a pointer, your argument is of type foo *. But there, you want to be able to change what you point to. So, you need a pointer to your pointer, to be able to change its value.

In java, any method having as an argument a TreeNode is equivalent to a C function having as an argument a tree_node* ; hence, if you have a method with that signature :

// Java code
static void treeInsert (TreeNode t);

Within that method, you can access methods from t that can read its current status, you can even modify the state of t, and that state will be changed even once you left the method.

But, if you're doing something like that

t = null;

that won't have an effect once you leave the method. That means

// Java code
static void treeNull (TreeNode t) {
    t = null;  // Warning, local change only !
}

static void treeChange (TreeNode t) {
    t.changeState();
}

static void foo () {
    t = new TreeNode();
    t.treeChange();   // Ok, t has now an update state
    t.treeNull();     // Warning, t is not null here
}

You can't have the equivalent of a double pointer in java, so you can't make that work.

In C, you can do this :

// C code
void updateState(tree_node* t) {
    data = data + 1;  // This is nonsense, just to make the point
}

void localChangePointer(tree_node* t) {
    t = NULL;
}

void changePointer(tree_node** t) {
    free_and_clean(*t);
    *t = NULL;
}

void sillyStuff() {
    tree_node* t;
    // Initialize t
    ...

    updateState(t); // (*t).data changed
    localChangePointer(t);  // Warning : t is not null yet !
    changePointer(&t);      // This time, we gave the address of t, not t itself

    // Now t == NULL;
}

Maybe you will like such variant:

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

typedef struct btree_node{
    int data;
    struct btree_node *left, *right;
} BTree;

// get tree leaf nearest to v
BTree *bt_get(BTree *root, int v){
    if(!root) return NULL;
    int D = root->data;
    if(D == v) return root;
    if(root->data > v) return root->left;
    else return root->right;
}

// find leaf with v or nearest to it (prev)
BTree *bt_search(BTree *root, int v, BTree **prev){
    if(!root){
        if(prev) *prev = NULL;
        return NULL;
    }
    BTree *p;
    do{
        p = root;
        root = bt_get(root, v);
    }while(root && root->data != v);
    if(prev) *prev = p;
    return root;
}

BTree *bt_create_leaf(int v){
    BTree *node = calloc(1, sizeof(BTree));
    if(!node) return NULL;
    node->data = v;
    return node;
}

// insert new leaf (or leave it as is, if exists)
// return root node
BTree *bt_insert(BTree *root, int v){
    BTree *closest, *node;
    node = bt_search(root, v, &closest);
    if(node) return node; // value exists
    if(!closest) // there's no values at all!
        return bt_create_leaf(v); // create root node
    // we have a closest node to our data, so create node and insert it:
    node = bt_create_leaf(v);
    if(!node) return NULL;
    int D = closest->data;
    if(D > v) // there's no left leaf of closest node, add our node there
        closest->left = node;
    else
        closest->right = node;
    return root;
}

int main(void){
    BTree *tp, *root_p = NULL;
    int i, ins[] = {4,2,6,1,3,4,7,14,0,12};
    for(i = 0; i < 10; i++)
        if(!(root_p = bt_insert(root_p, ins[i]))) err(1, "Malloc error"); // can't insert
    for(i = 0; i < 15; i++){
        tp = bt_search(root_p, i, NULL);
        printf("%d ", i);
        if(!tp) printf("not ");
        printf("found\n");
    }
    return 0;
}

// I was wrong in previous answer, correct

Here would be doing it without double pointers. I don't see any difference.

int t_insert(struct tree_node *root, int v) {
  while (root) {
    if (root->data == v)
      return 1;
    if (root->data > v)
      root = &(root->left_p);
    else
      root = &(root->right_p);
  }

  if ((root = (struct tree_node *) malloc(sizeof(struct tree_node))) == 0)
    return 2;

  root->data = v;
  root->left_p = 0;
  root->right_p = 0;

  return 0;
}