prints the resulting treethe empty tree results in no printingthe subtree at level in first printing its own left subtreethen the nodeproperly indented by preceding it with tabsand finally in printing its right subtree basic operations on binary trees there are many tasks that may have to be perfomed on tree structurea common one is that of executing given operation on each element of the tree is then understood to be parameter of the more general task of visting all nodes oras it is usually calledof tree traversal if we consider the task as single sequential processthen the individual nodes are visited in some specific order and may be considered as being laid out in linear arrangement in factthe description of many algorithms is considerably facilitated if we can talk about processing the next element in the tree based in an underlying order there are three principal orderings that emerge naturally from the structure of trees like the tree structure itselfthey are conveniently expressed in recursive terms referring to the binary tree in fig in which denotes the root and and denote the left and right subtreesthe three orderings are rab (visit root before the subtrees preorder inorder postorderarb abr (visit root after the subtreesr fig binary tree traversing the tree of fig and recording the characters seen at the nodes in the sequence of encounterwe obtain the following orderings preorder inorder postorder+ + + we recognize the three forms of expressionspreorder traversal of the expression tree yields prefix notationpostorder traversal generates postfix notationand inorder traversal yields conventional infix notationalthough without the parentheses necessary to clarify operator precedences let us now formulate the three methods of traversal by three concrete programs with the explicit parameter denoting the tree to be operated upon and with the implicit parameter denoting the operation to be performed on each node assume the following definitionstype node pointer to record leftrightnode end the three methods are now readily formulated as recursive proceduresthey demonstrate again the fact that operations on recursively defined data structures are most conveniently defined as recursive algorithms