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.



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: