Adhoc problems
Count of BSTs catalan numbers but think of the derivation. I can do 1 way for 0 and 1 nodes.
Archive
Iterator in BST
The core idea is simple, you have a pushLeft, on ctor you pushLeft(root) then the next is always the stack top.
Median in a BST
The idea that root is the middle element gets you a “balanced” bst.
Inorder invariant
Inorder traversal ( left → root → right ) is strictly increasing, that much is obvious.
Brute force that tripped me
this was a simple problem in the sense that they were looking for a specific optim that was easy to guess than prove that it was needed.
Traversals
A short note on different BST traversals and if they can be reversed.
Partition Invariant
Everything in the left subtree is smaller than node. Everything in the right subtree is greater than node.
Range invariant
The invariant is that each node will represent a range of valid values. For a binary tree, one end is unbounded. As you go down you partition ranges.
Foundational implementations
Common snippets of code that I should remember and do them exactly this way each time to build memory.
Storage classes
int x for this variable the compiler needs to know when to create memory for it when to destroy it aka how long does it live does another .cpp file refer to this same one are per thread copies The default scope boundaries are commonly known, eccentrics are harder.