What is tree traversal?

A tree is a widely used data structure in the world of programming. This structure, like its name, has branches and subdivisions, where each element in the tree is called a node.

For a tree to be “traversed” means that every node within the tree has been visited.

Where most data structures can be traversed in one or two ways by virtue of being linear, trees have a hierarchical structure and hence they can be traversed in multiple ways. Before we understand what these types are, we need to be familiar with a few terms.

• root: The first node of the tree (generally portrayed as the top-most node).
• parent: Each node that has a branch leading out from it, is called the parent of the subsequent node(s).
• children: The node(s) that extend from the parent are called children; the left and the right child depending on the placement of the node.

Types of traversals

Depth First Traversals

• Inorder: First, you traverse the left child and its sub-tree, visit the root and then the right child and its sub-tree.

• Preorder: Visit the root first, then traverse the left sub-tree, and then the right sub-tree.

• Postorder: Traverse the left sub-tree, then traverse the right sub-tree and then visit the root node.

Breadth First Traversals

• Levelorder: This traverses nodes by levels instead of sub-trees. First, visit the root node; then visit all children of the root node- left to right. Subsequently, go down levels till you reach the node that has no children- the leaf nodes.