Page 1 :
As with lists, we would like to be able to traverse through all nodes in our tree. Tree traverga}, is the process of visiting each node in the tree exactly once., , Problem: What order should the nodes be visisted in?, , * Top-down?, * Left-to-right?, * Bottom-up?, , In tree creation we take three parameters node, left and right child, so traversing of, binary tree means traversing of node, left sub-tree and right sub-tree. If root is denoted as, n, left sub-tree as L and right sub-tree as R, then there will be six combinations of traversals, NRL, NLR, LNR, LRN, RNL, RLN. But only three are standard, NLR (node-left-right), LNR, (left-node-right) and LRN (left-right-node) traversal. We can see left sub-tree is always traversed, before right sub-tree. NLR is called pre-order LNR is inorder NRL is post-order., , These traversals are as:, , Preorder (NLR Traversal), 1. Visit the root., 2. Traverse the left sub-tree of root., 3. Traverse the right sub-tree of root., , Inorder Traversal (LNR Traversal), 1. Traverse the left sub-tree of root., , 2. Visit the root., 3. Traverse the right sub-tree of root., , Postorder (LRN Traversal), 1. Traverse the left sub-tree of root., 2. Traverse the right sub-tree of root., 3. Visit the root., , , , , , , , That is,, | Pre order Root Left sub-tree Right sub-tree, | In-order Left-sub-tree Root _ Right sub-tree, Post-order Left-sub-tree Right sub-tree Root, , , , , , , , , , Scanned with CamScanner

Page 3 :
Pre-order Traversal:, , , , , , 1. Root, 2. Left subtree, 3. Right subtree, , , , , , , , Fig. 8.20., Here numbers represent the sequence of visited node. So the nodes are visited in pre, order traversal as., , , , , , ABDEFCGHIKL, , In this A is the root node, so visit it. Once the root node of the tree is visited it goes to the, root of the left subtree i.e,, node B then left child, ice, node D. Then the root of right sub-treé, i.e., node E then left child i.e., node F., , Now it goes to the root of the right sub-tree of root node, i.e., node C, then left child, i.e, G. Then root of right sub-tree of node C, i.e, node H, then root of left sub-tree of H, ie. node, J, then left child of J, i.e., node K, Then right child of node H, ive., L., , , , , , Scanned with CamScanner

Page 4 :
jnorder Traversal:, , , , , , 1. Left subtree, 2. Root node, 3. Right subtree, , Fig. 8.21., , The nodes are visited in inorder as:, , , , , , DBFEAGCKIJHL, , , , , , Postorder Traversal:, , , , Fig. 8.22., , The nodes are visited in post-order as:, , , , DFEBGKIJLHCA, , , , , , , , Example: Apply each traversal techniques in binary tree., , , , Scanned with CamScanner