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

typedef struct nodeTag 
{ 
    int data; 
    struct nodeTag* left; 
    struct nodeTag* right; 
} t_node;


/* allocate memory for a new node */
t_node* NewNode(int data);

/* insert a new node in the right place */
t_node* AddToTree(t_node* node, int data) ;

/* find a node (by its 'data' field), generate path */
int GetPathToNode(t_node *node, int data, char **path);


/* print tree */
void PrintTree(t_node *node);


int main()
{
    t_node *tree = NULL;
    char *path = NULL;
    int val;

    tree = AddToTree(tree, 10);
    tree = AddToTree(tree, 2);
    tree = AddToTree(tree, -2);
    tree = AddToTree(tree, 6);

    PrintTree(tree);

    val = -2;
    GetPathToNode(tree, val, &path);
    printf("path to node %i: %s\n", val, path);
}


/* allocate memory for a new node */
t_node* NewNode(int data) 
{ 
    t_node* node;

    if ((node = (t_node *)malloc(sizeof(t_node))) != NULL)
    {
        node->data = data; 
        node->left = NULL; 
        node->right = NULL;
    }

    return node; 
} 
 

/* insert a new node in the right place */
t_node* AddToTree(t_node* node, int data) 
{ 
    /* empty tree - return a new root node */
    if (node == NULL) 
        return NewNode(data); 
    
    /* otherwise, find the righ place (recur down) and inster */
    if (data <= node->data) 
        node->left = AddToTree(node->left, data); 
    else 
        node->right = AddToTree(node->right, data);

    return(node); /* return root node (existing) */
} 


/* print tree */
void PrintTree(t_node *node)
{
    if (node != NULL)
    {
        printf("Node %d (address %p, left %p, right %p)\n",
                node->data, node, node->left, node->right);

        PrintTree(node->left);
        PrintTree(node->right);
    }
}


/* find a node (by its 'data' field), generate path */
int GetPathToNode(t_node *node, int data, char **path)
{
   char buf[16];
   char *oldstring = NULL;
   int found = 0;

   if (node == NULL)
       return 0;

   if (node->data == data) /* we fount it! */
      found = 1; 
   else
   {
       /* otherwise, check which branch to take, and take it */
       if (data < node->data)
          found = GetPathToNode(node->left, data, path);
       else
          found = GetPathToNode(node->right, data, path); 
   }

   if (found) /* the value exists and we need to generate the path */
   {
       /* figure out how many bytes to add */
       sprintf(buf, "%d", node->data);
 
       if (*path == NULL) /* first time */
       {
           *path = (char *)malloc((strlen(buf)+1)*sizeof(char));

           /* generate new path string */
           sprintf(*path, "%s\0", buf);
       }
       else /* it already exists, but we need to enlarge it */
       {
           oldstring = *path;
           *path = (char *)malloc((strlen(*path)+strlen(buf)+2)*sizeof(char));
       
           /* add to an existing string */
           sprintf(*path, "%s:%s", buf, oldstring);

           free(oldstring);
       }
    }

    return found;
}