C Program to Find Maximum Value in Tree using Inorder Traversal

This is a C Program for finding the largest value in a Binary Search Tree using Inorder traversal.

Problem Description

We have to write a C program to find the largest value in a Binary Search Tree using Inorder traversal.

Expected Input and Output

Case 1. Balanced Tree:When the weight is equal on both the sides of root.

                    25
                  /    \  
                 17     35   
                / \     / \ 
              13  19   27 55

Output:
Inorder traversal of tree 1 : 13 17 19 25 27 35 55
Largest value is 55

Case 2. Right Skewed Tree:When the nodes at every level just have a right child.

Output:
Inorder traversal of tree 2 : 1 2 3 4 5
Largest value is 5

Case 3. Tree having just one node

Output:
Inorder traversal of tree 3 : 15
Largest value is 15

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Problem Solution

1. In binary search tree, the left child of a node is always smaller than it’s parent while the right child is always greater than it’s parent.
2. In Inorder traversal we traverse the left subtree then we print the values of the nodes and then we traverse the right subtree.
3. As mentioned above that for a Binary Search Tree, the left child of a node is always smaller and right child is always greater than it’s parent, if we traverse a tree using inorder traversal, we are going to get a sequence of nodes arranged in ascending order of their values.
4. So the largest value of a BST using inorder traversal will be the value of the last node traversed, because the output of inorder traversal gives nodes arranged in ascending order if the tree is a Binary Search Tree(BST).

Program/Source Code

Here is source code of the C Program for finding the largest node in a Binary Search Tree using Inorder traversal . The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on windows 10. The program output is also shown below.

```
/*
```

 * C Program for finding the largest node

 * in a Binary Search Tree using  Inorder Traversal

```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node *left, *right;
```
```
};
```
```
struct node *createnode(int key)
```
```
{
```

    struct node *newnode = (struct node*)malloc(sizeof(struct node));

```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
    return(newnode);
```
```
}
```
```
void inorder(struct node *root)
```
```
{
```
```
    if(root != NULL)
```
```
    {
```
```
        inorder(root->left);
```
```
        printf(" %d ",root->info);
```
```
        inorder(root->right);
```
```
    }
```
```
}
```
```
void largest(struct node *root)
```
```
{
```

    while (root != NULL && root->right != NULL)

```
    {
```
```
        root = root->right;
```
```
    }
```

    printf("\nLargest value is %d\n", root->info);

```
}
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
int main()
```
```
{
```
```
    /* Creating first Tree. */
```

    struct node *newnode = createnode(25);

```
    newnode->left = createnode(17);
```
```
    newnode->right = createnode(35);
```

    newnode->left->left = createnode(13);

    newnode->left->right = createnode(19);

    newnode->right->left = createnode(27);

    newnode->right->right = createnode(55);

```
    /* Sample Tree 1:
```
```
     *               25
```
```
     *             /    \
```
```
     *            17     35
```
```
     *           / \     / \
```
```
     *         13  19   27 55
```
```
     */
```

    printf("Inorder traversal of tree 1 :");

```
    inorder(newnode);
```
```
    largest(newnode);
```
```
 
```
```
    /* Creating second Tree. */
```
```
    struct node *node = createnode(1);
```
```
    node->right = createnode(2);
```
```
    node->right->right = createnode(3);
```

    node->right->right->right = createnode(4);

    node->right->right->right->right = createnode(5);

    /* Sample Tree 2:   Right Skewed Tree (Unbalanced).

```
     *               1
```
```
     *                \
```
```
     *                 2
```
```
     *                  \
```
```
     *                   3
```
```
     *                    \
```
```
     *                     4
```
```
     *                      \
```
```
     *                       5
```
```
     */
```

    printf("\nInorder traversal of tree 2 :");

```
    inorder(node);
```
```
    largest(node);
```
```
 
```
```
    /* Creating third Tree. */
```
```
    struct node *root = createnode(15);
```

    /* Sample Tree 3- Tree having just one root node.

```
     *              15
```
```
     */
```

    printf("\nInorder traversal of tree 3 :");

```
    inorder(root);
```
```
    largest(root);
```
```
    return 0;
```
```
}
```

Program Explanation

Program contains three important functions.

1. createnode(key);
This function helps to create a new node by allocating it a memory dynamically. It has just one parameter which is “key” which assigns value to the node thereby creating a fresh node having left and right child as “NULL”.

2. inorder(struct node *root);
This function helps to traverse the whole tree. First we recursively traverse the left subtree, then print the value of the node and then we recursively traverse the right subtree.

3. largest(struct node *root)
(a). Inorder traversal of a BST gives a sequence of nodes arranged in increasing order of their values because in BST the left child of a node is always smaller and the right child of a node is always greater than it’s parent.
(b). So the largest node in a BST will be the last node in the right subtree.
(c). That is what we are doing in largest() function, we are making the root = root->right so that we can reach the extreme right node or the last node in a right subtree.
(d). The last node in a right subtree will not have any child, therefore the while condition is going to terminate as root->right will become = NULL.

Runtime Test Cases

Inorder traversal of tree 1 : 13  17  19  25  27  35  55
Largest value is 55
 
Inorder traversal of tree 2 : 1  2  3  4  5
Largest value is 5
 
Inorder traversal of tree 3 : 15
Largest value is 15

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.

« Prev - C Program to Create a Mirror Copy of a Tree and Display using BFS Traversal

» Next - Singly Linked List Program in C

Related Posts:

Recommended Articles: