Python Data Structure and Algorithm Tutorial – Tree Traversal

Hits: 1

Tree Traversal – inorder, preorder and postorder

 

In this tutorial, you will learn about different tree traversal techniques. Also, you will find working examples of different tree traversal methods in C, C++, Java and Python.

Traversing a tree means visiting every node in the tree. You might, for instance, want to add all the values in the tree or find the largest one. For all these operations, you will need to visit each node of the tree.

Linear data structures like arrays, stacks, queues, and linked list have only one way to read the data. But a hierarchical data structure like a tree can be traversed in different ways.

sample tree to learn tree traversal - root node contains 1 with leftchild as 12 and right child as 9. The left child of root further has left child 5 and right child 6
Tree traversal

Let’s think about how we can read the elements of the tree in the image shown above.

Starting from top, Left to right

1 -> 12 -> 5 -> 6 -> 9

Starting from bottom, Left to right

5 -> 6 -> 12 -> 9 -> 1

Although this process is somewhat easy, it doesn’t respect the hierarchy of the tree, only the depth of the nodes.

Instead, we use traversal methods that take into account the basic structure of a tree i.e.

struct node {
    int data;
    struct node* left;
    struct node* right;
}

The struct node pointed to by left and right might have other left and right children so we should think of them as sub-trees instead of sub-nodes.

According to this structure, every tree is a combination of

  • A node carrying data
  • Two subtrees
root node with left subtree and right subtree
Left and Right Subtree

Remember that our goal is to visit each node, so we need to visit all the nodes in the subtree, visit the root node and visit all the nodes in the right subtree as well.

Depending on the order in which we do this, there can be three types of traversal.


Inorder traversal

  1. First, visit all the nodes in the left subtree
  2. Then the root node
  3. Visit all the nodes in the right subtree
inorder(root->left)
display(root->data)
inorder(root->right)

Preorder traversal

  1. Visit root node
  2. Visit all the nodes in the left subtree
  3. Visit all the nodes in the right subtree
display(root->data)
preorder(root->left)
preorder(root->right)

Postorder traversal

  1. Visit all the nodes in the left subtree
  2. Visit all the nodes in the right subtree
  3. Visit the root node
postorder(root->left)
postorder(root->right)
display(root->data)

Let’s visualize in-order traversal. We start from the root node.

outlining left subtree, right subtree and root node
Left and Right Subtree

We traverse the left subtree first. We also need to remember to visit the root node and the right subtree when this tree is done.

Let’s put all this in a stack so that we remember.

we put the left subtree, root node and right subtree in a stack in that order so that we can display root node and traverse right subtree when we are done with left subtree
Stack

Now we traverse to the subtree pointed on the TOP of the stack.

Again, we follow the same rule of inorder

Left subtree -> root -> right subtree

After traversing the left subtree, we are left with

situation of stack after traversing left subtree, stack now contains the elements of left subtree, followed by root, followed by right child of root
Final Stack

Since the node “5” doesn’t have any subtrees, we print it directly. After that we print its parent “12” and then the right child “6”.

Putting everything on a stack was helpful because now that the left-subtree of the root node has been traversed, we can print it and go to the right subtree.

After going through all the elements, we get the inorder traversal as

5 -> 12 -> 6 -> 1 -> 9

We don’t have to create the stack ourselves because recursion maintains the correct order for us.


Python Examples

/* Tree traversal in Python */


class Node:
    def __init__(self, item):
        self.left = None
        self.right = None
        self.val = item


def inorder(root):

    if root:
        /* Traverse left */
        inorder(root.left)
        /* Traverse root */
        print(str(root.val) + "->", end='')
        /* Traverse right */
        inorder(root.right)


def postorder(root):

    if root:
        /* Traverse left */
        postorder(root.left)
        /* Traverse right */
        postorder(root.right)
        /* Traverse root */

 

 

Python Example for Beginners

Two Machine Learning Fields

There are two sides to machine learning:

  • Practical Machine Learning:This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.
  • Theoretical Machine Learning: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.

Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes

Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!

Latest end-to-end Learn by Coding Recipes in Project-Based Learning:

Applied Statistics with R for Beginners and Business Professionals

Data Science and Machine Learning Projects in Python: Tabular Data Analytics

Data Science and Machine Learning Projects in R: Tabular Data Analytics

Python Machine Learning & Data Science Recipes: Learn by Coding

R Machine Learning & Data Science Recipes: Learn by Coding

Comparing Different Machine Learning Algorithms in Python for Classification (FREE)

Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.  

Google –> SETScholars