Data Structures Trees Question:
Do you know implementation of traversal of a binary tree?
Answer:
Binary tree traversal is a process of visiting each and every node of the tree. The two fundamental binary tree traversals are ‘depth-first’ and ‘breadth-first’.
The depth-first traversal are classified into 3 types, namely, pre-order, in-order and post-order.
Pre-order: Pre-order traversal involves visiting the root node first, then traversing the left sub tree and finally the right sub tree.
In-order: In-order traversal involves visiting the left sub tree first, then visiting the root node and finally the right sub tree.
Post-order: Post-order traversal involves visiting the left sub tree first, then visiting the right sub tree and finally visiting the root node.
The breadth-first traversal is the ‘level-order traversal’. The level-order traversal does not follow the branches of the tree. The first-in first-out queue is needed to traversal in level-order traversal.
The depth-first traversal are classified into 3 types, namely, pre-order, in-order and post-order.
Pre-order: Pre-order traversal involves visiting the root node first, then traversing the left sub tree and finally the right sub tree.
In-order: In-order traversal involves visiting the left sub tree first, then visiting the root node and finally the right sub tree.
Post-order: Post-order traversal involves visiting the left sub tree first, then visiting the right sub tree and finally visiting the root node.
The breadth-first traversal is the ‘level-order traversal’. The level-order traversal does not follow the branches of the tree. The first-in first-out queue is needed to traversal in level-order traversal.
| Previous Question | Next Question |
| What is threaded binary tree. Explain its common uses? | Can you explain implementation of deletion from a binary tree? |