title: Find path to node, Tree C
body: <p>Hi i'm trying to find the path to a given node in a Tree.</p>
  
  <p>I use the tree to analize all the possible pathways in a maze defined as a matrix of int.</p>
  
  <p>Here's the matrix:</p>
  
  <pre><code>int room[20][20] =
  {
    {0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  };
  </code></pre>
  
  <p>1 means that there is a wall, 2 is the exit, 0 is free space</p>
  
  <p>here's how i defined the node:</p>
  
  <pre><code>struct node
  {
   int i,j; //NODE COORDS
   int key;
   struct node *right;
   struct node *left;
   struct node *up;
   struct node *down;
  };
  </code></pre>
  
  <p>Here's the method i'm using to insert a node in the Tree:</p>
  
  <pre><code>void insert(int room[20][20], struct node **leaf, int i, int j)
  {
  
      if( *leaf == 0 )
      {
          *leaf = (struct node*) malloc( sizeof( struct node ) );
          (*leaf)-&gt;key = room[i][j];
          (*leaf)-&gt;i = i;
          (*leaf)-&gt;j = j;
          (*leaf)-&gt;left = 0;
          (*leaf)-&gt;right = 0;
          (*leaf)-&gt;up = 0;
          (*leaf)-&gt;down = 0;
      }
      else if((room[i][j+1]==0 || room[i][j+1]==2) &amp;&amp; i&lt;20 &amp;&amp; j&lt;20 &amp;&amp; i&gt;=0 &amp;&amp; j+1&gt;=0)//CHECK IF RIGHT IS FREE OR IS EXIT OF THE MAZE
      {
          (*leaf)-&gt;key = room[i][j+1];
          insert( room, &amp;(*leaf)-&gt;right, i ,j+1 );
      }
      else if((room[i][j-1]==0 || room[i][j-1]==2) &amp;&amp; i&lt;20 &amp;&amp; j&lt;20 &amp;&amp; i&gt;=0 &amp;&amp; j-1&gt;=0)//CHECK IF LEFT IS FREE OR IS EXIT OF THE MAZE
      {
          (*leaf)-&gt;key = room[i][j-1];
          insert( room, &amp;(*leaf)-&gt;left, i ,j-1 );
      }
      else if((room[i+1][j]==0 || room[i+1][j]==2) &amp;&amp; i&lt;20 &amp;&amp; j&lt;20 &amp;&amp; i+1&gt;=0 &amp;&amp; j&gt;=0)//CHECK IF DOWN IS FREE OR IS EXIT OF THE MAZE
      {
          (*leaf)-&gt;key = room[i+1][j];
          insert( room, &amp;(*leaf)-&gt;down, i+1 ,j );
      }
      else if((room[i-1][j]==0 || room[i-1][j]==2) &amp;&amp; i&lt;20 &amp;&amp; j&lt;20 &amp;&amp; i-1&gt;=0 &amp;&amp; j&gt;=0)//CHECK IF UP IS FREE OR IS EXIT OF THE MAZE
      {
          (*leaf)-&gt;key = room[i-1][j];
          insert( room, &amp;(*leaf)-&gt;up, i-1 ,j );
      }
  }
  </code></pre>
  
  <p>Initialise the Tree:</p>
  
  <pre><code>struct node *root = 0;
  for(i=0;i&lt;400;i++)
  insert(room,&amp;root,0,0); //INITIALIZE THE TREE ANALIZING EVERY CELL OF THE MATRIX
  </code></pre>
  
  <p>Once i initialized the Tree like above i want to search for the key that has the value 2(exit) and be able to find the path from that node to the root node and gather the coords of every node in between them. </p>
  
  <p>To do this once i find the node that has value 2 i want to find the parent of that node and so on until i find the root node, and every time i find a node in between them i want to store it's coords in an array, so later on i can use them to draw the path to the exit.</p>
  
  <p><strong>How do i find the node that has value 2 in this case ?</strong></p>
  
  <p><strong>How do i find the parent node of a given node in this case ?</strong></p>