1. What is PreOrder Traversal?

PreOrder traversal is a type of Depth-First Traversal of a binary tree where you:

1. Visit the current node
2. Traverse the left subtree
3. Traverse the right subtree

This is also known as the Root-Left-Right traversal order.

2. PreOrder Traversal Pattern

For each node:

PreOrder(node):
    if node is null:
        return
    visit(node)
    PreOrder(node.left)
    PreOrder(node.right)

3. Java Implementation

class TreeNode {
    int data;
    TreeNode left, right;

    public TreeNode(int item) {
        data = item;
        left = right = null;
    }
}

public class RecursivePreOrderTraversal {

    TreeNode root;

    public void preOrder(TreeNode node) {
        if (node == null)
            return;

        // Step 1: Visit the root
        System.out.print(node.data + " ");

        // Step 2: Traverse the left subtree
        preOrder(node.left);

        // Step 3: Traverse the right subtree
        preOrder(node.right);
    }

    public static void main(String[] args) {
        RecursivePreOrderTraversal tree = new RecursivePreOrderTraversal();

        // Manually creating the binary tree:
        /*
                1
              /   \
             2     3
            / \   /
           4   5 6
        */

        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        tree.root.right.left = new TreeNode(6);

        System.out.println("PreOrder traversal of binary tree is:");
        tree.preOrder(tree.root); // Output: 1 2 4 5 3 6
    }
}

8. Time and Space Complexity

Time Complexity: O(n)

• You visit every node exactly once.

Space Complexity:

• O(h), where h is the height of the tree (due to the recursive call stack).
• In the worst case (skewed tree), this becomes O(n).
• In a balanced tree, this is O(log n).