## What is it? Inorder traversal visits every node in a binary tree in **Left → Root → Right** order. When applied to a Binary Search Tree, it produces nodes in **sorted ascending order** — making it the key algorithm behind BST iteration. ## How it works - Recursively visit the **left** subtree - **Process (visit)** the current node - Recursively visit the **right** subtree ``` inorder(node): if node is null: return inorder(node.left) visit(node) ← add to result inorder(node.right) ``` ## When to use - Retrieve all elements of a BST in sorted order - Validate whether a binary tree satisfies the BST property - Flatten a BST to a sorted array/list - Any problem requiring sorted enumeration of BST nodes (kth smallest, range queries) ## Key Points - Produces sorted output for BSTs - Recursive call stack depth = O(h) where h is tree height - Iterative version uses an explicit stack - For a balanced BST: h = O(log n); for a skewed tree: h = O(n)