TODO
Top Current: ELF Immediate: Writing an ELF manually Stack For I have so little time.
Archive
Adhoc problems
Count of BSTs catalan numbers but think of the derivation. I can do 1 way for 0 and 1 nodes.
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.