Inorder

Run an inorder traversal on a **Binary Search Tree (BST)** of any size and the keys come out sorted, in `O(n)` time and `O(h)` space, with no separate sort step. That single property (an ordering invariant baked into the structure itself) is what turns a generic binary tree into a logarithmic-time search container that powers Java's `TreeMap`, C++ `std::map`, and the conceptual model behind every database index. This lesson covers the BST property (left subtree keys less than the node, right subtree keys greater), search and insert that follow the invariant, the three deletion cases (leaf, one child, two children resolved by inorder successor or predecessor), and the validation problem that interviewers love because the naive `node.left.val < node.val` check is wrong. You will also analyze the gap between the balanced `O(log n)` and the degenerate `O(n)` chain that motivates the next lesson. In **Trees: Binary Tree Fundamentals**, you implemented preorder, inorder, postorder, and level-order traversals; the BST property is what makes inorder special, because it now produces sorted output for free. Next, **Balanced BST (AVL / Red-Black)** addresses the elephant in the room: an unlucky insertion order can degrade a BST to a linked list, and self-balancing rotations are the fix.

Every web page you load is a tree (the DOM), every directory you `cd` into is a tree, every JSON document with nested objects is a tree, and every arithmetic expression a compiler parses is a tree. **Binary Tree Fundamentals** turns that ubiquitous shape into a precise data structure where each node has at most two children, named `left` and `right`. This lesson covers the vocabulary you need for the rest of the curriculum (root, leaf, parent, child, sibling, depth, height), the four common shape categories (full, complete, perfect, balanced) and the degenerate case that collapses to a chain, all four canonical traversals (preorder, inorder, postorder, and level-order BFS), and both recursive and iterative implementations of each. You will also analyze why traversals are `O(n)` time but only `O(h)` space when written recursively. In **Queue & Deque**, you saw that a FIFO queue processes items in arrival order; level-order traversal is exactly that pattern applied to tree nodes. In **Hash Map (Dictionary) Basics**, the bucket-by-key idea reappears here when you store parent-pointer mappings or memoize subtree results during a traversal. With binary trees in your toolkit, **Binary Search Tree (BST)** layers an ordering invariant on top to turn the same shape into a logarithmic-time search structure.