Binary Search Tree - Starting with lists

[ Personal detail: I want to share the things that I truly think are clever little designs, but if they're not and I'm stupid, then at least I learned about the greater scope of it all. ]

Binary Search Trees

Let's start from the top and work down:

A Binary Search Tree is a data structure centered around the concept of nodes, or structures which contain data and links to other structures. This concept is the driving force of a similar, more simple object as well, the list, more specifically -- a singly-linked list.

Linked Lists

Lets walk through an imaginary linked list and then describe it in code. First we must create our structure to hold data and our links to other structures. In our diagram, we can represent that structure with brackets:

[data,link]

With the definition we have so far a structure pointing to another structure is represented as:

[data,[data,link]]

However, that isn't quite accurate. The links are storing the location of the next structure, so it makes sense to use a more meaningful representation:

[data]->[data]

In that representation, we could walk through a list by following the links sequentially:

[H]->[e]->[l]->[l]->[o]

We do this by following each link to the next node, then following it's link, and so on. In theory, it is a simple idea, but it is the root of so many more complexities.

Now the C code:

(Only the relevant parts of a list)

typedef struct node_t { 
    int data;                                   
    struct node_t * next;                       
} node;


int traverse_forward(node * head, int (*action)(int value)){
    if(head == NULL){
        return -1;
    }
    
    while(head->next != NULL){               
        action(head->data);                  
        head->next = head->next->next; 
    }
}

Comments by line:

1 : This is the definition of the structure which holds our data and link.
2 : It holds a single int variable as our data;
3 : This is a pointer to another structure, this is what gives our list it's properties.

12: While we aren't at the end of the list:
13: Do an action with our data;
14: Go to the next link;

Next Time...

In the following post, I will describe the BST in C++ and break down the algorithm for inserting a node. (This is, after all, the algorithm that shapes the list into a tree.)