C Program to Find the Common Ancestor and Path

This C Program Finds the Common Ancestor and Print the Path.

Here is source code of the C Program to Find the Common Ancestor and Print the Path. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C Program to Find the Common Ancestor and Print the Path

```
 *
```
```
 *                       10
```

 *                       /  \

```
 *                      7    15
```
```
 *                     / \   / \
```
```
 *                    6   8 12  18
```
```
 *                   /     \
```
```
 *                  5         9
```
```
 *               (Given Binary tree) 
```
```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct btnode
```
```
{
```
```
    int value;
```
```
    struct btnode *l;
```
```
    struct btnode *r;
```
```
};
```
```
 
```
```
typedef struct btnode N;
```
```
 
```
```
N* new(int);
```
```
int count;
```
```
 
```
```
void create();
```
```
void preorder(N *t);
```
```
void ancestor(N *t);
```
```
int search(N *t, int, int);
```
```
void path(int, int, int);
```
```
 
```
```
N *root = NULL;
```
```
 
```
```
void main()
```
```
{
```
```
    int choice;
```
```
 
```
```
    create();
```
```
    while (1)
```
```
    {
```
```
        printf("Enter the choice\n");
```

        printf("1-Display : 2-path : 3-Exit\n");

```
        scanf("%d", &choice);
```
```
        switch (choice)
```
```
        {
```
```
        case 1:
```

            printf("preorder display of tree elements\n");

```
            preorder(root);
```
```
            printf("\n");
```
```
            break;
```
```
        case 2:
```
```
            ancestor(root);    
```
```
            break;
```
```
        case 3:
```
```
            exit(0);
```
```
        default:
```

            printf("Enter the right choice\n");

```
        }
```
```
    }
```
```
}
```
```
 
```
```
/* creating temporary node */
```
```
N* new(int data)
```
```
{
```
```
    N* temp = (N*)malloc(sizeof(N));
```
```
    temp->value = data;
```
```
    temp->l = NULL;
```
```
    temp->r = NULL;
```
```
 
```
```
    return(temp);
```
```
}
```
```
 
```
```
/* Creating the binary search tree */
```
```
void create()
```
```
{
```
```
    root = new(10);
```
```
    root->l = new(7);
```
```
    root->r = new(15);
```
```
    root->l->l = new(6);
```
```
    root->l->r = new(8);
```
```
    root->r->l = new(12);
```
```
    root->r->r = new(18);
```
```
    root->r->r->r = new(20);
```
```
    root->l->l->l = new(5);
```
```
    root->l->r->r = new(9);
```
```
}
```
```
 
```

/* To display the preorder traversal of the tree */

```
void preorder(N *temp)
```
```
{
```
```
        printf("%d->", temp->value);
```
```
        if (temp->l != NULL)
```
```
            preorder(temp->l);
```
```
        if (temp->r != NULL)
```
```
            preorder(temp->r);
```
```
}
```
```
 
```

/* to find common ancestor for given nodes */

```
void ancestor(N *temp)
```
```
{
```
```
    int a, b, anc = 0;
```
```
    count = 0;
```
```
 
```

    printf("enter two node values to find common ancestor\n");

```
    scanf("%d", &a);
```
```
    scanf("%d", &b);
```
```
    count = search(root, a, b);
```
```
    if (count  == 2)
```
```
    {
```

        while (temp->value != a && temp->value != b)

```
        {
```

            if ((temp->value > a)&&(temp->value > b))

```
            { 
```
```
                anc = temp->value;
```
```
                temp = temp->l;
```
```
            }
```

            else if ((temp->value < a)&&(temp->value < b))

```
            {
```
```
                anc = temp->value;
```
```
                temp = temp->r;
```
```
            }
```

            else if ((temp->value > a)&&(temp->value < b))

```
            {
```

                anc = temp->value;

                printf("anc = %d\n", anc);

```
                break;
```
```
            }
```

            else if ((temp->value < a)&&(temp->value > b))

```
            {
```
```
                anc = temp->value;
```
```
                temp = temp->r;    
```
```
            }
```
```
            else
```
```
            {
```

                printf("common ancestor = %d\n", anc);

```
                break;
```
```
            }
```
```
        }
```
```
    path(anc, a, b);
```
```
    }
```
```
    else
```

        printf("enter correct node values & do not enter root value\n");

```
}
```
```
 
```

/* to find whether given nodes are present in tree or not */

```
int search(N *temp, int a, int b)
```
```
{
```

    if ((temp->value  == a ||temp->value  == b)&& (root->value != a&&root->value != b))

```
    {
```
```
        count++;        
```
```
    }
```
```
    if (temp->l != NULL)
```
```
        search(temp->l, a, b);
```
```
    if (temp->r != NULL)
```
```
        search(temp->r, a, b);
```
```
    return count;
```
```
}
```
```
 
```

/* to print the path ancestor to given nodes */

```
void path(int anc, int c, int b)
```
```
{
```
```
    N *temp = NULL;
```
```
    int i = 0, a[2];
```
```
    a[0] = c;
```
```
    a[1] = b;
```
```
 
```
```
    for (;i < 2;i++)
```
```
    {
```

        if (anc == root->value)    // If ancestor is root

```
        {
```
```
            temp = root;
```
```
            while (1)
```
```
            {
```

                printf("%d", temp->value);

```
                if (a[i] < temp->value)
```
```
                    temp = temp->l;
```

                else if (a[i] > temp->value)

```
                    temp = temp->r;
```
```
                else
```
```
                {
```

                    if (a[i] == temp->value)

```
                    {
```
```
                        break;
```
```
                    }
```
```
                }
```
```
                printf("->");
```
```
            }
```
```
            printf("\n");
```
```
        }
```

        else if (anc < root->value)    //If ancestor is less than the root value

```
        {
```
```
            temp = root;
```
```
            while (temp != NULL)
```
```
            {
```
```
                if (anc < temp->value)
```
```
                    temp = temp->l;
```

                else if (anc > temp->value)

```
                    temp = temp->r;
```
```
                else
```
```
                {
```
```
                    while (1)
```
```
                    {
```

                        if (a[i] < temp->value)

```
                        {
```

                            printf("%d->", temp->value);

                            temp = temp->l;

```
                        }
```

                        else if (a[i] > temp->value)

```
                        {
```

                            printf("%d->", temp->value);

                            temp = temp->r;

```
                        }
```
```
                        else
```
```
                        {
```

                            printf("%d\n", temp->value);

```
                            break;
```
```
                        }
```
```
                    }
```
```
                }
```
```
            }
```
```
        }
```

        else //If ancestor greater than the root value

```
        {
```
```
            temp = root;
```
```
            while (temp != NULL)
```
```
            {
```
```
                if (anc > temp->value)
```
```
                    temp = temp->r;
```

                else if (anc < temp->value)

```
                    temp = temp->l;
```
```
                else
```
```
                {
```
```
                    while (1)
```
```
                    {
```

                        if (a[i] < temp->value)

```
                        {
```

                            printf("%d->", temp->value);

                            temp = temp->l;

```
                        }
```

                        else if (a[i] > temp->value)

```
                        {
```

                            printf("%d->", temp->value);

                            temp = temp->r;

```
                        }
```
```
                        else
```
```
                        {
```

                            printf("%d\n", temp->value);

```
                            break;
```
```
                        }
```
```
                    }
```
```
                }
```
```
            }
```
```
        }
```
```
    }
```
```
}
```

$ cc tree33.c
$ a.out
Enter the choice
1-Display : 2-path : 3-Exit
1
preorder display of tree elements
10->7->6->5->8->9->15->12->18->20
Enter the choice
1-Display : 2-path : 3-Exit
2
enter two node values to find common ancestor
6
8
anc = 7
7->6
7->8
Enter the choice
1-Display : 2-path : 3-Exit
2
enter two node values to find common ancestor
7
20
anc = 10
10->7
10->15->18->20
Enter the choice
1-Display : 2-path : 3-Exit
2
enter two node values to find common ancestor
12
20
anc = 15
15->12
15->18->20
Enter the choice
1-Display : 2-path : 3-Exit
2
enter two node values to find common ancestor
15
20
10->15
10->15->18->20
Enter the choice
1-Display : 2-path : 3-Exit
3

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Convert Sorted Array to Balanced BST

» Next - C Program to Find the Sum of All Nodes in a Binary Tree

Related Posts:

Recommended Articles: