Opgaver og løsninger
Datastrukturer og Dataabstraktion

Title: Pelle Erobreren
Year: 1910
University text book: no

Title: Ditte Menneskebarn
Year: 1917
University text book: no

Title: The C Programming Language
Year: 1988
University text book: yes

Title: C by Disssection
Year: 2001
University text book: yes

Title: Problem Solving and Program Design in C
Year: 2010
University text book: yes

#include <stdio.h>
#include <string.h>
#define MAX_BOOKS 10

struct book {
  char *title, *author, *publisher;
  int publishing_year;
  int university_text_book;
};

typedef struct book book;

book make_book(char *title, char *author, char *publisher, 
               int year, int text_book){
  book result;
  result.title = title; result.author = author;
  result.publisher = publisher; result.publishing_year = year;
  result.university_text_book = text_book;
 
  return result;
}

void prnt_book(book b){
  char *yes_or_no;

  yes_or_no = (b.university_text_book ? "yes" : "no"); 
  printf("Title: %s\n"
         "Author: %s\n"
         "Publisher: %s\n"
         "Year: %4i\n"
         "University text book: %s\n\n",
         b.title, b.author, b.publisher, 
         b.publishing_year, yes_or_no);
}

int book_compare_by_title(const void *book1, const void *book2){
  return strcmp( ((book *)book1)->title, ((book *)book2)->title);
}

// A compare function for booleans represented as integers, following the conventions in C.
// false (0) is less than true (non-zero).
int compare_boolean_integers(int b1, int b2){
  if (b1 == 0 && b2 != 0)
    return -1;       // b1 < b2
  else if (b1 != 0 && b2 == 0)
    return 1;        // b1 >  b2
  else 
    return 0;        // b1 and b2 are equal (in the boolean sense).
}

// A natural integer compare function:
int compare_integers(int i1, int i2){
  if (i1 < i2)
    return -1;
  else if (i1 == i2)
    return 0;
  else return 1;
}

int book_compare_by_kind_and_year(const void *book1, const void *book2){
  int uni_book_1 = ((book *)book1)->university_text_book,
      uni_book_2 = ((book *)book2)->university_text_book,
      y1 =         ((book *)book1)->publishing_year,
      y2 =         ((book *)book2)->publishing_year,

      kind_compare = compare_boolean_integers(uni_book_1, uni_book_2);

  if (kind_compare != 0)                // books of different kinds
     return kind_compare;               // boolean 0 (kind not text books) before boolean 1 (text books).
  else
     return compare_integers(y1, y2);   // order by publishing year
}

void sort_books_by_title(book shelf[], int last){
  qsort(shelf, last+1, sizeof(book), book_compare_by_title);
}

void sort_books_by_kind_and_year(book shelf[], int last){
  qsort(shelf, last+1, sizeof(book), book_compare_by_kind_and_year);
}

int main(void) {
  book shelf[MAX_BOOKS];
  int i;

  shelf[0] =
    make_book("Problem Solving and Program Design in C", "Hanly and Koffman", 
              "Pearson", 2010, 1);   

  shelf[1] =
    make_book("C by Disssection", "Kelley and Pohl", 
              "Addison Wesley", 2001, 1);   

  shelf[2] =
    make_book("The C Programming Language", "Kernighan og Ritchie", 
              "Prentice Hall", 1988, 1);   

  shelf[3] =
    make_book("Pelle Erobreren", "Martin Andersen Nexoe",
              "Gyldendal", 1910, 0);

  shelf[4] = shelf[3];
  shelf[4].title = "Ditte Menneskebarn"; 
  shelf[4].publishing_year = 1917;

//  sort_books_by_title(shelf, 4);
  sort_books_by_kind_and_year(shelf, 4);

  for(i = 0; i <=4; i++)
    prnt_book(shelf[i]);
  
  return 0;
}

int book_compare_by_kind_and_year(const void *book1, const void *book2){
  int uni_book_1 = ((book *)book1)->university_text_book,
      uni_book_2 = ((book *)book2)->university_text_book,
      y1 =         ((book *)book1)->publishing_year,
      y2 =         ((book *)book2)->publishing_year;

  if (uni_book_1 == 0 && uni_book_2 == 1)
       return -1;        //  book1 is not a text book, book2 is a text book. book1 comes before book2. Therefore -1
  else if (uni_book_1 == 1 && uni_book_2 == 0)
       return 1;
  else if (y1 < y2)      // both book are of the same kind. Then order by publishing year:
       return -1;
  else if (y1 > y2)
       return 1;
  else return 0;
}

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

#define DATE_MAX 1000

/* Date related types */
enum weekday {sunday, monday, tuesday, wednesday, thursday, 
           friday, saturday};
typedef enum weekday weekday;

struct date {
  weekday day_of_week;
  int day;
  int month;
  int year;
};

typedef struct date date;

/* Funktion prototypes */

int leapYear(int);
int date_before(date, date);
weekday next_day_of(weekday);
void prnt_date(date);
char *name_of_weekday(date);
date tomorrow(date);

int main(void) {
  date calendar[DATE_MAX];
  char ignore;

  date first_date = {tuesday, 17, 11, 2015},
       last_date  = {thursday, 17, 11, 2016},
       current_date;
  int i = 0, j = 0;

  current_date = first_date;
  while (date_before(current_date, last_date)){
    calendar[i] = current_date;
    current_date = tomorrow(current_date);
    i++;
  }

 for (j = 0; j < i; j++){
    if (j % 20 == 0) {
      printf("More? - touch the enter key: ");
      scanf("%c", &ignore);
    }
    prnt_date(calendar[j]);

  }
}  

/* Return the date after d */
date tomorrow(date d){
  date result;
  
  result = d;

  switch(d.month){
    case 1: case 3: case 5: case 7: case 8: case 10: 
      if (d.day < 31)
	++(result.day);
      else {result.day = 1; ++(result.month);}
      break;
    case 4: case 6: case 9: case 11: 
      if (d.day < 30)
	++(result.day);
      else {result.day = 1; ++(result.month);}
      break;
    case 2:
      if (d.day < (leapYear(d.year)? 29 : 28))
        ++(result.day);
      else {result.day = 1; result.month = 3;}
      break;
    case 12:
      if (d.day < 31)
	++(result.day);
      else {result.day = 1; result.month = 1; (++result.year);}
      break;
    default: exit(-1);  break;
  }

  result.day_of_week = next_day_of(d.day_of_week);
  return result;
}

/* Is y a leapyear */
int leapYear(int y){
  int result;

  if (y % 400 == 0) result = 1;
  else if (y % 100 == 0) result = 0;
  else if (y % 4 == 0) result = 1;
  else result = 0;

  return result;
}

/* Is date d1 less than date d2 */
int date_before(date d1, date d2){
 return
  (d1.year < d2.year) ||
  (d1.year == d2.year && d1.month < d2.month) ||
  (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day);
}  

weekday next_day_of(weekday d){
  return (weekday) (((int) d + 1) % 7);
}

/* Print date d */
void prnt_date(date d){
  printf("%9s %2i.%2i.%4i\n", name_of_weekday(d), d.day, d.month, d.year);
}

/* Return the name of the weekday of the date d */
char *name_of_weekday(date d){
  char *result;
  switch (d.day_of_week) {
    case sunday: result = "Sunday";
       break;
    case monday: result = "Monday";
       break;
    case tuesday: result = "Tuesday";
       break;
    case wednesday: result = "Wednesday";
       break;
    case thursday: result = "Thursday";
       break;
    case friday: result = "Friday";
       break;
    case saturday: result = "Saturday";
       break;
  }
  return result;
}   

#include <stdio.h>
#include <stdlib.h> 
#include <time.h>
/* NUMBER_OF_CARDS controls the number of jokers */
#define NUMBER_OF_CARDS 55

enum card_type {club, diamond, heart, spade, joker};
typedef enum card_type card_type;

/* Card values range from 2 to ace. Card values above 10 have symbolic names: */
enum card_value {jack = 11, queen = 12, king = 13, ace = 14};  
typedef enum card_value card_value;

struct card{
  card_type type;
  card_value value;
};
typedef struct card card;

card make_card(card_type t, card_value v);
card make_joker(void);
void put_cards_in_deck(card deck[]);
void print_deck(card deck[]);
void print_card(card c);
int card_compare(const void *ep1, const void *ep2);
void sort_cards(card deck[]);
void swap_cards(card deck[], int i, int j);
void shuffle_cards(card deck[]);

int main(void) {
  card deck[NUMBER_OF_CARDS];

  srand(time(NULL));   /* Seed random number generator */

  put_cards_in_deck(deck);
  printf("INITIAL:\n");
  print_deck(deck);

  shuffle_cards(deck);
  printf("\nAFTER SHUFFLE:\n");
  print_deck(deck);

  sort_cards(deck);
  printf("\nAFTER SORTING:\n");
  print_deck(deck);
  
  return 0;
}

void put_cards_in_deck(card deck[]){
  int ct, cv, i = 0, j;
  card c;

  /* Make 4 x 13 normal cards: */
  for(ct = club; ct <= spade; ct++){
    for(cv = 2; cv <= ace; cv++){
      c = make_card(ct, cv);
      deck[i] = c;
      i++;
    }
  }

  /* Make sufficient jokers, to a total of NUMBER_OF_CARS cards. */
  for(j = 1; j <= NUMBER_OF_CARDS - (4 * (int)king); j++)
    deck[i++] = make_joker();
}

void print_deck(card deck[]){
  int i;
  for (i = 0; i < NUMBER_OF_CARDS; i++) {
    print_card(deck[i]);
    printf("\n");
  }
}


card make_card(card_type t, card_value v){
  card result;
  result.type = t;
  result.value = v;
  return result;
}

card make_joker(void){
  card result;
  result.type = joker;
  result.value = 0;    /* arbitrary, but well-defined */
  return result;
}

  
void print_card(card c){
  static char *card_type_name[] = {"club", "diamond", "heart", "spade", "joker"};
  static char *card_value_name[] = {"two", "three", "four", "five", "six",
                                    "seven", "eight", "nine", "ten", 
                                    "jack", "queen", "king", "ace"};
  if (c.type == joker)
    printf("joker");
  else 
    printf("%s %s", card_type_name[c.type], card_value_name[c.value-2]);
}

void sort_cards(card deck[]){
  qsort(deck, NUMBER_OF_CARDS, sizeof(card), card_compare);
}


int card_compare(const void *ep1, const void *ep2){
  card *cp1 = (card *)ep1,
       *cp2 = (card *)ep2;

  if (cp1->type == cp2->type)
    return cp1->value - cp2->value;
  else 
    return cp1->type - cp2->type;
}


void swap_cards(card deck[], int i, int j){
  card temp_card;
  temp_card = deck[i];
  deck[i] = deck[j];
  deck[j] = temp_card;
}

void shuffle_cards(card deck[]){
  int i, r;
  for(i = 0; i < NUMBER_OF_CARDS; i++){
    r = rand() % NUMBER_OF_CARDS;
    swap_cards(deck, i, r);
  }
}

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

struct fraction{
  unsigned int numerator;
  unsigned int denominator;
}; 
typedef struct fraction fraction;

void print_fraction(const fraction f);
fraction shorten(const fraction f);
fraction add_fractions(fraction f, fraction g);
fraction multiply_fractions(fraction f, fraction g);
fraction multiply_fraction_with_int(fraction f, unsigned int i);

unsigned int gcd(unsigned int large, unsigned int small);

int main(void) {
  fraction f1 = {50, 30},
           f2 = {12, 32},
           f3 = {1, 2};

  print_fraction(shorten(f1));
  print_fraction(add_fractions(f2, f3));
  print_fraction(add_fractions(f3, f3));
  print_fraction(multiply_fractions(f2, f3));
  print_fraction(multiply_fractions(f3, f3));
  print_fraction(multiply_fraction_with_int(f3, 4));
  
  return EXIT_SUCCESS;
}

/* Make and return a fraction with numerator and denominator */
fraction make_fraction(unsigned int numerator, unsigned int denominator){
  fraction result;
  result.numerator = numerator; result.denominator = denominator;
  return result;
}

/* Add two the fractions f and g, and return the sum */
fraction add_fractions(fraction f, fraction g){
  return shorten(make_fraction(f.numerator * g.denominator + g.numerator * f.denominator, f.denominator * g.denominator));
}

/* Multiply the two fractions f and g, and return the sum */
fraction multiply_fractions(fraction f, fraction g){
  return shorten(make_fraction(f.numerator * g.numerator, f.denominator * g.denominator));
}

/* Multiply the fraction f and i and return the product. */
fraction multiply_fraction_with_int(fraction f, unsigned int i){
  return multiply_fractions(f, make_fraction(i, 1));
}

/* Return the greatest common divisor of large and small. Assume that large is greater than small. */
unsigned int gcd(unsigned int large, unsigned int small){
  unsigned int remainder; 
  while (small > 0){
    remainder = large % small;
    large = small;
    small = remainder;
  }
  return large;
}

/* Print the fraction f on standard output */
void print_fraction(const fraction f){
  if (f.denominator == 1)
    printf("%u\n", f. numerator);
  else 
    printf("%u/%u\n", f. numerator, f.denominator); 
}

/* Shorten f as much as possible, and return the shortened fraction */
fraction shorten(const fraction f){
  unsigned int factor = gcd(f.numerator, f.denominator);
  fraction result;
  
  result.numerator = f.numerator /factor;
  result.denominator = f.denominator /factor;

  return result;
}

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

struct point {int x; int y;};
typedef struct point point;

struct list_node {
  void             *data;
  struct list_node *next;
};
typedef struct list_node list_node;

void print_point(point *p);
void print_circular_point_list(list_node *cl);
list_node *insert_head(list_node *cl, void *el);
list_node *insert_tail(list_node *cl, void *el);
list_node *delete_head(list_node *cl);
list_node *delete_tail(list_node *cl);
int length_of_circular_list(list_node *cl);
list_node *find_previous_node(list_node *cl);

int main(void) {
  point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p4 = {7,8};

  list_node *circular_list = NULL;
  printf("Length of circular list: %d\n", length_of_circular_list(circular_list));

  return EXIT_SUCCESS;
}

void print_point(point *p){
  printf("(%1d, %1d)\n", p->x, p->y);
}

void print_circular_point_list(list_node *cl){
  list_node *cur, *prev;

  if (cl != NULL){
   cur = cl->next;
   do{
     prev = cur;
     print_point(cur->data);
     cur = cur->next;
   }
   while(prev != cl);
  }
}

/* An exercise */
int length_of_circular_list(list_node *cl){
  return 0; 
}

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

struct point {int x; int y;};
typedef struct point point;

struct list_node {
  void             *data;
  struct list_node *next;
};
typedef struct list_node list_node;

void print_point(point *p);
void print_circular_point_list(list_node *cl);
list_node *insert_head(list_node *cl, void *el);
list_node *insert_tail(list_node *cl, void *el);
list_node *delete_head(list_node *cl);
list_node *delete_tail(list_node *cl);
int length_of_circular_list(list_node *cl);
list_node *find_previous_node(list_node *cl);
void assert_allocation_success(list_node *ln);

int main(void) {
  point p1 = {1,2}, p2 = {3,4}, p3 = {5,6};

  list_node *circular_list = NULL;
  printf("Length of circular list: %d\n", length_of_circular_list(circular_list));

  circular_list =
    insert_tail(
      insert_tail(
        insert_tail(circular_list, &p1),
        &p2),
      &p3);
  printf("Length of circular list: %d\n", length_of_circular_list(circular_list));
  print_circular_point_list(circular_list);

  circular_list = delete_tail(circular_list);
  printf("Length of circular list: %d\n", length_of_circular_list(circular_list));
  print_circular_point_list(circular_list);

  circular_list = delete_head(circular_list);
  printf("Length of circular list: %d\n", length_of_circular_list(circular_list));
  print_circular_point_list(circular_list);

  circular_list = delete_tail(circular_list);
  printf("Length of circular list: %d\n", length_of_circular_list(circular_list));
  print_circular_point_list(circular_list);

  circular_list = delete_tail(circular_list);
  printf("Length of circular list: %d\n", length_of_circular_list(circular_list));
  print_circular_point_list(circular_list);

  return EXIT_SUCCESS;
}

void print_point(point *p){
  printf("(%1d, %1d)\n", p->x, p->y);
}

void print_circular_point_list(list_node *cl){
  list_node *cur, *prev;

  if (cl != NULL){
   cur = cl->next;
   do{
     prev = cur;
     print_point(cur->data);
     cur = cur->next;
   }
   while(prev != cl);
  }
}

/* Insert el as a new head. Return the circular list */
list_node *insert_head(list_node *cl, void *el){
  list_node *new_node = malloc(sizeof(list_node));
  assert_allocation_success(new_node);
  new_node->data = el;

  if (cl == NULL){
    new_node->next = new_node;
    return new_node;
  }
  else{    
    list_node *old_head = cl->next;
    new_node->next = old_head;
    cl->next = new_node;
    return cl;  
  }
}

/* Insert el as a new tail. Return the circular list */
list_node *insert_tail(list_node *cl, void *el){
  list_node *new_node = malloc(sizeof(list_node));
  assert_allocation_success(new_node);
  new_node->data = el;

  if (cl == NULL){
    new_node->next = new_node;
    return new_node;
  }
  else{    
    list_node *old_head = cl->next;
    cl->next = new_node;
    new_node->next = old_head;
    return new_node;
  }
}

void assert_allocation_success(list_node *ln){
  if (ln == NULL){
    printf("Cannot allocate list node. Bye\n");
    exit(EXIT_FAILURE);
  }
}


/* Delete the head, if possible, and return the resulting (shorter) circular list */
list_node *delete_head(list_node *cl){
  if(cl == NULL){
    printf("Cannot delete from emtpy list");
    exit(EXIT_FAILURE);
  }
  else if (cl == cl->next) { /* circular list of length one */
    free(cl);
    return NULL;
  }
  else{
    list_node *node_to_delete = cl->next;
    cl->next = cl->next->next;
    free(node_to_delete);
    return cl;
  }
}

/* Delete the tail, if possible, and return the resulting (shorter) circular list */
list_node *delete_tail(list_node *cl){
  if(cl == NULL){
    printf("Cannot delete from emtpy list");
    exit(EXIT_FAILURE);
  }
  else if (cl == cl->next) { /* circular list of length one */
    free(cl);
    return NULL;
  }
  else{
    list_node *before_tail = find_previous_node(cl);
    before_tail->next = cl->next;
    free(cl);
    return before_tail;
  }
}

/* As a precondition, assume that cl is not empty and that cl is not singular. Thus the list has least two elements. */
list_node *find_previous_node(list_node *cl){
  list_node *cur = cl->next;
  
  while (cur->next != cl){
    cur = cur->next;
  }
  return cur;
}

int length_of_circular_list(list_node *cl){
  if (cl == NULL)
    return 0;
  else {
    int count = 0;
    list_node *cur = cl->next, *prev;
    do{
      prev = cur;
      ++count;
      cur = cur->next;
    }
    while(prev != cl);
    return count;
  }
}

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

struct tree_node{
  int key;
  struct tree_node *leftp, *rightp;
};

typedef struct tree_node tree_node;

tree_node *make_tree(int key, tree_node *left, tree_node *right);
void assert_allocation_success(void *alloc_pointer);
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e);
void print_tree(tree_node *tree_ptr);
void print_tree_helper(tree_node *tree_ptr, int level);
int tree_height(tree_node *tree_ptr);

int main(void) {

  tree_node *tree4 = NULL;
  tree4 = insert_in_binary_search_tree(tree4, 6);
  tree4 = insert_in_binary_search_tree(tree4, 2);
  tree4 = insert_in_binary_search_tree(tree4, 1);
  tree4 = insert_in_binary_search_tree(tree4, 4);
  tree4 = insert_in_binary_search_tree(tree4, 3);
  tree4 = insert_in_binary_search_tree(tree4, 5);
  tree4 = insert_in_binary_search_tree(tree4, 7);
  tree4 = insert_in_binary_search_tree(tree4, 9);
  tree4 = insert_in_binary_search_tree(tree4, 8);

  printf("tree4:\n");
  print_tree(tree4);

  exit(EXIT_FAILURE);
}


tree_node *make_tree(int key, tree_node *left, tree_node *right){
  tree_node *the_tree = malloc(sizeof(tree_node));
  assert_allocation_success(the_tree);
  the_tree->key = key; 
  the_tree->leftp = left; 
  the_tree->rightp = right; 
  return the_tree;
} 

void assert_allocation_success(void *alloc_pointer){
  if (alloc_pointer == NULL){
    printf("Allocation problems. Your program stops.");
    exit(EXIT_FAILURE);
  }
}

/* Insert the element e i the binary search tree, designated by tree_ptr. 
   Drop the insertion if e is already in the tree. 
   Return the tree  in terms of a pointer to its root node. */
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e){
  if (tree_ptr == NULL){
    /* Make a small tree rooted with e and empty subtrees */
    /* This branch is never reached via recursion */
    tree_node *the_tree = make_tree(e, NULL, NULL);
    return the_tree;
  }
  else if (e == tree_ptr->key){
    /* Do nothing */
    return tree_ptr;
  }
  else if (e < tree_ptr->key && tree_ptr->leftp == NULL){
    tree_node *the_tree = make_tree(e, NULL, NULL);
    tree_ptr->leftp = the_tree;
    return tree_ptr;         
  }
  else if (e < tree_ptr->key){
    insert_in_binary_search_tree(tree_ptr->leftp, e);
    return tree_ptr;
  }
  else if (e > tree_ptr->key && tree_ptr->rightp == NULL){
    tree_node *the_tree = make_tree(e, NULL, NULL);
    tree_ptr->rightp = the_tree;
    return tree_ptr;         
  }
  else { /* e > tree_ptr->key) */
    insert_in_binary_search_tree(tree_ptr->rightp, e);
    return tree_ptr;
  }
}

void print_tree(tree_node *tree_ptr){
  print_tree_helper(tree_ptr, 0);
}    

/* print the tree designated by tree_ptr as horizotally, as an indented text, on standard output.
   Empty subtrees are printed as "." if tree_ptr is passsed as NULL */
void print_tree_helper(tree_node *tree_ptr, int level){
  int i; 

  /* print indented root */
  for(i = 0; i < level; ++i) 
    printf("   ");
  if (tree_ptr == NULL)
    printf(".\n");  /* Missing part */
  else
    printf("%d\n", tree_ptr->key);

  if(tree_ptr != NULL){
    /* print branches */
    if (tree_ptr->leftp == NULL && tree_ptr->rightp == NULL){
      /* print nothing */
    }
    else if (tree_ptr->leftp != NULL && tree_ptr->rightp == NULL){
      print_tree_helper(tree_ptr->leftp, level+1);
      print_tree_helper(NULL, level+1);
    }   
    else if (tree_ptr->leftp == NULL && tree_ptr->rightp != NULL){
      print_tree_helper(NULL, level+1);
      print_tree_helper(tree_ptr->rightp, level+1);
    }
    else {  
      print_tree_helper(tree_ptr->leftp, level+1);
      print_tree_helper(tree_ptr->rightp, level+1);
    }
  }
}


/* Opgave */
int tree_height(tree_node *tree_ptr){
  return 0;
}

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

struct tree_node{
  int key;
  struct tree_node *leftp, *rightp;
};

typedef struct tree_node tree_node;

tree_node *make_tree(int key, tree_node *left, tree_node *right);
void assert_allocation_success(void *alloc_pointer);
void print_tree(tree_node *tree_ptr);
void print_tree_helper(tree_node *tree_ptr, int level);
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e);
int is_binary_search_tree(tree_node *tree_ptr);

int main(void) {
  tree_node *tree4 = NULL;
  tree4 = insert_in_binary_search_tree(tree4, 6);
  tree4 = insert_in_binary_search_tree(tree4, 2);
  tree4 = insert_in_binary_search_tree(tree4, 1);
  tree4 = insert_in_binary_search_tree(tree4, 4);
  tree4 = insert_in_binary_search_tree(tree4, 3);
  tree4 = insert_in_binary_search_tree(tree4, 5);
  tree4 = insert_in_binary_search_tree(tree4, 7);
  tree4 = insert_in_binary_search_tree(tree4, 9);
  tree4 = insert_in_binary_search_tree(tree4, 8);

  /* Per construction, tree4 should be a binary search tree */
  /* You can use make_tree to construct other trees which are not binary search trees */

  printf("tree4:\n");
  print_tree(tree4);

  exit(EXIT_FAILURE);
}


tree_node *make_tree(int key, tree_node *left, tree_node *right){
  tree_node *the_tree = malloc(sizeof(tree_node));
  assert_allocation_success(the_tree);
  the_tree->key = key; 
  the_tree->leftp = left; 
  the_tree->rightp = right; 
  return the_tree;
} 

void assert_allocation_success(void *alloc_pointer){
  if (alloc_pointer == NULL){
    printf("Allocation problems. Your program stops.");
    exit(EXIT_FAILURE);
  }
}

/* Insert the element e i the binary search tree, designated by tree_ptr. 
   Drop the insertion if e is already in the tree. 
   Return the tree  in terms of a pointer to its root node. */
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e){
  if (tree_ptr == NULL){
    /* Make a small tree rooted with e and empty subtrees */
    /* This branch is never reached via recursion */
    tree_node *the_tree = make_tree(e, NULL, NULL);
    return the_tree;
  }
  else if (e == tree_ptr->key){
    /* Do nothing */
    return tree_ptr;
  }
  else if (e < tree_ptr->key && tree_ptr->leftp == NULL){
    tree_node *the_tree = make_tree(e, NULL, NULL);
    tree_ptr->leftp = the_tree;
    return tree_ptr;         
  }
  else if (e < tree_ptr->key){
    insert_in_binary_search_tree(tree_ptr->leftp, e);
    return tree_ptr;
  }
  else if (e > tree_ptr->key && tree_ptr->rightp == NULL){
    tree_node *the_tree = make_tree(e, NULL, NULL);
    tree_ptr->rightp = the_tree;
    return tree_ptr;         
  }
  else { /* e > tree_ptr->key) */
    insert_in_binary_search_tree(tree_ptr->rightp, e);
    return tree_ptr;
  }
}
/* void delete_tree(tree_node *tree_ptr)
   Rather difficult to program because it requires access to parents */


void print_tree(tree_node *tree_ptr){
  print_tree_helper(tree_ptr, 0);
}    

/* print the tree designated by tree_ptr as horizotally, as an indented text, on standard output.
   Empty subtrees are printed as "." if tree_ptr is passsed as NULL */
void print_tree_helper(tree_node *tree_ptr, int level){
  int i; 

  /* print indented root */
  for(i = 0; i < level; ++i) 
    printf("   ");
  if (tree_ptr == NULL)
    printf(".\n");  /* Missing part */
  else
    printf("%d\n", tree_ptr->key);

  if(tree_ptr != NULL){
    /* print branches */
    if (tree_ptr->leftp == NULL && tree_ptr->rightp == NULL){
      /* print nothing */
    }
    else if (tree_ptr->leftp != NULL && tree_ptr->rightp == NULL){
      print_tree_helper(tree_ptr->leftp, level+1);
      print_tree_helper(NULL, level+1);
    }   
    else if (tree_ptr->leftp == NULL && tree_ptr->rightp != NULL){
      print_tree_helper(NULL, level+1);
      print_tree_helper(tree_ptr->rightp, level+1);
    }
    else {  
      print_tree_helper(tree_ptr->leftp, level+1);
      print_tree_helper(tree_ptr->rightp, level+1);
    }
  }
}


int int_max(int a, int b){
  return a > b ? a : b;
}

/* Opgaven */
int is_binary_search_tree(tree_node *tree_ptr){
  return 0;
}


    

int is_binary_search_tree(tree_node *tree_ptr){
  if (tree_ptr == NULL)
    return 1;  /* The empty tree is here considered as binary search tree */
  else if (tree_ptr->leftp != NULL && tree_ptr->rightp != NULL)
    return tree_ptr->key > max_value_in_binary_tree(tree_ptr->leftp) &&
           tree_ptr->key < max_value_in_binary_tree(tree_ptr->rightp) &&
           is_binary_search_tree(tree_ptr->leftp) &&
           is_binary_search_tree(tree_ptr->rightp);
  else if (tree_ptr->leftp != NULL && tree_ptr->rightp == NULL)
    return tree_ptr->key > max_value_in_binary_tree(tree_ptr->leftp) &&
           is_binary_search_tree(tree_ptr->leftp);
  else if (tree_ptr->leftp == NULL && tree_ptr->rightp != NULL)
    return tree_ptr->key < max_value_in_binary_tree(tree_ptr->rightp) &&
           is_binary_search_tree(tree_ptr->rightp);
  else if (tree_ptr->leftp == NULL && tree_ptr->rightp == NULL)
    return 1;
  else {
    printf("is_binary_search_tree: Should not happen\n");
    exit(EXIT_FAILURE);
  }
}

int max_value_in_binary_tree(tree_node *tree_ptr){
  if (tree_ptr == NULL)
    return INT_MIN; /* Convenient value for empty trees */
  else 
    return int_max(int_max(tree_ptr->key, max_value_in_binary_tree(tree_ptr->leftp)), 
                   max_value_in_binary_tree(tree_ptr->rightp));
}

int int_max(int a, int b){
  return a > b ? a : b;
}