How to Create a Binary Tree in C

By Techwalla Internet Editor

Binary trees in C are a good way to dynamically organize data for easy searching. However, they require a lot of work to maintain.

Create the Binary Tree

Step 1

Structure your binary tree. Every binary tree will need a structure, even if it only has one variable. Choose a name, then use typedef to create it:

typedef struct student_data STUDENT_DATA;

Step 2

Define the structure. Include two pointers to the same structure:

struct student_data {
int student_ID;
int student_grade;
STUDENT_DATA *left, *right;
};

Step 3

Allocate a pointer to this data structure, initializing it to NULL, to be the tree's head:

STUDENT_DATA *students = NULL;

Add to the Binary Tree

Step 1

Allocate two temporary pointers to the data structure:

STUDENT_DATA *new_student, *cur_student;

Step 2

Use malloc() to create a new element, always checking for an error:

if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) { abort(); }

Step 3

Populate the new element's fields. Set its left and right fields to NULL:

new_student->student_ID = newID;
new_student->student_size = newsize;
new_student->left = NULL;
new_student->right = NULL;

Step 4

Consider the head variable. If the head variable is NULL, this is the first element added to the tree, so set the head variable to point to it, and you're done:

if (!students) { students = new_student; return; }

Step 5

Start at the top of the tree:

cur_student = students;
while (cur_student) {

Step 6

Handle the duplicate entry if the new value and current value are equal:

 if (newID == cur_student->student_ID) { abort(); }

Step 7

Deal with unequal values. If the new value is less than the current value, the new element goes on the left. Add it immediately if there's nothing on the left. Otherwise, traverse left and loop:

 if (newID < cur_student->student_ID) {
if (cur_student->left == NULL) {
cur_student->left = newstudent;
return 1;
}
cur_student = cur_student->left;

Step 8

Do the same thing on the right, otherwise:

 } else {
if (cur_student->right == NULL) {
cur_student->right = newstudent;
return 1;
}
cur_student = cur_student->right;
}
}

Search the Binary Tree

Step 1

Create a temporary variable pointing to the data structure:

STUDENT_DATA *cur_student;

Step 2

Set your temporary variable to the head variable:

cur_student = students_head;

Step 3

Loop through the elements, checking for the desired value:

while (cur_student) {
if (cur_student->student_ID == 15) { return cur_student->student_grade; }

Step 4

Branch left or right, and loop, if it's not found:

 if (cur_student->student_ID < 15) {
cur_student = cur_student->right;
} else {
cur_student = cur_student->left;
}

Step 5

See if the loop ends. If it does, it means you never found the item:

}
return 0;

Clean Up

Step 1

Deallocate the binary tree when your program ends, as not all operating systems will handle this automatically. This is best done using a recursive function:

void deallocate_binary_tree(STUDENT_DATA *tree) {

Step 2

Observe: If there isn't any tree, there's nothing to do:

 if (!tree) return;

Step 3

Deallocate the left and right subtrees recursively:

 deallocate_binary_tree(tree->left);
deallocate_binary_tree(tree->right);

Step 4

Deallocate the element, and you're done:

 free(tree);
}

Tips & Warnings

  • Searching and adding to binary trees can also be done using recursion. This will be much easier to write and maintain, but a little harder to understand, until you get used to it.
  • It's common to create a binary tree that contains only pointers into a second C data structure, often an array or linked list, where the actual data resides. Each binary tree is an index to quickly search a single field of the list data.
  • Deleting from a binary tree is a very complicated algorithm in C, but in many uses of binary trees, elements are never deleted.