fabianbaechli

struct node* BSTreeDelete(struct node* root, struct node* x) {
  u = root; v = NULL; 
  while (u != x) { 
    v = u; 
    if (x->key < u->key) u = u->lft; 
    else u = u->rgt; 
  }

  if (u->rgt == NULL) { 
    if (v == NULL) root = u->lft; 

fabianbaechli

struct node* BSTTreeInsert(struct node* p, struct node* r) { 
  struct node* y = NULL; 

  struct node* x = r; 

  while (x != NULL) { 
    // y is one step behind y = x; 
    if (x -> key < p -> key) { 
        x = x -> rgt; 
    } else { 

fabianbaechli

struct node* BSTreeSuccAbove(struct node* p, struct node* x) { 
    struct node* succ = NULL; 
    while (p != x) { 
        if (x->key < p->key) { 
            succ = p; 
            p = p->lft; 
        } else if (x->key > p->key) { 
            p = p->rgt; 
        } 
    } 

fabianbaechli

BSTRecCount(struct node* p, int x) { 
  if (p ≠ NULL) { 
    if (x < p->val) { 
      return BSTRecCount(p->lft); 
    } else if (x > p-val) { 
      return BSTRecCount(p->rgt); 
    } else { 
      return 1 + BSTRecCount(p->lft) + BSTRecCount(p->rgt) 
    } 
  } else { 

fabianbaechli

// Iterative
BSTreeSearch(p,v) 
  while p ≠ NIL AND p->key≠v do 
    if v<p->key then 
      p = p->lft 
    else 
      p = p->rgt; 
  return p;

// Recursive

fabianbaechli

infix(struct node* p = { 
  if (p ≠ NULL) { 
    if (needParanthesis(p, false)) { 
      printf("("); 
      infix(p->lft); 
      printf(")"); 
    } else { 
      infix(p->lft); 
    } 
  }

fabianbaechli

bool needsParentheses(struct node* p, bool rgt) { 

return (
  // (a + b) / c
  !rgt && precedence(p) < precedence(p->lft)) ||
  
  // case where right operation has precedence
  // for example: a + (b * c)
  (rgt && precedence(p) < precedence(p->rgt)) ||
  

fabianbaechli

// can also be implemented using functions which return the altered head of the list
struct node { 
  int val; 
  struct node* next; 
};

struct node** init() {
  struct node** l = malloc(sizeof(struct node*));
  *l = NULL;

fabianbaechli

struct Queue { 
    int a[5]; // queue with 5 elements 
    int h; // head (first element of queue) 
    int t; // tail (right after last element) 
};

/* 
  This implementation can add infinite numbers of elements to the queue (even though it might be full) 
  because it is a circular queue implementation. If the array is full, elements are dropped. If this isn't reasonable
  add a isFull check before adding

fabianbaechli

struct Stack {
  int a[5];
  int t;
};

struct Stack* create() {
  struct Stack* s = malloc(sizeof(struct Stack));
  s -> t = 0;
  return s;
}