Build a binary search tree – Data Structures Practice

Insert n keys into an empty binary search tree, in the order given. A key that is already in the tree is ignored. Then print the keys in sorted order (an inorder traversal) and the height of the tree, counting levels: a tree with one node has height 1.

What to build

A binary search tree built by repeated insertion, and two facts about it.

Requirements

Insert the keys in the order given, ignoring a key that is already in the tree.
Print the keys in increasing order with an inorder traversal.
Print the height, counting levels.

Input

The first line has n (1 ≤ n ≤ 200). The second line has the n keys.

Output

Two lines: the keys in sorted order, separated by spaces, and the height.

Constraints

1 ≤ n ≤ 200.

Example

Input:

6
50 30 70 20 40 60

Output:

20 30 40 50 60 70
3

Why it works

Smaller keys always go left and larger keys go right, so visiting the left subtree, the node and then the right subtree meets the keys in sorted order.

Examples

Example 1 · Input

6
50 30 70 20 40 60

Expected output

20 30 40 50 60 70
3

Example 2 · Input

4
1 2 3 4

Expected output

1 2 3 4
4

Hints

Hint 1

insert(t, key): if t is NULL, malloc a new node; otherwise go left or right and set t->left or t->right to the result.

Hint 2

An inorder traversal prints the keys sorted.

Hint 3

height(NULL) is 0; otherwise 1 + the larger height of the two subtrees.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>
#include <stdlib.h>

typedef struct tree {
    int key;
    struct tree *left, *right;
} Tree;

int printed = 0;

Tree *insert(Tree *t, int key) {
    if (t == NULL) {
        Tree *n = malloc(sizeof(Tree));
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < t->key) t->left = insert(t->left, key);
    else if (key > t->key) t->right = insert(t->right, key);
    return t;
}

void inorder(Tree *t) {
    if (t == NULL) return;
    inorder(t->left);
    if (printed++ > 0) printf(" ");
    printf("%d", t->key);
    inorder(t->right);
}

int height(Tree *t) {
    if (t == NULL) return 0;
    int l = height(t->left);
    int r = height(t->right);
    return 1 + (l > r ? l : r);
}

int main(void) {
    int n;
    scanf("%d", &n);
    Tree *root = NULL;
    for (int i = 0; i < n; i++) {
        int key;
        scanf("%d", &key);
        root = insert(root, key);
    }
    inorder(root);
    printf("\n%d\n", height(root));
    return 0;
}

Lesson: Binary search trees →