Description

In this assignment, you have to find the maximum value in a binary tree.

The idea of solving this problem is to find the maximum value in the left sub-tree, find maximum in the right sub-tree, compare it with the root data and select the one that gives the maximum value. Like this,

max{root, max of left subtree, max of right subtree}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "function.h"
int idxSearch(int arr[], int strt, int end, int value)
{
    int i;
    for (i = strt; i <= end; i++)
    {
        if (arr[i] == value)
            return i;
    }
}

Node* newNode(int val)
{
    Node *node = (Node *)malloc(sizeof(Node));;
    node->data = val;
    node->left = node->right = NULL;
    return (node);
}

Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end)
{
    static int preorder_idx = 0;
    if(inorder_start > inorder_end)
        return NULL;
    Node *tree_node = newNode(preorder[preorder_idx++]);
    if(inorder_start == inorder_end)
        return tree_node;
    int inorder_idx = idxSearch(inorder, inorder_start, inorder_end, tree_node->data);
    tree_node->left = constructTree(inorder, preorder, inorder_start, inorder_idx-1);
    tree_node->right = constructTree(inorder, preorder, inorder_idx+1, inorder_end);

    return tree_node;
}

void destroyTree(Node *root)
{
    if(root != NULL)
    {
        destroyTree(root->left);
        destroyTree(root->right);
        free(root);
    }
}

int main(void)
{
    int *in, *pre, n, i;
    scanf("%d", &n);// get the size of tree
    in = (int *) malloc(n * sizeof(int));//allocate space for inorder
    pre = (int *) malloc(n * sizeof(int));// allocate space for preorder
    for(i=0; i<n; i++)// read in inorder
        scanf("%d", &in[i]);
    for(i=0; i<n; i++)// read in pre-order
        scanf("%d", &pre[i]);

    Node *root = constructTree(in, pre, 0, n-1);// construct trr
    printf("%d\n", maxValue(root));// print the max value of the tree
    destroyTree(root);// clean up
    free(in);
    free(pre);

    return 0;
}

function.h

#include <stdlib.h>
typedef struct treeNode
{
    int data;
    struct treeNode *left;
    struct treeNode *right;
} Node;

int idxSearch(int arr[], int strt, int end, int value);

Node* newNode(int val);

Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end);

void destroyTree(Node *root);

int maxValue(Node *tree);

All other function are provided. You only need to implement the function maxValue,

        int maxValue(Node *root)

        which gets the pointer of the tree root and returns the maximum value.

 

       You will be provided with main.c and function.h, and asked to implement function.c.

        For OJ submission:

        Step 1. Submit only your maxValue into the submission block. (Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

Input

The first line will have a number N with the number of tree node, second and third line are inorder and preorder of a tree respectively.

Notice that all the values are different.

Output

The maximum of a binary tree.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11359.c

Partial Judge Header

11359.h

Tags

Add Tag

Discuss