sizeisempty ( iteratorpositions (nreplace ( rootparentchildrenleftright ( haslefthasrightisinternalisexternalisroot ( traversals of binary trees as with general treesbinary tree computations often involve traversals building an expression tree consider the problem of constructing an expression tree from fully parenthesized arithmetic expression of size (recall example and code fragment in code fragment we give algorithm buildexpression for building such an expression treeassuming all arithmetic operations are binary and variables are not parenthesized thusevery parenthesized subexpression contains an operator in the middle the algorithm uses stack while scanning the input expression looking for variablesoperatorsand right parentheses when we see variable or operator xwe create single-node binary tree twhose root stores and we push on the stack when we see right parenthesis")"we pop the top three trees from the stack swhich represent subexpression ( we then attach the trees for and to the one for oand push the resulting tree back on we repeat this until the expression has been processedat which time the top element on the stack is the expression tree for the total running time is (