#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
  int ID;
  struct Node *leftMostChild;
  struct Node *rightSibling;
} Node;

Node *root;
//        1
//  2     3      4
//  |     |     / \
//  5     6    7   8
//            / \
//          10   9
Node *makeNode(int ID)
{
  Node *newNode = (Node *)malloc(sizeof(Node));
  newNode->ID = ID;
  newNode->leftMostChild = NULL;
  newNode->rightSibling = NULL;
  return newNode;
}
Node *findID(Node *tree, int u)
{
  if (tree == NULL)
    return NULL;
  if (tree->ID == u)
    return tree;
  Node *p = tree->leftMostChild;
  while (p != NULL)
  {
    Node *q = findID(p, u);
    if (q != NULL)
      return q;
    p = p->rightSibling;
  }
  return NULL;
}
void addChild(Node *tree, int u, int x)
{
  //create a node having ID x, addd this node at the end of children list of node with ID u
  Node *p = findID(tree, u);
  if (p == NULL)
    return;
  Node *newNode = makeNode(x);
  if (p->leftMostChild == NULL)
    p->leftMostChild = newNode;
  else
  {
    Node *last = p->leftMostChild;
    while (last->rightSibling != NULL)
    {
      last = last->rightSibling;
    }
    last->rightSibling = newNode;
  }
}

void loadDataBuildTree(char *filename)
{
  FILE *f = fopen(filename, "r");
  while (1)
  {
    int u;
    fscanf(f, "%d", &u);
    if (u == -1)
      break;
    if (root == NULL)
      root = makeNode(u);
    int k;
    fscanf(f, "%d", &k);
    for (int i = 0; i < k; i++)
    {
      int x;
      fscanf(f, "%d", &x);
      addChild(root, u, x);
    }
  }
  fclose(f);
}

void printTree(Node *r)
{
  if (r == NULL)
    return;
  if (r->leftMostChild != NULL)
    printf("%d ", r->ID);
  for (Node *p = r->leftMostChild; p != NULL; p = p->rightSibling)
  {
    printf("%d ", p->ID);
    if(p->rightSibling==NULL) printf("\n");
  }
  for (Node *p = r->leftMostChild; p != NULL; p = p->rightSibling)
    printTree(p);
}


int countNodes(Node *r)
{
  int c = 1;
  if (r == NULL)
    return 0;
  Node *p = r->leftMostChild;
  while (p != NULL)
  {
    c += countNodes(p);
    p = p->rightSibling;
  }
  return c;
}
int countLeaves(Node *r)
{
  if (r == NULL)
    return 0;
  if (r->leftMostChild == NULL)
    return 1;
  int c = 0;
  Node *p = r->leftMostChild;
  while (p != NULL)
  {
    c += countLeaves(p);
    p = p->rightSibling;
  }
  return c;
}

int height(Node *cur)
{
  if (cur == NULL)
    return 0;
  int h = 0;
  Node *p = cur->leftMostChild;
  while (p != NULL)
  {
    int hp = height(p);
    if (hp > h)
      h = hp;
    p = p->rightSibling;
  }
  return h + 1;
}
int depthTmp(Node *q, int depthQ, int u)
{
  if (q == NULL)
    return -1;
  if (q->ID == u)
    return depthQ;
  Node *p = q->leftMostChild;
  while (p != NULL)
  {
    if (p->ID == u)
      return depthQ + 1;
    int d = depthTmp(p, depthQ + 1, u);
    if (d > 0)
      return d;

    p = p->rightSibling;
  }
  return -1;
}

int depth(Node *r, int u)
{
  if (r == NULL)
    return 0;
  return depthTmp(r, 1, u);
}

void preOrder(Node *r)
{
  if (r == NULL)
    return;
  printf("%d ", r->ID);
  Node *p = r->leftMostChild;
  while (p != NULL)
  {
    preOrder(p);
    p = p->rightSibling;
  }
}

void inOrder(Node *r)
{
  if (r == NULL)
    return;
  inOrder(r->leftMostChild);
  printf("%d ", r->ID);
  if (r->leftMostChild == NULL)
    return;
  Node *p = r->leftMostChild->rightSibling;
  while (p != NULL)
  {
    inOrder(p);
    p = p->rightSibling;
  }
}

void postOrder(Node *r)
{
  if (r == NULL)
    return;
  Node *p = r->leftMostChild;
  while (p != NULL)
  {
    postOrder(p);
    p = p->rightSibling;
  }
  printf("%d ", r->ID);
}

int main()
{
  loadDataBuildTree("treedata.txt");
  int curID = 4;
  Node *cur = findID(root, curID);

  printf("number of nodes: %d\nnumber of leaves: %d\n", countNodes(root), countLeaves(root));
  printf("height of %d : %d\n", curID, height(cur));
  printf("depth of %d : %d\n", curID, depth(root, curID));
  printf("preOrder: "); preOrder(root);printf("\n");
  printf("inOrder: ");inOrder(root);printf("\n");
  printf("postOrder: ");postOrder(root);printf("\n");
  printTree(root);
  return 0;
}