C Academy · Lesson

Evaluating the Tree

Compute the result.

Evaluating the Tree is a free C Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

Walking the AST

Evaluation is a post-order traversal: compute the children first, then combine them with the node's operator. A number leaf simply returns its value.

This tree-walking interpreter is the simplest backend an interpreter can have.

The eval Signature

Our evaluator takes a node pointer and returns an integer. Because the tree is recursive, the function is too.

For floating-point languages you would return a double or a tagged value instead.

int eval(Node *n);  /* returns the integer value of the subtree */

Evaluating a Leaf

The base case stops the recursion. When a node is a number, its value is the answer for that subtree.

Every recursive descent must reach a base case, or it would never terminate.

int eval(Node *n) {
  if (n->kind == N_NUM) {
    return n->value;
  }
  /* ... handle N_BINOP below ... */
  return 0;
}

Evaluating a BinOp

For an operator node we recurse into both children, then apply the operator. Evaluating left before right gives the usual left-to-right order.

A switch on the operator character keeps the logic readable.

int eval(Node *n) {
  if (n->kind == N_NUM) return n->value;
  int l = eval(n->bin.left);
  int r = eval(n->bin.right);
  switch (n->bin.op) {
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

Guarding Division by Zero

Integer division by zero is undefined behavior in C and typically crashes the process. A safe interpreter checks the divisor first.

Reporting a clean runtime error beats an uncontrolled SIGFPE.

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

static int safe_div(int a, int b) {
  if (b == 0) {
    fprintf(stderr, "runtime error: division by zero\n");
    exit(1);
  }
  return a / b;
}

End-to-End Evaluation

Here a manually built tree for (2 + 3) * 4 is evaluated to 20. The same eval would run any tree the parser produces.

Run it to confirm the post-order traversal computes the right answer.

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

typedef struct Node {
  int is_num; int value;
  char op; struct Node *l, *r;
} Node;

static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }

static int eval(Node *n){
  if (n->is_num) return n->value;
  int l = eval(n->l), r = eval(n->r);
  switch (n->op){
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

int main(void){
  Node *ast = B('*', B('+', N(2), N(3)), N(4));
  printf("%d\n", eval(ast));
  return 0;
}

Stack Depth

Each nested operator adds a frame to the C call stack. A deeply nested expression like a thousand parentheses can overflow it.

Most real expressions are shallow, but a robust interpreter may convert to an explicit stack to be safe.

Folding Constants

Because evaluation and parsing share the tree, you can optimize. If both children of a binop are numbers, you may compute the result once and replace the node with a leaf.

This constant folding is a classic interpreter optimization.

/* fold: collapse a binop of two literals into one literal */
Node *fold(Node *n) {
  if (n->kind == N_BINOP) {
    n->bin.left  = fold(n->bin.left);
    n->bin.right = fold(n->bin.right);
    if (n->bin.left->kind == N_NUM &&
        n->bin.right->kind == N_NUM)
      return num(eval(n));
  }
  return n;
}

Freeing the Tree

Heap-allocated nodes must be released. A post-order free visits children before the parent, mirroring evaluation.

Forgetting this leaks memory on every expression the interpreter runs.

void free_tree(Node *n) {
  if (n->kind == N_BINOP) {
    free_tree(n->bin.left);
    free_tree(n->bin.right);
  }
  free(n);
}

Unary Minus

Negation such as -5 needs handling. One option is a unary node; another is to desugar -x into 0 - x at parse time.

Either way, evaluation stays a simple recursive walk.

/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
  bump();
  return binop('-', num(0), parse_factor());
}

Why Tree-Walking?

Tree-walking interpreters are easy to write and debug, at some speed cost. Languages like early Ruby used this model before moving to bytecode VMs.

Next we add variables so the interpreter can remember values.

Quick Check

Reason about the order in which eval visits nodes.

Recap

You implemented a recursive evaluator: leaf base case, binop recursion, a division-by-zero guard, plus tree freeing and constant folding.

The interpreter now computes any arithmetic AST. Adding variables is next.

Frequently asked questions

Is the “Evaluating the Tree” lesson free?

Yes — the full text of “Evaluating the Tree” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.

What will I learn in “Evaluating the Tree”?

Compute the result. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start C Academy?

No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Evaluating the Tree” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this C Academy lesson?

Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to C Academy