Preorder Traversal of Binary Tree

#include <stdio.h>
#include <stdlib.h>

// Define the structure of a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
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;
}

// Function for Preorder Traversal
void preorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }

    // Visit the root node first
    printf("%d ", root->data);

    // Traverse the left subtree
    preorderTraversal(root->left);

    // Traverse the right subtree
    preorderTraversal(root->right);
}

int main() {
    // Manually creating the binary tree
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);

    // Print Preorder Traversal
    printf("Preorder Traversal of the binary tree is: ");
    preorderTraversal(root);

    return 0;
}

Explanation:

1. Struct Definition:
   • struct Node represents a node in the binary tree. Each node has data, left, and right.
   • The createNode function allocates memory for a new node, assigns it the given data, and sets its left and right pointers to NULL.
2. Preorder Traversal Function:
   • preorderTraversal is a recursive function that performs the preorder traversal.
   • It first prints the data of the current node.
   • It then calls itself with root->left to traverse the left subtree.
   • After that, it calls itself with root->right to traverse the right subtree.
3. Building the Tree:
   • The main function builds a binary tree by creating nodes and linking them as shown in the example.
4. Output:
   • When preorderTraversal is called with root, it prints the values in preorder.

Output of the Program

When you run the program, the output will be:

Preorder Traversal of the binary tree is: 1 2 4 5 3 6

How the Program Works

• The root node (1) is visited first and printed.
• Then the left subtree of 1 (rooted at 2) is traversed:
  • 2 is visited.
  • Its left child 4 is visited.
  • Its right child 5 is visited.
• After that, the right subtree of 1 (rooted at 3) is traversed:
  • 3 is visited.
  • Its right child 6 is visited.

Thus, the traversal sequence is 1 2 4 5 3 6.