C Program to Find Maximum Distance Between Two Nodes in a Binary Tree

This C Program finds nodes which are at maximum distance in binary tree.

Here is source code of the C Program find nodes which are at maximum distance in binary tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/* 
```

 * C Program to Find Nodes which are at Maximum Distance in Binary Tree

```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct btnode
```
```
{
```
```
    int value;
```
```
    struct btnode *r,*l;
```
```
} *root = NULL, *temp = NULL;
```
```
 
```
```
void create();
```
```
void insert();
```
```
void add(struct btnode *t);
```
```
void maxdistance(struct btnode *t);
```
```
 
```

int count = 0, max = 0, v[100] = {0}, z = 0, max2, max1[100] = {0};

```
 
```
```
void main()
```
```
{
```
```
    int ch, i;
```
```
 
```

    printf("Program to find nodes at maximum distance");

```
    printf("\n  OPERATIONS ----"); 
```
```
    printf("\n1] Insert ");
```
```
    printf("\n2] Display nodes ");
```
```
    printf("\n3] Exit ");    
```
```
    while (1)
```
```
    {                        
```

        printf("\nEnter your choice : ");

```
        scanf("%d", &ch);
```
```
        switch (ch)
```
```
        {
```
```
        case 1:    
```
```
            insert();
```
```
            break;
```
```
        case 2:    
```
```
            max = 0;
```
```
            count = 0;
```
```
            maxdistance(root);
```
```
        for (i = 1; i < z; i++)
```
```
        {
```
```
            max2 = max1[0];
```
```
            if (max2 < max1[i])
```
```
                max2 = max1[i];
```
```
        }
```

        printf("Maximum distance nodes \nNodes\t Distance ");

```
        for (i = 0; i < z; i++)
```
```
        {
```
```
            if (max2 == max1[i])
```

                printf("\n %d\t  %d ",v[i],max2);

```
        }
```
```
        break;
```
```
        case 3: 
```
```
            exit(0);
```
```
        default :     
```

            printf("Wrong choice, Please enter correct choice  ");

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

/* To create a new node with the data from the user */

```
void create()
```
```
{
```
```
    int data;
```
```
 
```

    printf("Enter the data of node : ");

```
    scanf("%d", &data);
```

    temp = (struct btnode* ) malloc(1*(sizeof(struct btnode)));

```
    temp->value = data;
```
```
    temp->l = temp->r = NULL;
```
```
}
```
```
 
```

/* To check for root node and then create it */

```
void insert()
```
```
{
```
```
    create();
```
```
 
```
```
    if (root == NULL)
```
```
        root = temp;
```
```
    else
```
```
        add(root);
```
```
}
```
```
 
```

/* Search for the appropriate position to insert the new node */

```
void add(struct btnode *t)
```
```
{
```

    if ((temp->value > t->value) && (t->r!=NULL))    /* value more than root node value insert at right */

```
        add(t->r);
```

    else if ((temp->value > t->value) && (t->r==NULL))

```
        t->r = temp;
```

    else if ((temp->value < t->value) && (t->l!=NULL))   /* value less than root node value insert at left */

```
        add(t->l);
```

    else if ((temp->value < t->value) && (t->l==NULL))

```
        t->l = temp;
```
```
}
```
```
 
```

/* Function to find the max distance nodes */

```
void maxdistance(struct btnode *t)
```
```
{
```
```
    if (t->l!=NULL)
```
```
    {
```

        count++;            /* to count the number of nodes in between root and leaf */

```
        maxdistance(t->l);
```
```
    }
```
```
    if (max < count)
```
```
        max = count;
```
```
    if (max == count)
```
```
    {
```
```
        max1[z] = max;
```
```
        v[z] = t->value;
```
```
        z++;
```
```
    }
```
```
    if (t->r != NULL)
```
```
    {
```
```
        count++;        
```
```
        maxdistance(t->r);
```
```
    }
```
```
    count--;
```
```
}
```

$ cc tree19.c
$ a.out
Program to find nodes at maximum distance
OPERATIONS ----
   1] Insert 
   2] Display nodes 
   3] Exit 
   Enter your choice : 1
   Enter the data of node : 50
 
   Enter your choice : 1
   Enter the data of node : 30
 
   Enter your choice : 1
   Enter the data of node : 20
 
   Enter your choice : 1
   Enter the data of node : 40
 
   Enter your choice : 1
   Enter the data of node : 35
 
   Enter your choice : 1
   Enter the data of node : 100
 
   Enter your choice : 1
   Enter the data of node : 70
 
   Enter your choice : 1
   Enter the data of node : 120
 
   Enter your choice : 1
   Enter the data of node : 140
 
   Enter your choice : 2
   Maximum distance nodes 
   Nodes     Distance 
    35      3 
    140      3 
 
 
            50
            /\
           /  \
         30    100
         / \   / \
       20  40 70 120
           /       \
          35       140
 
    Enter your choice : 3
 
 
   $ ./a.out
 
   Program to find nodes at maximum distance
      OPERATIONS ----
   1] Insert 
   2] Display nodes 
   3] Exit 
   Enter your choice : 1
   Enter the data of node : 40
 
   Enter your choice : 1
   Enter the data of node : 20
 
   Enter your choice : 1
   Enter the data of node : 60
 
   Enter your choice : 1
   Enter the data of node : 10
 
   Enter your choice : 1
   Enter the data of node : 30
 
   Enter your choice : 1
   Enter the data of node : 80
 
   Enter your choice : 1
   Enter the data of node : 90
 
   Enter your choice : 2
   Maximum distance nodes 
      Nodes     Distance 
       90     3 
   Enter your choice : 3
 
 
 
            40
            /\
           /  \
         20    60
         / \    \
       10  30   80
                  \
                  90

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 Print Height and Depth of Binary Tree

» Next - C Program to Count Non Leaf Nodes in a Tree

Related Posts:

Check Programming Books
Practice Computer Science MCQs
Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Check Data Structure Books

Recommended Articles: