Converting a binary tree expression to infix notation using the BAIT algorithm

Abstract

When we evaluate an expression (be it mathematical, Boolean, or other) we have to deal with the precedence and associativity rules on operators (this is because the notation we use is infix). Following these rules an expression can be represented by means of a tree hierarchy and vice-versa an expression tree can be transformed into a linear infix expression. To derive the linear infix expression from an expression-tree the algorithm given in textbooks consists of the use of the inorder traversal (IT) enriched with placing brackets that themselves impose the operator order expressed implicitly in the tree. The author devised the BA (Brackets Algorithm) which consists of adding brackets inside the terminal nodes of the tree (call this tree TB – Tree with Brackets). If IT is applied on TB (without any need of augmenting the code of IT) then the equivalent linear infix expression will be delivered. Proof is given in the paper of the correctness of the BA. The BAIT algorithm consists of the application of the BA and the IT algorithms in succession.