Introduction

Binary Tree Traversal is a method of visiting all the nodes in a binary tree in a specific order. The traversal algorithms are essential for many operations, including searching, sorting, and printing the tree structure.
In this tutorial, we will explore three common types of binary tree traversal:

• In-order Traversal: Visits nodes in the order left, root, right.
• Pre-order Traversal: Visits nodes in the order root, left, right.
• Post-order Traversal: Visits nodes in the order left, right, root.

In this tutorial, we will implement these three traversal techniques using Python.

Objective

The objective of this tutorial is to help you implement the three basic binary tree traversal algorithms (In-order, Pre-order, Post-order) using Python. By the end, you will understand how to traverse a binary tree and how each algorithm works.

Python Code for Binary Tree Traversal

# Binary Tree Traversal Algorithms in Python

# Create a Node class for the binary tree
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

# In-order traversal (Left, Root, Right)
def inorder(root):
    if root:
        inorder(root.left)
        print(root.value, end=" ")
        inorder(root.right)

# Pre-order traversal (Root, Left, Right)
def preorder(root):
    if root:
        print(root.value, end=" ")
        preorder(root.left)
        preorder(root.right)

# Post-order traversal (Left, Right, Root)
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.value, end=" ")

# Driver code to test the traversal methods
if __name__ == "__main__":
    # Creating a simple binary tree:
    #         1
    #        / \
    #       2   3
    #      / \ 
    #     4   5
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    print("In-order Traversal: ", end="")
    inorder(root)  # Output: 4 2 5 1 3
    print()

    print("Pre-order Traversal: ", end="")
    preorder(root)  # Output: 1 2 4 5 3
    print()

    print("Post-order Traversal: ", end="")
    postorder(root)  # Output: 4 5 2 3 1
    print()
            

Program Explanation

The program implements a simple binary tree with the following components:

• Node Class: This class represents a node in the binary tree. It has three attributes: value (stores the value of the node), left (points to the left child), and right (points to the right child).
• Traversal Functions:
  • inorder(root): This function recursively performs an in-order traversal. It first visits the left subtree, then the root node, and finally the right subtree.
  • preorder(root): This function performs a pre-order traversal. It first visits the root node, then the left subtree, and finally the right subtree.
  • postorder(root): This function performs a post-order traversal. It first visits the left subtree, then the right subtree, and finally the root node.
• Driver Code: This code creates a binary tree with a root node (value 1), and two child nodes (values 2 and 3), further expanding node 2 with left and right children (values 4 and 5). It then calls each of the traversal functions to print the traversal output.

How to Run the Program

To run the program, follow these steps:

• Ensure that you have Python installed on your computer. If not, you can download and install it from here.
• Copy the code provided above into a text editor and save it with a `.py` extension (e.g., `binary_tree_traversal.py`).
• Open a terminal or command prompt window.
• Navigate to the folder where you saved the Python file.
• Type the following command to run the program:

  python binary_tree_traversal.py

• You should see the output of each traversal algorithm printed in the terminal.