Expression Tree of logical expression

Question

I need to transform this: (a < b)∧(b < c)∨(c < d) expression into an expression tree, but I can't figure out a way that looks correct. Here is what I got:

Answer 1

I'm predicting this will be a long answer, because I will go through the general thinking process for achieving a solution. For the inpatient, the solution is at the end.

Is your solution correct?

Well, it depends. Your picture would be totally correct if ∨ took precedence over ∧, in which case you would need to apply ∧ only after (b < c) ∨ (c < d) has a result. It would also be correct if you forced precedence using parenthesis like so:

(a < b) ∧ ( (b < c) ∨ (c < d) )

That said, when talking about operator precedence, typically ∧/and has precedence over ∨/or. When precedence is the same, the evaluation happens from left to right, meaning the right side depends on the result of the left side.

The highest the precedence of an operator, the lower it appears in the tree.

The rest of the answer will assume the usual operator precedence.

How to approach this problem?

The best approach to this sort of problems is to decompose the expression. Even better, if we decompose using the prefix/polish notation, it will be more natural to build up the tree later.

Given: (a < b) ∧ (b < c) ∨ (c < d)

Let's decompose it into parts:

x = (a < b), which translates to prefix: < a b
y = (b < c), which translates to prefix: < b c
z = (c < d), which translates to prefix: < c d

We now have 3 inequality expressions decomposed as x, y and z.

Now to the logical operators.

i = x ∧ y, which translates to prefix: ∧ x y
j = i ∨ z, which translates to prefix: ∨ i z

We now have 2 logical expressions decomposed as i and j. Note how they depend on x, y, z. But also, that j depends on i. Dependencies are important because you know tree leaves have no dependencies.

How to build the tree?

To sum up, this is what we decomposed from the original expression:

x = < a b
y = < b c
z = < c d
i = ∧ x y
j = ∨ i z

Let's approach it bottom-up.

Considering the dependencies, the leaves are obviously the most independent elements: a, b, c and d.

Let's build the bottom of the tree considering all appearances of these independent elements in the decomposition we just made (b and c appear twice, we put them twice).

a   b   b   c   c   d

Now let's build x, y and z which depends only on a, b, c and d. I'll be using / and \ for building my ASCII art as equivalent to your picture lines.

  x       y       z
  <       <       <
 / \     / \     / \
a   b   b   c   c   d

Now as we've seen, i depends only on x and y. So we can put it there now. We can't add j just yet, because we need i to be there first.

      i
      ∧
    /   \
  x       y       z
  <       <       <
 / \     / \     / \
a   b   b   c   c   d

Now we are just missing j, which depends on i and z.

           j
           ∨
         /   \      
        /     \
      i        \
      ∧         \
   /     \       \
  x       y       z
  <       <       <
 / \     / \     / \
a   b   b   c   c   d

And we have a full expression tree. As you see, each dependency level will result in a tree level.

To be completely accurate, a Breadth-First Search in this tree would have to consider that z is on the same level of i, so the correct representation of the tree would have to put z one level higher:

            j
            ∨
         /     \      
        /       \
      i          z
      ∧          <
   /     \      / \
  x       y    c   d
  <       <       
 / \     / \     
a   b   b   c

Just one more note, for it to be completely clear, for the expression (a < b) ∧ ( (b < c) ∨ (c < d) ), the decomposition result would be:

x = < a b
y = < b c
z = < c d
j = ∨ y z
i = ∧ x j

Which would, in turn, result in the tree in your picture.

Hope this helps your future endeavours on building expression trees.