Inverting a binary tree in C
Fri, Mar 11 2022
Messing around with trees is fun. Messing around with trees in C must be, therefore, by definition, double fun. In this article, I will show you how to invert a binary tree in C and, hopefully, teach you a thing or two.
Prerequisites
Some knowledge of C pointers, recursion, and an understanding of what a tree data structure is.
What is a binary tree?
A binary tree is a type of tree that has at most two child nodes. We refer to these child nodes as the left child and the right child.
Fig 1: An example of a binary tree.
Fig 2: Another example of a binary tree.
Like all tree data structures, a binary tree can be defined recursively. This recursive attribute hints at a solution to the problem of inverting a binary tree. But...
What does it mean to "invert" a binary tree?
To put it simply, inverting a binary tree means creating its mirror image. More formally, it means swapping the children of each of its non-leaf nodes. Therefore, the left child of a node will take the place of the right child and vice-versa.
Fig 3: The result of inverting a binary tree. The only node that remained in it's original place is the root node. Children of each non-leaf node got swapped.
The algorithm
One way to invert a binary tree is to use the power of recursion. Every node contains a value (in our case, an integer) and two pointers, one for each of the node's children. Our algorithm will begin at the root node.
First, we will check whether the current node exists. This might seem counter-intuitive, but bear with me. If it doesn't exist
(this will be expressed in C as the node being equal to NULL), we are done inverting.
Fulfilling this condition will be the base case for our recursive calls.
If the current node exists (i.e. it's not NULL), we swap its left child for its right child.
We then perform the above steps recursively on both of the node's children.
(Don't worry, the notion of a node's existence or nonexistence will become clearer once you see the code.)
The code
We will now gradually build the program. If you only care about the finished product, you can find it at the bottom of this page.
Boilerplate
We will start with the usual C boilerplate, defining the main function:
int main(void) {
return 0;
}
Nodes
To represent our tree's nodes, we will define a struct named node.
Let's put it outside the main function:
struct node {
int value;
struct node* left;
struct node* right;
};
int main(void) {
return 0;
};
Notice that our struct is self-referential.
That means that it contains one or more pointers to a struct of the same kind.
We will name these pointers left and right. As you could've guessed, they represent the node's child nodes.
Having our struct point to two instances of itself establishes the recursive nature of trees, that we've mentioned before.
To make our sruct easier to work with, we will "wrap" it inside a typedef.
This will allow us to give the struct a new name. We will call it Node (note the capital N):
typedef struct node {
int value;
struct node* left;
struct node* right;
} Node;
int main(void) {
return 0;
};
This way, we won't need to refer to the node struct with its "full" name when creating a new node.
We won't need to create a new node like this:
struct node* root = create_node(value);
Instead, we can create it this way:
Node* root = create_node(value);
This will save us a lot of typing down the line.
Creating the nodes
We will now define a function that will be responsible for creating the nodes of our binary tree.
It looks like this:
Node* create_node(int value) {
// Allocate enough memory for our node struct
Node* n = malloc(sizeof(Node));
// Exit if the allocation failed
if (n == NULL) {
printf("Memory allocation failed");
exit(1);
}
// Populate the node with values and return it
n->value = value;
n->left = NULL;
n->right = NULL;
return n;
}
Note that the function allocates memory dynamically using malloc.
Should the allocation fail for any reason, the program prints an error message and exits.
However, functions like malloc, printf and exit aren't
built-in to C. We have to include their prototype declarations from their respective header files.
(The same holds true for the symbolic constant NULL.)
Let's include the headers then. Our code will then look like this:
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node* left;
struct node* right;
} Node;
Node* create_node(int value) {
// --snip--
}
int main(void) {
return 0;
};
Other than allocating memory and checking for allocation errors, the create_node function doesn't do anything magical.
It populates the Node with the value from the function's arguments list,
creates the Node's children and returns the Node to the callee.
Inverting the tree
Now it's time to write a function that will invert the binary tree. As mentioned before, it will use the power of recursion.
It will take a Node as its argument and will call itself recursively on the Node's children.
This is how it looks:
void invert_tree(Node* node) {
// Check whether the node "exists"
if (node == NULL) {
return;
}
// Swap left and right children
Node* temp = node->left;
node->left = node->right;
node->right = temp;
// Recursively call the function on both children
invert_tree(node->left);
invert_tree(node->right);
}
This function does all the steps we've discussed in the algorithm section of this tutorial.
It checks whether the current node is NULL.
Then it swaps the left and right children, using pointers.
After that, the function calls itself on the left and right children of the current node.
Putting it all together
Let's now create a binary tree and then invert it, just like we've seen in Fig 3.
To create a binary tree, we will use this approach:
int main(void) {
// Create the tree
Node* root = create_node(3);
root->left = create_node(2);
root->right = create_node(5);
root->left->left = create_node(1);
root->left->right = create_node(6);
root->right->left = create_node(7);
root->right->right = create_node(4);
return 0;
}
We will invert the tree by calling the invert_tree function:
int main(void) {
// Create the tree
// --snip--
invert_tree(root);
return 0;
}
To check the result of the inversion, we can print the tree. To do that, we will use a print_tree function
that I've found somewhere on the internet (and then modified it to my liking):
void print_tree(Node* root, int space) {
if (root == NULL)
return;
space += 3;
// Print the right child first, recursively
print_tree(root->right, space);
// Print spaces to signify recursion depth
for (int i = 3; i <= space; i++) {
printf(" ");
}
// Print the root value
printf("%d\n", root->value);
// Print the left child, recursively
print_tree(root->left, space);
}
Now we can call the print_tree function from the main function:
int main(void) {
// Create the tree
// --snip--
printf("Before the inversion:\n");
print_tree(root, 0);
printf("\n");
invert_tree(root);
printf("After the inversion:\n");
print_tree(root, 0);
return 0;
}
Let's compile the program with the following command:
gcc whatever_you_named_your_file.c
And execute the program by running ./a.out. You should see the following output:
Before the inversion:
4
5
7
3
6
2
1
After the inversion:
1
2
6
3
7
5
4
Cleaning up
Now it's time to free the dynamically allocated memory. Once again,
we will harness the power of recursion. The function that will perform the task looks like this:
void free_memory(Node* root) {
if (root == NULL) {
return;
}
free_memory(root->left);
free_memory(root->right);
free(root);
}
We will call it before the return statement of the main function:
int main(void) {
// --snip--
free_memory(root);
return 0;
}
The end product
The whole program looks like this:
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node* left;
struct node* right;
} Node;
Node* create_node(int value) {
// Allocate enough memory four our node struct
Node* n = malloc(sizeof(Node));
// Exit if the allocation failed
if (n == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
// Populate the node with values and return it
n->value = value;
n->left = NULL;
n->right = NULL;
return n;
}
void invert_tree(Node* node) {
// Check whether the node "exists"
if (node == NULL) {
return;
}
// Swap left and right children
Node* temp = node->left;
node->left = node->right;
node->right = temp;
// Recursively call the function on the children
invert_tree(node->left);
invert_tree(node->right);
}
void print_tree(Node* root, int space) {
if (root == NULL)
return;
space += 3;
// Print the right child first, recursively
print_tree(root->right, space);
// Print spaces to signify recursion depth
for (int i = 3; i <= space; i++) {
printf(" ");
}
// Print the root value
printf("%d\n", root->value);
// Print the left child, recursively
print_tree(root->left, space);
}
void free_memory(Node* root) {
if (root == NULL) {
return;
}
free_memory(root->left);
free_memory(root->right);
free(root);
}
int main(void) {
// Create the tree
Node* root = create_node(3);
root->left = create_node(2);
root->right = create_node(5);
root->left->left = create_node(1);
root->left->right = create_node(6);
root->right->left = create_node(7);
root->right->right = create_node(4);
// Print the tree before inverting it
printf("Before inversion:\n");
print_tree(root, 0);
printf("\n");
invert_tree(root);
// Print the tree after inverting it
printf("After inversion:\n");
print_tree(root, 0);
free_memory(root);
return 0;
}
Conclusion
I hope this tutorial was understandable enough and that you've learned something from it. Stay curious!