# Binary Tree Recursion

Recursion can be used to traverse a binary tree in a depth-first manner, visiting nodes in a specific order.

In this example, we'll create a simple binary tree data structure and perform an inorder traversal using recursion. An inorder traversal visits nodes in a binary tree in the order of left subtree, current node, and right subtree. This traversal is often used to print the nodes of a binary search tree.

Advertise on this site. I promise you will like the rates :)

Here's a breakdown of the key components of the example:

## 1. Binary Tree Node Structure

We define a struct TreeNode to represent a node in the binary tree. Each node contains an integer data, a pointer to the left child (left), and a pointer to the right child (right).

 ```1 2 3 4 5``` ```struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; }; ```

## 2. Creating Nodes:

The createNode function is used to create a new binary tree node with the given data. It dynamically allocates memory for the node and initializes its fields.

 ```1 2 3 4 5 6 7``` ```struct TreeNode* createNode(int data) { struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } ```

## 3. Inorder Traversal:

The inorderTraversal function performs an inorder traversal of the binary tree using recursion. It follows the left-subtree-current-node-right-subtree order.

 ```1 2 3 4 5 6 7``` ```void inorderTraversal(struct TreeNode* root) { if (root != NULL) { inorderTraversal(root->left); // Traverse left subtree printf("%d ", root->data); // Visit current node inorderTraversal(root->right); // Traverse right subtree } } ```

## 4. Main Function

In the main function, we create a sample binary tree and then perform an inorder traversal to print the values of the nodes.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15``` ```int main() { // Creating a sample binary tree struct TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); // Performing inorder traversal printf("Inorder traversal: "); inorderTraversal(root); printf("\n"); return 0; } ```

## 5. Output

When you run the program, it will create the binary tree:

```     1
/ \
2   3
/ \
4   5
```

The inorder traversal will print the values of the nodes:

```Inorder traversal: 4 2 5 1 3
```

## Conclusion

We've just demonstrated how recursion can be used to perform an inorder traversal of a binary tree, visiting nodes in a specific order. The example highlights the power and elegance of recursion in solving problems related to hierarchical data structures like binary trees.

Search this site: