• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
PythonForBeginners.com

PythonForBeginners.com

Learn By Example

  • Home
  • Learn Python
    • Python Tutorial
  • Categories
    • Basics
    • Lists
    • Dictionary
    • Code Snippets
    • Comments
    • Modules
    • API
    • Beautiful Soup
    • Cheatsheet
    • Games
    • Loops
  • Python Courses
    • Python 3 For Beginners
You are here: Home / Data Structures / In-order Tree Traversal in Python

In-order Tree Traversal in Python

Author: Aditya Raj
Last Updated: September 9, 2021

You might have studied algorithms to traverse a python dictionary, a list, or a tuple. In this article, we will study the in-order traversal algorithm to traverse a binary tree.  We will also discuss the implementation of the algorithm. 

Table of Contents
  1. What is an In-order tree traversal algorithm?
  2. Algorithm for In-order Traversal
  3. Implementation of In-order tree traversal in Python
  4. Conclusion

What is an In-order tree traversal algorithm?

In-order tree traversal algorithm is a depth first traversal algorithm. It means that we traverse the children of a node before traversing its siblings. In this way, we traverse to the maximum depth, print the elements till the last node and then come back to the top to print other elements. 

The algorithm is termed as in-order traversal algorithm because, when we traverse a binary search tree using this algorithm, The elements of the tree are printed in increasing order of their value. 

Algorithm for In-order Traversal

We know that, In a binary search tree, The left child of any node contains an element less than the current node and the right child of a node contains an element greater than the current node. So, to print the elements in order, we will have to print the left child first, then the current node and the right child at last. This same rule will be used to print each node of the tree.  

We will start from the root node, will traverse the left child or left sub-tree of the current node and then we will  traverse the current node. At last we will traverse the right child or right sub-tree of the current node. We will perform this operation recursively till all the nodes are traversed.

To understand the concept better, let us use an example binary search tree and traverse it using the In-order binary tree traversal algorithm.

In-order Tree Traversal in Python
In-order Tree traversal

Here, we will start from root node 50. Before printing 50, we have to traverse the left subtree of 50. So, we will go to 20. Before printing 20, we have to traverse the left subtree of 20. So, we will go to 11. As 11 has no children, we will print 11 and move upwards to 20. After printing 20, we will traverse right subtree of 20. As 22 has no children, we will print 22 and move upwards to 50. At 50, its left subtree has been traversed, so we will print 50. After that we will traverse the right subtree of 50 using the same process. The in-order traversal of whole tree is : 11, 20, 22, 50, 52, 53, 78.

Implementation of In-order tree traversal in Python

The algorithm for in-order tree traversal can be formulated as follows.

  1. Recursively Traverse the left sub-tree.
  2. Print the root node.
  3. Recursively Traverse the right sub-tree.

Here, we print the element in the node only if it is a leaf node or all the elements in its left subtree have already been printed.

We will now implement the above algorithm in python and will execute it for the binary search tree given in the above example.

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def inorder(root):
    # if root is None,return
    if root == None:
        return
    # traverse left subtree
    inorder(root.leftChild)
    # print the current node
    print(root.data, end=" ,")
    # traverse right subtree
    inorder(root.rightChild)


def insert(root, newValue):
    # if binary search tree is empty, create a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Inorder traversal of the binary tree is:")
inorder(root)

Output:

Inorder traversal of the binary tree is:
11 ,20 ,22 ,50 ,52 ,53 ,78 ,

Conclusion

In this article, we have discussed the In-order tree traversal algorithm in Python. In next articles, we will implement other tree traversal algorithms such as preorder tree traversal, and postorder tree traversal algorithm. To learn more about other data structures, you can read this article on Linked List in Python.

Related

Recommended Python Training

Course: Python 3 For Beginners

Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.

Enroll Now

Filed Under: Data Structures Author: Aditya Raj

More Python Topics

API Argv Basics Beautiful Soup Cheatsheet Code Code Snippets Command Line Comments Concatenation crawler Data Structures Data Types deque Development Dictionary Dictionary Data Structure In Python Error Handling Exceptions Filehandling Files Functions Games GUI Json Lists Loops Mechanzie Modules Modules In Python Mysql OS pip Pyspark Python Python On The Web Python Strings Queue Requests Scraping Scripts Split Strings System & OS urllib2

Primary Sidebar

Menu

  • Basics
  • Cheatsheet
  • Code Snippets
  • Development
  • Dictionary
  • Error Handling
  • Lists
  • Loops
  • Modules
  • Scripts
  • Strings
  • System & OS
  • Web

Get Our Free Guide To Learning Python

Most Popular Content

  • Reading and Writing Files in Python
  • Python Dictionary – How To Create Dictionaries In Python
  • How to use Split in Python
  • Python String Concatenation and Formatting
  • List Comprehension in Python
  • How to Use sys.argv in Python?
  • How to use comments in Python
  • Try and Except in Python

Recent Posts

  • Count Rows With Null Values in PySpark
  • PySpark OrderBy One or Multiple Columns
  • Select Rows with Null values in PySpark
  • PySpark Count Distinct Values in One or Multiple Columns
  • PySpark Filter Rows in a DataFrame by Condition

Copyright © 2012–2025 · PythonForBeginners.com

  • Home
  • Contact Us
  • Privacy Policy
  • Write For Us