C DSA Trees
What is a Tree?
Like a linked list, a tree stores values in nodes that are connected with pointers. But in a tree, one node can point to several nodes.
A few words you will see a lot:
- Root - the node at the top
- Child - a node directly below another node (its parent)
- Leaf - a node with no children
Binary Search Trees
In a binary tree, each node has at most two children: a left child and a right child.
A binary search tree (BST) adds one simple rule:
- Smaller values go to the left.
- Bigger values go to the right.
Check the rule yourself: every value to the left of 50 is smaller than 50, and every value to the right is bigger. The same is true for 30 and 70.
This rule makes it very fast to find values. You will see why soon!
Create a Tree Node
A tree node looks like a linked list node, but with two pointers instead of one:
Example
struct Node {
int data;
struct Node *left; // Smaller values
struct Node *right; // Bigger values
};Here is one node, with its two pointers:
Insert Values
To insert a value, start at the root:
- If the value is smaller, go left. If it is bigger, go right.
- Repeat until you find an empty spot (
NULL). - Put the new node there.
"Repeat the same steps on a smaller part" is a perfect job for recursion. The insert() function calls itself on the left or right side.
We also add a function that prints the tree in order: first everything on the left, then the node itself, then everything on the right. Watch what happens:
Example
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *createNode(int value) {
struct Node *newNode = malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct Node *insert(struct Node *root, int value) {
// Found an empty spot: put the new node here
if (root == NULL) {
return createNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value); // Go left
} else {
root->right = insert(root->right, value); // Go right
}
return root;
}
void printInOrder(struct Node *root) {
if (root == NULL) {
return;
}
printInOrder(root->left); // First, everything smaller
printf("%d ", root->data); // Then this node
printInOrder(root->right); // Then everything bigger
}
void freeTree(struct Node *root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
struct Node *root = NULL;
int values[] = {50, 70, 30, 80, 20, 60, 40};
int length = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < length; i++) {
root = insert(root, values[i]);
}
printInOrder(root);
printf("\n");
freeTree(root);
return 0;
}Result:
20 30 40 50 60 70 80 Did you see that? We inserted the values in a mixed order, but they came out sorted! That is the magic of the binary search tree rule. These seven values build exactly the tree in the picture above.
Example Explained
insert()walks left or right until it reachesNULL, and creates the new node there.printInOrder()prints the left side, then the node, then the right side. Because smaller values are always on the left, the output is sorted.freeTree()frees both children first, then the node itself. If it freed the node first, it would lose the pointers to the children.
Run the simulation below to see how the code above works, one step at a time. The green line is the pointer that just changed:
Search the Tree
Searching works just like inserting. At each node, the rule tells you which way to go, so you never have to look at the other side.
Does that sound familiar? It is the same idea as binary search: every check skips a big part of the values that are left.
The program uses the same createNode(), insert() and freeTree() functions as before. The new part is search(), which uses a simple loop and prints every node it checks:
Example
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *createNode(int value) {
struct Node *newNode = malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct Node *insert(struct Node *root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else {
root->right = insert(root->right, value);
}
return root;
}
// Returns 1 (true) if the value is in the tree
int search(struct Node *root, int value) {
struct Node *current = root;
while (current != NULL) {
printf("Checking %d\n", current->data);
if (value == current->data) {
return 1; // Found it
}
if (value < current->data) {
current = current->left; // Go left
} else {
current = current->right; // Go right
}
}
return 0; // Not found
}
void freeTree(struct Node *root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
struct Node *root = NULL;
int values[] = {50, 70, 30, 80, 20, 60, 40};
int length = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < length; i++) {
root = insert(root, values[i]);
}
if (search(root, 60)) {
printf("60 was found!\n");
} else {
printf("60 was not found.\n");
}
freeTree(root);
return 0;
}Result:
Checking 50
Checking 70
Checking 60
60 was found!Only 3 checks to find 60! In a large, well-shaped tree with 1,000,000 values, you need only about 20 checks.
Run the simulation below to see how the code above works, one step at a time. Grey nodes are the ones the search never has to look at:
Summary
- A tree stores values in nodes, and each node can have children. The top node is the root.
- In a binary search tree, smaller values go left and bigger values go right.
- Insert and search by going left or right at each node, until you find the spot or the value.
- Printing a binary search tree "in order" gives you the values sorted.
You have now seen that some ways to store and search data are much faster than others. But how do programmers measure "fast"? Find out in the next chapter!
