Binary Tree in C | Introduction
For understanding this structure, we need to know the terms of it, so that we can use them truely.
Path − Path refers to sequence of nodes along the edges of a tree.
Root − Node at the top of the tree is called root. There is only one root per tree and one path from root node to any node.
Parent − Any node except root node has one edge upward to a node called parent.
Child − Node below a given node connected by its edge downward is called its child node.
Leaf − Node which does not have any child node is called leaf node.
Subtree − Subtree represents descendents of a node.
Visiting − Visiting refers to checking value of a node when control is on the node.
Traversing − Traversing means passing through nodes in a specific order.
Levels − Level of a node represents the generation of a node. If root node is at level 0, then its next child node is at level 1, its grandchild is at level 2 and so on.
keys − Key represents a value of a node based on which a search operation is to be carried out for a node.
- 1. When you need to store information that naturally forms a hierarchy. File system in computer can be an example for this
There are lots of files in computer. And also, as you know, you are allowed to create new ones into other ones. So, computer needs to know that which file is located into which file. So that it can show you the root or the wa that goes to other file that is already located into another.
Assume that you have a school project, and you located it in a folder that named “CS111” and this CS111 file is located in “School Projects” folder, and that folder is in your “D:/” drive. So the computer is showing you the way as -> D:/School Projects/CS111
This is an example to tree structure.
- 2. Trees (with some ordering e.g., BST) provide moderate access/search (quicker than Linked List and slower than arrays).
- 3. Trees provide moderate insertion/deletion (quicker than Arrays and slower than Unordered Linked Lists).
- 4. Like Linked Lists and unlike Arrays, Trees don’t have an upper limit on number of nodes as nodes are linked using pointers.
What operations can you do with your tree structure:
- 1. As mentioned above, you can search your data over it. So you can make some tricks on it to make it easier to search values.
- 2. You can manipulate the sorted list of data
- 3. You can manipulate the hierarchical data (Insertion, deletion etc.)
- 4. Router Algorithms
- 5. If it is needed, you can form of a multi-stage decision-making (like for chess kind of games)
What is Binary Tree
A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. Binary Search tree exhibits a special behaviour.
Representation of Binary Tree in C
There needs to be a pointer that points to the root of the tree. So that, we will be able to see where is the beginning. And there is one check that we need to do here, it is to check if tree is empty or not, if it is empty then value of root is NULL.
A Tree node must contain Data, Pointer to Left Child, and Pointer to Right Child.
In C, we can represent a tree node using structures. Below is an example of a tree node with an integer data.
struct TreeNode *left;
struct TreeNode *right;
As you see above, we have a tree struct that named as TreeNode, and we have data variable as integer to make some process, and also we have left and right pointers to use them to create new leaves for that tree.
Simple Tree Example Code:
Since we have above structure, now we can make an example. Assume that, we have a simple tree that has 4 nodes in it. Let’s code it.
// A struct for us to create and use nodes like this
struct node *left;
struct node *right;
// newNode() allocates a new node with the given data and NULL left and
// right pointers.
struct node* newNode(char data)
// Allocate memory for new node
struct node* node = (struct node*)malloc(sizeof(struct node));
// Assign data to this node
node->data = data;
// Initialize left and right children as NULL
node->left = NULL;
node->right = NULL;
struct node *root = newNode('o');
/* following is the tree after above statement
root->left = newNode(r);
root->right = newNode(c);
/* 'r' and 'c' become left and right children of 'o'
/ \ / \
NULL NULL NULL NULL
root->left->left = newNode(u);
/* 'u' becomes left child of r
/ \ / \
u NULL NULL NULL
Summary: Tree is a hierarchical data structure. Main uses of trees include maintaining hierarchical data, providing moderate access and insert/delete operations. Binary trees are special cases of tree where every node has at most two children.
Note: For understanding the difference between Binary Tree and Binary Search Tree, read this.