Tree Applications

Syntax Trees

What is a Syntax Tree?

A syntax tree (also called an expression tree, or more generally an Abstract Syntax Tree/AST) captures the grammatical structure of an expression or piece of code, rather than its raw text. For arithmetic expressions specifically, every operator becomes an internal node with its operands as children, and every literal value becomes a leaf. The shape of the tree, not the order characters appear on the page, is what encodes precedence and grouping.

How Does It Work?

Building one from an infix expression like "3 + 4 * (2 - 1)" requires a parser that respects operator precedence and parentheses — multiplication and division bind tighter than addition and subtraction, and anything inside parentheses is parsed as its own self-contained sub-expression first. A common approach is recursive-descent parsing: one function handles addition/subtraction terms, which calls another handling multiplication/division factors, which calls another handling numbers and parenthesized groups — the recursive call structure mirrors the grammar's precedence levels directly.

Once built, the tree makes evaluation and notation conversion almost mechanical, because each is just a different tree traversal. Evaluating the expression is a post-order traversal: recursively compute both children's values first, then apply the operator to combine them — by the time an operator node is processed, both its operands are already known. Reading the tree with a pre-order traversal produces prefix notation, and post-order traversal produces postfix notation; both eliminate the need for parentheses or precedence rules entirely, since the tree structure alone determines evaluation order.

The syntax tree for 3 + 4 * (2 - 1) — its shape alone encodes precedence, no parentheses needed

Algorithm Steps

Tokenize the input into numbers, operators, and parentheses
Parse recursively, respecting precedence:
- Parse an expression as a sequence of terms joined by + or -
- Parse a term as a sequence of factors joined by * or /
- Parse a factor as either a number, or a parenthesized sub-expression parsed from scratch
Each operator encountered becomes an internal node whose children are the two operands just parsed
To evaluate: post-order traverse the tree, computing both children before applying the operator at each node

Time Complexity

Parsing Time: O(n) — each token is consumed exactly once by the recursive-descent parser.
Evaluation Time: O(n) — each node in the tree is visited exactly once during the post-order traversal.
Space Complexity: O(n) for the tree, plus O(h) recursion stack depth for parsing and evaluating.

Time Complexity Analysis

Syntax trees are the intermediate representation nearly every compiler and interpreter builds after parsing source code, before generating machine code or bytecode from it. The same idea powers calculator apps, spreadsheet formula engines, and query planners in databases — anywhere text needs to become something with an unambiguous, machine-processable structure.

Daily DSA Challenge by Scale Engineer

Parse an arithmetic expression into a syntax tree, then evaluate it bottom-up

Enter an arithmetic expression and parse it into a tree

Syntax Tree

Parse an expression to see its tree here

Operator nodeOperand (leaf)RootCurrently combining

Test Your Knowledge before moving forward!

Syntax Trees Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Syntax Tree Implementation

function tokenize(input) {
  const tokens = [];
  let i = 0;
  while (i < input.length) {
    const c = input[i];
    if (/\s/.test(c)) { i++; continue; }
    if (/[0-9.]/.test(c)) {
      let num = "";
      while (i < input.length && /[0-9.]/.test(input[i])) { num += input[i]; i++; }
      tokens.push({ type: "num", value: parseFloat(num) });
      continue;
    }
    if ("+-*/()".includes(c)) { tokens.push({ type: c }); i++; continue; }
    throw new Error(`Unexpected character "${c}"`);
  }
  return tokens;
}

// Recursive-descent parser: expression -> term -> factor mirrors precedence.
function parseExpression(input) {
  const tokens = tokenize(input);
  let pos = 0;
  const peek = () => tokens[pos];
  const consume = () => tokens[pos++];

  function parseExpr() {
    let node = parseTerm();
    while (peek() && (peek().type === "+" || peek().type === "-")) {
      const op = consume().type;
      node = { type: "op", op, left: node, right: parseTerm() };
    }
    return node;
  }
  function parseTerm() {
    let node = parseFactor();
    while (peek() && (peek().type === "*" || peek().type === "/")) {
      const op = consume().type;
      node = { type: "op", op, left: node, right: parseFactor() };
    }
    return node;
  }
  function parseFactor() {
    const t = peek();
    if (t.type === "(") {
      consume();
      const node = parseExpr();
      consume(); // closing ')'
      return node;
    }
    consume();
    return { type: "num", value: t.value };
  }

  return parseExpr();
}

// Post-order evaluation: both children resolve before the operator combines them.
function evaluate(node) {
  if (node.type === "num") return node.value;
  const left = evaluate(node.left);
  const right = evaluate(node.right);
  switch (node.op) {
    case "+": return left + right;
    case "-": return left - right;
    case "*": return left * right;
    case "/": return left / right;
  }
}

// Usage example
const tree = parseExpression("3 + 4 * (2 - 1)");
evaluate(tree); // 7

Done With the Learning

Mark Syntax Trees as done and view it on your dashboard

Explore Other Tree Topics

Decision Trees

Huffman Coding

Heap Sort

Post-order Traversal

Structure & Properties