Evaluating expression trees

Question

Skiena's book on Algorithm contains the following question:

1) Evaluate expression given as binary tree in O(n) time, given n nodes.

2) Evaluate expression given as DAG in O(n+m) time, given n nodes and m edges in DAG.

I could think of a way for the first question:

evaluate(node) {
     if(node has children){
          left_val = evaluate(node->left);
          right_val = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          return val;
     }
     else {
          return node_value;
     }
}

Since we visit each node once, it will take O(n) time.

Since the book has no solutions, can anyone please tell if this is correct ?

Also can anyone suggest a solution for second question.

Thanks.

Solution

First way looks fine to me.

For the DAG, if you can modify the tree to add cached values to each node, you can use the same algorithm with a small tweak to not recurse if an operator node has a cached value. This should be O(n+m) time (at most one arithmetic operation per node and at most one pointer lookup per edge). Explicitly:

evaluate(node) {
     if (node has value) {
          return node->value;
     } else {
          left = evaluate(node->left);
          right = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          node->value = val;
          return val;
     }
}