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

// Definition of the node structure
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 = newNode->right = NULL;
    return newNode;
}

// Function to insert a node in the binary tree
struct Node* insertNode(struct Node* root, int data) {
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left = insertNode(root->left, data);// Insert `30`: Since `30` is less than `50`, it becomes the left child
    else
        root->right = insertNode(root->right, data);
    return root;
}

// Function for inorder traversal
void inorderTraversal(struct Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

// Main function to test the binary tree implementation
int main() {
    struct Node* root = NULL;
    int elements[] = {50, 30, 20, 40, 70, 60, 80};
    int n = sizeof(elements) / sizeof(elements[0]);

    for (int i = 0; i < n; i++)
        root = insertNode(root, elements[i]);

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}


/*

Step-by-Step Insertion

    Insert 50:
        The tree is initially empty.
        50 becomes the root node.

50

Insert 30:

    30 is less than 50, so it becomes the left child of 50.

  50
 /
30

Insert 20:

    20 is less than 50, go left.
    20 is less than 30, so it becomes the left child of 30.

      50
     /
    30
/
20

markdown


4. **Insert 40**:
- `40` is less than `50`, go left.
- `40` is greater than `30`, so it becomes the right child of `30`.

 50
/

30
/
20 40

markdown


5. **Insert 70**:
- `70` is greater than `50`, so it becomes the right child of `50`.

 50
/  \

30 70
/
20 40

markdown


6. **Insert 60**:
- `60` is greater than `50`, go right.
- `60` is less than `70`, so it becomes the left child of `70`.

 50
/  \

30     70
/ \    /
20 40 60

markdown


7. **Insert 80**:
- `80` is greater than `50`, go right.
- `80` is greater than `70`, so it becomes the right child of `70`.

 50
/  \

30      70
/ \    /
20 40 60 80

makefile


### Final Binary Tree Structure

**Diagram:**

    50
   /  \
  30    70
 / \    / \
20 40 60 80

### Inorder Traversal

Inorder traversal of this tree will visit the nodes in ascending order: 20, 30, 40, 50, 60, 70, 80.

**Inorder Traversal Process:**

- Visit the left subtree of `50`:
  - Visit the left subtree of `30`:
    - Visit the left subtree of `20` (NULL).
    - Visit `20`.
    - Visit the right subtree of `20` (NULL).
  - Visit `30`.
  - Visit the right subtree of `30`:
    - Visit the left subtree of `40` (NULL).
    - Visit `40`.
    - Visit the right subtree of `40` (NULL).
- Visit `50`.
- Visit the right subtree of `50`:
  - Visit the left subtree of `70`:
    - Visit the left subtree of `60` (NULL).
    - Visit `60`.
    - Visit the right subtree of `60` (NULL).
  - Visit `70`.
  - Visit the right subtree of `70`:
    - Visit the left subtree of `80` (NULL).
    - Visit `80`.
    - Visit the right subtree of `80` (NULL).

This traversal sequence will print: `20 30 40 50 60 70 80`.

**Code Output:**
*/