Inorder Traversal (Recursive) 🎯

Welcome to CodeYourCraft! Today, we're going to dive into the fascinating world of Data Structures and Algorithms, and specifically, we'll learn about Inorder Traversal of a Binary Tree using a recursive approach.

What is Inorder Traversal? 📝

Inorder Traversal is a technique used to traverse a Binary Search Tree (BST) in a specific way. The nodes are visited in a left-root-right (LDR) order, which means we first traverse the left subtree, then visit the root, and finally, we traverse the right subtree.

Why Inorder Traversal? 💡

Inorder traversal is used when we want to explore the nodes of a BST in a sorted order. It is particularly useful in applications like finding the minimum and maximum values in a BST, printing the nodes of a BST in sorted order, and many more.

Let's Write a Function 📝

First, let's define a function for Inorder Traversal in a recursive manner. We'll call this function inorderRecursive.

python

def inorderRecursive(node):
    # Base case: if the node is None, we return
    if node is None:
        return

    # Traverse the left subtree
    inorderRecursive(node.left)

    # Visit the current node
    print(node.data)

    # Traverse the right subtree
    inorderRecursive(node.right)

In the code above, we first check if the node is None. If it is, we simply return, as there's nothing more to traverse. Otherwise, we first traverse the left subtree by calling inorderRecursive(node.left). Then, we visit the current node by printing its data. Lastly, we traverse the right subtree by calling inorderRecursive(node.right).

Practical Application 🎯

Now, let's test our function with a simple Binary Search Tree.

python

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

root = Node(10)
root.left = Node(7)
root.right = Node(15)
root.left.left = Node(6)
root.left.right = Node(9)
root.right.left = Node(14)
root.right.right = Node(20)

inorderRecursive(root)

When you run this code, you'll see the nodes being printed in Inorder Traversal:

Quiz Time 💡

That's it for today! In the next lesson, we'll learn about Inorder Traversal using an iterative approach. Until then, keep practicing and happy coding! 🚀