Tree Traversals (Pre-order, In-order, Post-order)

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Depth-First Search (DFS) on Trees

Traversing a tree means visiting every node once in a deterministic order. Depth-First Search (DFS) explores down a branch as deep as possible before backtracking.

2. The Three DFS Traversal Orders

The name specifies WHEN the current root node is processed relative to its left and right subtrees:

1. Pre-Order (Root -> Left -> Right): Used to clone/serialize trees.
2. In-Order (Left -> Root -> Right): Visits BST nodes in strictly sorted ascending order!
3. Post-Order (Left -> Right -> Root): Used to delete trees or calculate subtree heights bottom-up.

                 4
               /   \
              2     5
             / \
            1   3

Pre-order:  [ 4, 2, 1, 3, 5 ]
In-order:   [ 1, 2, 3, 4, 5 ]  ◄── Sorted order on BST!
Post-order: [ 1, 3, 2, 5, 4 ]

3. Implementation

// In-order Traversal: Left -> Node -> Right
function inOrderTraversal(root, result = []) {
  if (!root) return result;

  inOrderTraversal(root.left, result);  // 1. Traverse left subtree
  result.push(root.val);                // 2. Visit current node
  inOrderTraversal(root.right, result); // 3. Traverse right subtree

  return result;
}

// Pre-order Traversal: Node -> Left -> Right
function preOrderTraversal(root, result = []) {
  if (!root) return result;

  result.push(root.val);
  preOrderTraversal(root.left, result);
  preOrderTraversal(root.right, result);

  return result;
}

4. Time & Space Complexity

• Time Complexity: $O(N)$ where $N$ is total nodes (every node visited once).
• Space Complexity: $O(H)$ where $H$ is tree height (call stack depth).

5. Common Mistakes

• Forgetting In-Order Yields Sorted BST Elements: When asked to find the $K$-th smallest element in a BST, an in-order traversal yields elements in sorted order directly without sorting!

6. Next Steps

Use in-order for BST validation. Next, let's explore Breadth-First Search (BFS) Level-Order Traversal!