# 50029. Tree Construction

## Problem Description

Construct a binary tree in a level-by-level fashion. You will be given an array of n elements, and you will construct a tree with root having array[0] as the level, which has array[1] as it left child, and array[2] as its right child, and so on. Your function should return a pointer to the root of the constructed tree.

Node *construct(int array[], int n);


The definition of a Node is as follows.

### tree.h

#ifndef _TREE_H#define _TREE_H typedef struct Node {    int label;    struct Node *left, *right;} Node; Node* construct(int array[], int n); #endif


• 5pt. $n = 1$
• 5pt. $n = 2$
• 10pt. $n = 3$
• 30pt. $n$ is no more than $100$.
• 50pt. $n$ is no more than $1000$.

## Hint

It is easy to see that the left child of array[i] is array[2 * i + 1] and the right child is array[2 * i + 2], so it is easy to construct the tree recursively.

p10071

p10071

## main.c (test)

12345678910111213141516171819202122#include <stdio.h>#include "tree.h" void printAndFree(Node *u) {    if (u == NULL)    return ;    printf("%d ", u->label);    printAndFree(u->left);    printAndFree(u->right);    free(u);} int main() {    int A[32767], n;    while (scanf("%d", &n) == 1 && n != 0) {        for (int i = 0; i < n; i++)            scanf("%d", &A[i]);        Node *root = construct(A, n);        printAndFree(root);        puts("");    }    return 0;}


## Sample Input

1831 3 281 2 3 7 5 1 1 6


## Sample Output

8 1 3 2 1 2 7 6 5 3 1 1