Recursion is the answer, but you descend into each subtree before handling the operation:

int a = 1 + 2 - 3 * 4 - 5

to tree form:

(assign (a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

Inferring the type happens by first walking the left hand side, then the right hand side, and then handling the operator as soon as the operands' types are inferred:

(assign*(a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> descend into lhs

(assign (a*) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> infer a. a is known to be int. We're back in the assign node now:

(assign*(int:a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> descend into rhs, then into the lhs of the inner operators until we hit something interesting

(assign (int:a) (sub*(sub (add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub*(add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add*(1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add (1*) (2)) (mul (3) (4))) (5))

-> infer the type of 1, which is int, and return to the parent

(assign (int:a) (sub (sub (add*(int:1) (2)) (mul (3) (4))) (5))

-> go into the rhs

(assign (int:a) (sub (sub (add (int:1) (2*)) (mul (3) (4))) (5))

-> infer the type of 2, which is int, and return to the parent

(assign (int:a) (sub (sub (add*(int:1) (int:2)) (mul (3) (4))) (5))

-> infer the type of add(int, int), which is int, and return to the parent

(assign (int:a) (sub (sub*(int:add (int:1) (int:2)) (mul (3) (4))) (5))

-> descend into the rhs

(assign (int:a) (sub (sub (int:add (int:1) (int:2)) (mul*(3) (4))) (5))

etc., until you end up with

(assign (int:a) (int:sub (int:sub (int:add (int:1) (int:2)) (int:mul (int:3) (int:4))) (int:5))

Whether the assignment itself is also an expression with a type depends on your language.

The important takeaway: to determine the type of any operator node in the tree, you only have to look at its immediate children, which need to have a type assigned to them already.