## Tree Terminologies

When working with trees in C programming, it's important to understand the basic terminologies that describe their parts and functions. Here are the key terms you need to know:

### Node

This is a fundamental part of a tree. A node represents a single point within the tree containing data. It can have a connection to other nodes, which are typically referred to as children.

### Root

The root node is the topmost node in a tree from which all other nodes branch out. There is only one root per tree and no other node in the tree points to the root.

### Child

A child is a node that is directly connected to another node moving away from the root. Nodes can have zero or more children. Nodes that have the same parent are called siblings.

### Parent

The converse of a child, the parent node is the one directly connected to one or more nodes below it in the tree.

### Sibling

Nodes that share the same parent are siblings. They are on the same level in the hierarchy of the tree.

### Leaf

Also known as a terminal node, a leaf is a node that does not have any children. It represents the end of a path in the tree.

### Subtree

A subtree is a portion of a tree consisting of a node and all its descendants. This can be thought of as a tree within a tree.

### Depth

The depth of a node is the number of edges from the node to the tree's root node.

### Height

The height of a node is the number of edges on the longest path from the node to a leaf. The height of the tree is the height of the root node.

### Level

The level of a node is defined by 1 + the number of connections between the node and the root. The root is at level 1.

## Representation of Binary Tree in C

In C language, a binary tree is represented using a structure definition. This representation involves creating a node structure that includes the data part and pointers to the left and right child nodes. Hereâ€™s how you can define a binary tree node in C:

```
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
```

In this structure:

- int data is where the actual data that is stored in the node goes. This can be any type of data, but here we are using an integer for simplicity.

- struct Node* left and struct Node* right are pointers to the left and right children of the node, respectively. If a child does not exist, these pointers will be set to NULL.

To create a new node, we generally use a function that allocates memory for the node, sets the data, and initializes the child pointers to NULL. Here's a simple function to create a new node:

```
Node* createNode(int value) {
Node* newNode = (Node*) malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "Out of memory\n");
exit(1);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
```

This function:

- Allocates memory for a new node using malloc.

- Checks if the memory allocation was successful.

- Initializes the node's data with the provided value.

- Sets both child pointers to NULL.

Using such nodes, you can then build the binary tree by connecting nodes appropriately. This involves setting the left and right pointers to point to other nodes in the tree.

## Need for Binary Trees

Now, letâ€™s see at some of the key reasons why binary trees is required:

### Efficient Search

Binary search trees (BSTs) provide an efficient way to search for elements. By organizing the nodes in a specific order (left subtree contains smaller values, right subtree contains larger values), the search operation can be performed in logarithmic time complexity, which is much faster than linear search in arrays or linked lists.

### Hierarchical Data Representation

Binary trees are ideal for representing hierarchical data structures. Many real-world scenarios, such as file systems, organizational charts, & HTML/XML document structures, can be naturally modeled using binary trees. The hierarchical relationship between elements can be easily captured & traversed using the parent-child connections in a binary tree.

### Sorting & Ordering

Binary search trees maintain elements in a sorted order, making them useful for sorting & ordering data. The in-order traversal of a BST visits the nodes in ascending order, allowing for efficient sorting algorithms like binary tree sort.

### Expression Parsing

Binary trees are used to represent & evaluate expressions in programming languages & mathematical formulas. The structure of an expression can be captured using a binary tree, with operators as internal nodes & operands as leaf nodes. This representation allows for easy evaluation & manipulation of expressions.

### Huffman Coding

Binary trees are used in Huffman coding, a data compression technique. Huffman coding assigns variable-length codes to characters based on their frequencies, with more frequent characters assigned shorter codes. The Huffman tree, a binary tree, is constructed based on these frequencies, enabling efficient encoding & decoding of data.

### Balanced Trees

Balanced binary trees, such as AVL trees & Red-Black trees, provide guaranteed logarithmic time complexity for search, insertion, & deletion operations. These trees automatically maintain their balance by performing rotations or color adjustments, ensuring optimal performance even in the worst case.

### Efficient Memory Utilization

Binary trees can be more memory-efficient compared to other data structures like arrays, especially when the data size is unknown or varies dynamically. The nodes in a binary tree are allocated dynamically, allowing for efficient memory utilization based on the actual number of elements stored.

## Implementation of Binary Tree in C

Implementing a binary tree in C involves creating the structure for nodes and then adding functions to insert nodes, delete nodes, and traverse the tree. Letâ€™s see how we can implement a basic binary tree:

### Define the Node Structure

As discussed in earlier sections, you start by defining a node with data and pointers to the left and right children.

```
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
```

### Create a New Node

Use a function to create new nodes. This function allocates memory for a new node, sets its data, and initializes its children to NULL.

```
Node* createNode(int data) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
```

### Insert Nodes

To insert nodes, you need a function that takes the root of the tree and the data to insert. The function places data in the correct position based on certain rules (e.g., in a binary search tree, data smaller than the parent node goes to the left, and larger data goes to the right).

```
Node* insertNode(Node* root, int data) {
if (root == NULL) { // If the tree is empty, the new node becomes the root
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data); // Insert in the left subtree
} else {
root->right = insertNode(root->right, data); // Insert in the right subtree
}
return root;
}
```

### Traverse the Tree

Traversal can be done in several waysâ€”preorder, inorder, and postorder. Here is how you can perform an inorder traversal, which prints the nodes in ascending order if itâ€™s a binary search tree.

```
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left); // Visit left subtree
printf("%d ", root->data); // Visit node itself
inorderTraversal(root->right); // Visit right subtree
}
}
```

### Free the Tree

Finally, itâ€™s important to free up the memory used by the tree when it is no longer needed. This function uses postorder traversal to free each node.

```
void freeTree(Node* root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}
```

This basic setup allows you to start working with binary trees. You can expand these functions to include more features, such as deleting nodes, finding the minimum or maximum value, or balancing the tree.

## Traversal of Binary Tree

Traversing a binary tree means visiting all the nodes in the tree in a specific order. This is crucial because the way you traverse a tree can affect what you can do with the data you collect. There are several methods to traverse a binary tree, each useful for different purposes:

### Inorder Traversal

This method visits the left subtree, the root node, and then the right subtree. It is commonly used because it gives nodes in a non-decreasing order for binary search trees.

```
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left); // Visit left subtree
printf("%d ", root->data); // Visit root node
inorderTraversal(root->right); // Visit right subtree
}
}
```

### Preorder Traversal

This method visits the root node first, followed by the left subtree, and finally the right subtree. Itâ€™s useful for creating a copy of the tree or examining the structure quickly.

```
void preorderTraversal(Node* root) {
if (root != NULL) {
printf("%d ", root->data); // Visit root node
preorderTraversal(root->left); // Visit left subtree
preorderTraversal(root->right); // Visit right subtree
}
}
```

### Postorder Traversal

This method visits the left subtree, the right subtree, and the root node last. This is useful for deleting or freeing nodes and space because you process all descendants before the node itself.

```
void postorderTraversal(Node* root) {
if (root != NULL) {
postorderTraversal(root->left); // Visit left subtree
postorderTraversal(root->right); // Visit right subtree
printf("%d ", root->data); // Visit root node
}
}
```

Each traversal method serves a different purpose, and understanding them helps you manipulate and utilize binary trees more effectively. Depending on what you need from the data structure, you might choose one method over another.

## Example: Implementation of Binary Tree in C

Let's put together all the concepts we have learned so far & implement a complete binary tree program in C. We'll create a menu-driven program that allows the user to perform various operations on a binary tree.

### C

`#include <stdio.h>`

#include <stdlib.h>

struct Node {

int data;

struct Node* left;

struct Node* right;

};

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

}

struct Node* insertNode(struct Node* root, int data) {

if (root == NULL) {

root = createNode(data);

}

else if (data <= root->data) {

root->left = insertNode(root->left, data);

}

else {

root->right = insertNode(root->right, data);

}

return root;

}

void inorderTraversal(struct Node* root) {

if (root == NULL)

return;

inorderTraversal(root->left);

printf("%d ", root->data);

inorderTraversal(root->right);

}

void preorderTraversal(struct Node* root) {

if (root == NULL)

return;

printf("%d ", root->data);

preorderTraversal(root->left);

preorderTraversal(root->right);

}

void postorderTraversal(struct Node* root) {

if (root == NULL)

return;

postorderTraversal(root->left);

postorderTraversal(root->right);

printf("%d ", root->data);

}

int main() {

struct Node* root = NULL;

int choice, value;

do {

printf("\nBinary Tree Operations\n");

printf("1. Insert a node\n");

printf("2. In-order Traversal\n");

printf("3. Pre-order Traversal\n");

printf("4. Post-order Traversal\n");

printf("0. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter the value to be inserted: ");

scanf("%d", &value);

root = insertNode(root, value);

break;

case 2:

printf("In-order Traversal: ");

inorderTraversal(root);

printf("\n");

break;

case 3:

printf("Pre-order Traversal: ");

preorderTraversal(root);

printf("\n");

break;

case 4:

printf("Post-order Traversal: ");

postorderTraversal(root);

printf("\n");

break;

case 0:

printf("Exiting the program.\n");

break;

default:

printf("Invalid choice. Please try again.\n");

}

} while (choice != 0);

return 0;

}

Output

```
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 1
Enter the value to be inserted: 5
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 1
Enter the value to be inserted: 6
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 1
Enter the value to be inserted:
8
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 2
In-order Traversal: 5 6 8
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 0
Exiting the program.
```

In this program, we define the Node structure & the necessary functions for creating a node, inserting a node into the binary tree, & performing in-order, pre-order, & post-order traversals.

The main function presents a menu to the user, allowing them to choose from different options:

**Insert a node:** Prompts the user to enter a value & inserts it into the binary tree.

**In-order Traversal: **Performs an in-order traversal of the binary tree & displays the node values.

**Pre-order Traversal: **Performs a pre-order traversal of the binary tree & displays the node values.

**Post-order Traversal: **Performs a post-order traversal of the binary tree & displays the node values.

- Exit: Terminates the program.

The program continues to prompt the user for their choice until they choose to exit.

Note -: You can further extend this program to include additional functionalities like searching for a node, deleting a node, or calculating the height of the tree, depending on your specific requirements.

## Frequently Asked Questions

### What is the time complexity of inserting an element in a binary tree?

The time complexity of inserting an element in a binary tree depends on the tree's structure. For a balanced tree, it is O(log n), whereas for an unbalanced tree, it can degrade to O(n), where n is the number of nodes.

### Can binary trees be used for sorting data?

Yes, binary trees, especially binary search trees, are commonly used for sorting data. By performing an inorder traversal on a binary search tree, you can retrieve elements in sorted order.

### How do you balance a binary tree?

Balancing a binary tree can be achieved using various tree structures like AVL trees or Red-Black trees, which automatically maintain balance through rotations and other operations during insertions and deletions.

## Conclusion

In this article, we have learned about the basics and implementation of binary trees in C. We started with understanding what binary trees are and their essential terminologies. We then discused how to represent and implement these trees in C, including node insertion and tree traversal techniques. With the help of different examples, we showed creating and manipulating a simple binary search tree, focusing on how these structures enable efficient data management and operations like searching and sorting.

You can refer to our __guided paths__ on the Coding Ninjas. You can check our course to learn more about __DSA__, __DBMS__, __Competitive Programming__, __Python__, __Java__, __JavaScript,__ etc. Also, check out some of the __Guided Paths__ on topics such as __Data Structure andAlgorithms__, __Competitive Programming__, __Operating Systems__, __Computer Networks,__ __DBMS__, __System Design__, etc., as well as some __Contests, ____Test Series__, and __Interview Experiences__ curated by top Industry.