DSA Tutorial

📦 Preorder Traversal in DSA (Binary Tree)

Preorder traversal is one of the Depth First Traversal methods in a binary tree. The sequence of processing nodes is:

          1
         / \
        2   3
       / \
      4   5

      ➤ Preorder Traversal Output: 1 2 4 5 3
      

🧠 Preorder Traversal Algorithm

In preorder, we:

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

💻 Python Code

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

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

⚙️ Output

🎯 Real-Time Use Cases

• Used in copying a tree.
• Used to prefix expression generation (in expression trees).
• Used in serializing and deserializing trees.

🔄 Iterative Approach (with Stack)

Instead of recursion, we can use a stack to simulate preorder traversal:

def preorder_iterative(root):
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val, end=" ")
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
  

📌 Summary

• Visits nodes in Root → Left → Right order.
• Can be implemented using recursion or stack.
• Used in cloning and prefix notation.