A complete guide to binary tree traversals covering Depth-First Search (Pre-order, In-order, Post-order), Breadth-First Search (Level-order), and O(1) space Morris Traversal.
Key Takeaways Summary:
- In-order traversal of a Binary Search Tree (BST) produces nodes in sorted order.
- Pre-order traversal is ideal for cloning or serializing tree structures.
- Post-order traversal is used for bottom-up node deletions and subtree depth evaluations.
- Morris Traversal achieves O(1) auxiliary space complexity by temporarily modifying tree pointers.
1. Depth-First Search (DFS) Patterns
Tree traversals are fundamental to algorithmic problem-solving. Depth-First Search explores as deep as possible along each branch before backtracking. The order in which the root node is visited relative to its left and right subtrees dictates the traversal type:
- **Pre-Order (Root -> Left -> Right)**: Process root first.
- **In-Order (Left -> Root -> Right)**: Process left subtree, visit root, process right subtree.
- **Post-Order (Left -> Right -> Root)**: Process subtrees first, visit root last.
2. Recursive & Iterative In-Order Traversal
Here is the clean implementation for In-Order Traversal using both recursion and an explicit Stack data structure:
javascript
// Iterative In-Order Traversal using Stack O(N) Time, O(H) Space
function inorderTraversal(root) {
const result = [];
const stack = [];
let curr = root;
while (curr !== null || stack.length > 0) {
// Reach the leftmost node of current node
while (curr !== null) {
stack.push(curr);
curr = curr.left;
}
// Current must be null at this point
curr = stack.pop();
result.push(curr.val);
// We have visited the node and its left subtree. Now, it's right subtree's turn
curr = curr.right;
}
return result;
}