Traversals | Data Structures

Its a Topic of DataStructure which covers the Transversal

1. The process of systematically visiting all the nodes in a tree and performing some computation at each node in the tree is called a tree traversal. Tree Traversal (Definition)

2. Traversal H D B A C E G I K M O N L J F O G E N F B H

3. Traversals CODE for each Node: Name public void displayTree (Node n){ if( n == null ) return; printf ( n.data ); displayTree ( n.left ); displayTree ( n.right ); } Visit the node Visit the left subtree , if any. Visit the right subtree , if any. Preorder (N-L-R) public void displayTree (Node n){ if( n == null ) return; displayTree ( n.left ); printf ( n.data ); displayTree ( n.right ); } Visit the left subtree , if any. Visit the node Visit the right subtree , if any. Inorder (L-N-R) public void displayTree (Node n){ if( n == null ) return; displayTree ( n.left ); displayTree ( n.right ); printf ( n.data ); } Visit the left subtree , if any. Visit the right subtree , if any. Visit the node Postorder (L-R-N)

4. Preorder Traversal H D B A C E G I K M O N L J F O N K I J L E C A D H N-L-R

5. Inorder Traversal H D B A C E G I K M O N L J F L-N-R O N M L K J I H G F E D C B A Note: An inorder traversal of a BST visits the keys sorted in increasing order.

6. Postorder Traversal H D B A C E G I K M O N L J F L-R-N H L N O M J K I D F G E B C A

7. The children of any node in a binary tree are ordered into a left child and a right child A node can have a left and a right child, a left child only, a right child only, or no children The tree made up of a left child (of a node x) and all its descendents is called the left subtree of x Right subtrees are defined similarly 7 Binary-Tree Related Definitions 10 1 3 11 9 8 4 6 5 7 12

8. Assume: visiting a node is printing its label Preorder: 1 3 5 4 6 7 8 9 10 11 12 Inorder : 4 5 6 3 1 8 7 9 11 10 12 Postorder : 4 6 5 3 8 11 12 10 9 7 1 8 Label wise sequence 1 3 11 9 8 4 6 5 7 12 10

9. Assume: visiting a node is printing its data Preorder: 15 8 2 6 3 7 11 10 12 14 20 27 22 30 Inorder : 2 3 6 7 8 10 11 12 14 15 20 22 27 30 Postorder : 3 7 6 2 10 14 12 11 8 22 30 27 20 15 9 Node wise sequence 6 15 8 2 3 7 11 10 14 12 20 27 22 30

10. Observe the output of the inorder traversal of the BST example two slides earlier It is sorted This is no coincidence As a general rule, if you output the keys (data) of the nodes of a BST using inorder traversal, the data comes out sorted in increasing order 10 Application of Traversal Sorting a BST