Data Structures and Algorithms - Old Questions

13. Write short notes on:

    a. Tree traversal

    b. Circular queue

a) Tree Traversal

The tree traversal is a way in which each node in the tree is visited exactly once in a symmetric manner.

The binary tree can be traverse in 3 ways:

1. Pre-order traversal

2. In-order traversal

3. Post-order traversal

1. Pre-order Traversal: In Pre-Order traversal, the root node is visited before left child and right child nodes. In this traversal, the root node is visited first, then its left child and later its right child. This is performed recursively for all nodes in the tree. For e.g.

The preorder traversal output of the given above tree is: A B D H I E C F G

2. In-order Traversal: In In-Order traversal, the root node is visited between left child and right child. In this traversal, the left child node is visited first, then the root node is visited and later we go for visiting right child node. This is performed recursively for all nodes in the tree. For e.g.

The inorder traversal output of the given tree is: H D I B E A F C G

3. Post-order Traversal: In Post-Order traversal, the root node is visited after left child and right child. In this traversal, left child node is visited first, then its right child and then its root node. This is recursively performed until the right most node is visited. For e.g.

The post-order traversal output of the given above tree is: H I D E B F G C A