Create Binary Tree

Let us create a binary tree using recursion.

Sequence of calls is shown by nos in the below figure.

We have to create a binary tree as shown below:

Let me show you a recursive create function here:

node* create()
{
        node* curr;char x;
        fflush(stdin);
        scanf("%c",&x);
        if(x==' ')                        
            return NULL;
        else
        {
            curr=(node*)malloc(sizeof(node));
            curr->data=x;
            printf("Enter left child of %c ",curr->data);
            curr->left=create();
            printf("Enter right child of %c ",curr->data);
            curr->right=create();
            return curr;
        }
}

Lets trace recursion below:

Note: Return statements are numbered to make your understanding clear.

Steps:

1.Create node A.

2.Create node B.

3.Create node C.

4.Make left pointer of C as NULL.

5.Make right pointer of C as NULL.

6.Make left pointer of B point to C.

7.Create node D.

8.Make left pointer of D as NULL.

9.Make right pointer of D as NULL.

10.Make right pointer of B point to D.

11.Make left pointer of A point to B.

12.Create node E.

13.Make left pointer of E as NULL.

14.Make right pointer of E as NULL.

15.Make right pointer of A point to E.

The binary tree is now created.