DSA Tutorial

🌿 Inorder Traversal in DSA (Binary Tree)

Inorder traversal is a depth-first traversal method where we visit:

          1
         / \
        2   3
       / \
      4   5

      ➤ Inorder Traversal Output: 4 2 5 1 3
      

🧠 Inorder Traversal Algorithm

• Recursively traverse the left subtree.
• Visit the root node.
• Recursively traverse the right subtree.

💻 Python Code

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

def inorder(root):
    if root:
        inorder(root.left)       # Left
        print(root.val, end=" ") # Root
        inorder(root.right)      # Right
  

⚙️ Output

🌐 Real-Time Use Case

🔄 Iterative Inorder Traversal (Using Stack)

When recursion depth is a concern, we can use a stack to simulate inorder traversal:

def inorder_iterative(root):
    stack = []
    current = root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        print(current.val, end=" ")
        current = current.right
  

📌 Summary

• Visits nodes in Left → Root → Right order.
• Useful in Binary Search Trees for sorted output.
• Can be implemented recursively or using a stack.