Next: 4.1.3 The Tree ADT Up: 4.1 Introduction Previous: 4.1.1 Definitions

## 4.1.2 Preorder, Inorder, Postorder

If a tree is null, then the empty list is the preorder, inorder, and postorder listing of T

If T comprises a single node, that node itself is the preorder, inorder, and postorder list of T

Otherwise
1.
The preorder listing of T is the root of T, followed by the nodes of T1 in preorder, . . . , and the nodes of Tk in preorder.
2.
The inorder listing of T is the nodes of T1 in inorder, followed by the root r, followed by the nodes of T2 in inorder, . . . , and the nodes of Tk in inorder.
3.
The postorder listing of T is the nodes of T1 in postorder, . . . , the nodes of Tk in postorder, all followed by the root r.

Example: see Figure 4.2.

Preorder 1,2,3,5,8,9,6,10,4,7
Postorder 2,8,9,5,10,6,3,7,4,1
Inorder 2,1,8,5,9,3,10,6,7,4

Note that the order of appearance of the leaves is the same in all the three schemes. This is true in general.

Next: 4.1.3 The Tree ADT Up: 4.1 Introduction Previous: 4.1.1 Definitions
eEL,CSA_Dept,IISc,Bangalore