# How to solve a Simple Linear Equation using a binary tree data structure

i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so:

        =
/     \
+       -
/ \     / \
x   3   *   2
/ \
3   x


now that i have the expression in this format could someone please explain how can i obtain the value of x, any help is appreciated and if you have an alternative method that may make it easier i would love to hear it thank you

• Interesting question (+1). I suspect that there might be a way to go from the parse tree to a solution (if one exists), but it's not obvious to me. For example, you need to ensure that both the left and right subtrees produce a linear expression. That would mean that the subtrees of any * node can't both be expressions involving $x$. Given these constraints, as I said, I suspect that you could manipulate the parse tree to get the solution, but I'll have to look at it later. For practical purposes, I'd just use @Yuval's idea. – Rick Decker Apr 7 '15 at 1:02

You don't really want to solve the equation using this representation. You want to convert it into a normal form such as $ax+b = 0$, from which you can read the solution. The first step would be to replace $P = Q$ with $P - Q = 0$. The second step would be to normalize $P - Q$ to some standard form, say a polynomial (or in you case, perhaps $ax+b$). One way to do this is to convert each subexpression into normal form recursively, using rules for handling leaves such as numerical constants and $x$, and mathematical operations such as $+,-,\times$.