Tree Traversal
Basic Concept of Tree Traversal?
What is Tree Traversal?
Traversing a tree means visiting each node in a specified order. Linear data structures such as arrays and linked lists have only one logical way to traverse them, as each nodes has a single entry and exit point. Since each node in a tree does not have unique entry and exit points, trees can be traversed in different ways.
Types
There are mainly two types of tree traversals:
- Depth First Traversal
- Breadth First Traversal
Definition
1. Depth First Traversal: Depth First Traversal, as the name suggests, is a traversal technique, in which we traverse the tree in a depth first manner. This means that we start from the root node and keep going down the “depth” of the tree until we reach a leaf node (a node having no children) and then traverse back again to the node we started with.
2. Breadth First Traversal: Breadth First Traversal, also called level order traversal of the tree, is a traversal technique in which we traverse the tree in a "breadth first" manner. This means that nodes are traversed level-by-level in the tree from left to right.
Search vs Traversal
Traversal: Traversal of a tree involves examining every node in the tree.
Search: Search in a graph is an accelerated look-up, which involves visiting nodes in the graph in a systematic manner, and may or may not result in a visit to all nodes.