title: Evaluating expression trees
body: <p>Skiena's book on Algorithm contains the following question:</p>
  
  <p>1) Evaluate expression given as binary tree in O(n) time, given n nodes.</p>
  
  <p>2) Evaluate expression given as DAG in O(n+m) time, given n nodes and m edges in DAG.</p>
  
  <p><img src="https://i.stack.imgur.com/vjOjF.jpg" alt="enter image description here"></p>
  
  <p>I could think of a way for the first question:</p>
  
  <pre><code>evaluate(node) {
       if(node has children){
            left_val = evaluate(node-&gt;left);
            right_val = evaluate(node-&gt;right);
  
            // find operation symbol for node and use it as
            // val = left_val operation right_val
  
            return val;
       }
       else {
            return node_value;
       }
  }
  </code></pre>
  
  <p>Since we visit each node once, it will take O(n) time.</p>
  
  <p>Since the book has no solutions, can anyone please tell if this is correct ? </p>
  
  <p>Also can anyone suggest a solution for second question.</p>
  
  <p>Thanks.</p>