Tree traversal techniques in Python using Recursion

A tree is a hierarchical data structure that stores the information naturally in the form of a hierarchy style. A tree is one of the most powerful and advanced data structures. It is a non-linear data structure compared to arrays, linked lists, stack, and queue.

Trees contain nodes connected to each other. A node may or may not have its child. It represents the nodes connected by edges. To read each and every node we need some traversal techniques. There are many traversal techniques like in-order, pre-order, post-order, level-order, etc.

Let’s discuss in-order, pre-order, and post-order using recursion in python.

In-Order Tree Traversal:

There are usually three steps in a traversal technique.

1 → Move to the left child.

2 → visit the current node. (dealing with that node)

3 → Move to the right child.

Following the 3 steps in the above manner gives In-order traversal.

Pre-Order Tree Traversal:

Pre-order traversal first visits the current node and then check for the left node if any.

1 → visit the current node. (dealing with that node)

2 → Move to the left child.

3 → Move to the right child.

Following the 3 steps in the above manner gives Pre-order traversal.

Post-Order Tree Traversal:

Pre-order traversal first checks for the left node and later right node if any and then visits the current node.

1 → Move to the left child.

2 → Move to the right child.

3 → visit the current node. (dealing with that node)

Following the 3 steps in the above manner gives Post-order traversal.

The python code for the tree traversal techniques is written below.

We create a class Tree that comes with a left child, right child, and data block for each instance. insert_node performs the task of inserting data into the binary tree by holding its properties.

We use recursion for performing the in-order, pre-order, and post-order tree traversals. For example, in in-order traversal first, we need to check if the left node exists, so the in-order function is called for every node with the left child as its parameter. The base case for this recursion will be when there is no left child further.

Thanks For Reading, Follow Me For More :)