// Example of stack-based approach to tree walking for lab 3, Spring 2013

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

#define LEVELS (5)

typedef struct tnode* link;

struct tnode
{
int key;
link l,r;
};

link build(int start,int k)
{ // Build complete BST with k levels
link newpt;

if (k==0)
  return NULL;
newpt=(link) malloc(sizeof(struct tnode));
newpt->l=build(start,k-1);
newpt->key=start+(1<<(k-1))-1;
newpt->r= build(newpt->key+1,k-1);
}

void inorder(link h,int k,int leftFlag)
{ // Recursive inorder
if (h==NULL)
  return;
inorder(h->l,k-1,1);
printf("%*s %d k %d",3*(1+LEVELS-k),"key",h->key,k);
if (leftFlag)
  printf(" left");
else
  printf(" right");
printf("\n");
inorder(h->r,k-1,0);
}

int x,j,sp; // Globals

struct {
  link h;
  int lastVisit; // 1=from parent, 2=from left child, 3=from right child
} stack[100];

void command1(link root,int levels)
{ // Finds a key and builds stack for later inorder movement
link h=root;
//int left=0;

sp=0;
while (h!=NULL)
{
  stack[sp].h=h;
  sp++;
  if (h->key==x)
  {
    printf("1 found %d %d\n",x,levels+1-sp);
    stack[sp-1].lastVisit=2;
    return;
  }
  if (h->key>x)
  {
    stack[sp-1].lastVisit=1; // could be printed later
    h=h->l;
  }
  else
  {
    stack[sp-1].lastVisit=2; // cannot be printed later
    h=h->r;
  }
}
printf("Command failed %d\n",__LINE__); // Never found key
exit(0);
}

void command2(int levels)
{ // j steps of inorder traversal from current stack state
int arrived;

for ( ;j>0;j--)
{
  arrived=0;
  while (!arrived)
    switch (stack[sp-1].lastVisit)
    {
      case 1:
        if (stack[sp-1].h->l==NULL)
          arrived=1;
        else
        {
          stack[sp].h=stack[sp-1].h->l;
          stack[sp].lastVisit=1;
          sp++;
        }
        break;
      case 2:
        if (stack[sp-1].h->r==NULL)
          stack[sp-1].lastVisit=3;
        else
        {
          stack[sp].h=stack[sp-1].h->r;
          stack[sp].lastVisit=1;
          sp++;
        }
        break;
      case 3:
        while (stack[sp-1].lastVisit!=1)
        {
          sp--;
          if (sp==0)
          { // Have climbed up 
            printf("Command failed %d\n",__LINE__);
            exit(0);
          }
        }
        arrived=1;
        break;
    }
  printf("%d %d\n",stack[sp-1].h->key,levels+1-sp);
  stack[sp-1].lastVisit=2;
}
}

void treewalker(link root,int levels)
{ // Gets commands
int command;

scanf("%d",&command);
if (command==2)
{
  printf("No current node\n");
  exit(0);
}
while (command)
{
  if (command==1)
  {
    scanf("%d",&x);
    command1(root,levels);
  }
  else if (command==2)
  {
    scanf("%d",&j);
    if (j<0)
    {
      printf("Invalid negative value\n");
      exit(0);
    }
    command2(levels);
  }
  else
  {
    printf("Bad command #\n");
    exit(0);
  }
  scanf("%d",&command);
}
}

main()
{
link root;

root=build(0,LEVELS);
inorder(root,LEVELS,1);
treewalker(root,LEVELS);
}