title: Building parse tree from prefixed expression in c
body: <p>I'm trying to create a binary tree like this: <a href="http://interactivepython.org/runestone/static/pythonds/_images/meParse.png" rel="nofollow noreferrer">link</a></p>
  
  <p><img src="https://i.stack.imgur.com/1nj7r.png" alt="enter image description here"></p>
  
  <p>The input will be entered by the user as prefix and read as a string, then put in a binary tree.</p>
  
  <p>This is what I have so far:</p>
  
  <pre><code>struct node{
     char val;
     struct node *left;
     struct node *right;
  };
  typedef struct node root;
  typedef root *tree;
  </code></pre>
  
  <p>In main:</p>
  
  <pre><code>void main(){
      int i;
      tree tr;
      char* s;
      s=input(); //input function
      tr=create_empty_tree(); 
      for(i=0;s[i]!='\0';i++){
          tr=add_root(s[i],ab);
      }
      convert_infix(tr);
  }
  </code></pre>
  
  <p>and this is the part I've been struggling with for days; I can't seem to build the tree correctly.
  This is what I have so far:</p>
  
  <pre><code>tree add_root(char val, tree tr){
      if ( tr == NULL ){
          tr= create_root(val);
      }
      else{
          if(val=="*" || val=="+" || val=="-" || val=="/"){
              tr-&gt;left= add_root(val, tr-&gt;left);
          }
          else{
              if(tr-&gt;left == NULL){
                  tr-&gt;left= add_root(val, tr-&gt;left);
              }
              else{
                  tr-&gt;right= add_root(val, tr-&gt;right);
              }
          }
      }
      return tr;
  }
  </code></pre>
  
  <p>I looked this up online and I know that my function is wrong, I tried doing this: </p>
  
  <ul>
  <li><p>Insert new nodes, each time moving to the left until an operand has been inserted.</p></li>
  <li><p>Backtrack to the last operator, and put the next node to its right.</p></li>
  <li><p>Continue in the same pattern.</p></li>
  </ul>
  
  <p>but I don't know how to backtrack. 
  I've been at this for days and I'm going crazy; I'm just a beginner in programming so please don't judge.</p>