CODEWITHSUNDEEP
javaexpressionexpression-trees
LPD
LPD

Reputation: 2883

Expression Trees as Binary Trees

I have a simple question.

Why all expression trees are modeled as "Binary Trees" and not as 'N ary trees' ?

Is there any reason why an expression cannot be modeled using N-ary tree?

Upvotes: 0

Views: 382

Answers (2)

user207421
user207421

Reputation: 310885

Why all expression trees are modeled as "Binary Trees" and not as 'N ary trees' ?

They aren't. Expression tree internal nodes are operators, and operators can be unary, binary, or ternary at least, maybe more.

Is there any reason why an expression cannot be modeled using N-ary tree?

They are.

Upvotes: 0

svick
svick

Reputation: 244767

There are some good reasons why expression trees are often binary:

  1. The most common expression trees represent arithmetic operations (+, -, *, /) or logical predicates (AND, OR, NOT, XOR). There are all binary (and unary) operations, so binary trees make the most sense. You could have for example n-ary +, but that just complicates things without good reason.

  2. From a more theoretical perspective, if you have an n-ary tree, you can represent it using an equivalent binary tree without losing anything. Using the n-ary + example the following trees (one n-ary and one binary) could be considered the same:

      +       +
 /|\     / \
a b c   +   c
       / \
      a   b

On the other hand, there are libraries that use n-ary expression trees where they make sense. For example, C# expression trees (from the System.Linq.Expressions namespace) use n-ary trees for invocation expressions. So, the expression f(a, b, c) would be represented as InvocationExpression that looks like this:

  f
 /|\
a b c

Upvotes: 2

Related Questions